Как я могу перейти от `a -> Parser b` к `Parser (a → b)`?

Question

Я пытаюсь обновить парсер синтаксического анализа, который использует Text.Parsec.Expr . Я пытаюсь (и, возможно, это опрометчиво, но, похоже, это должно быть практично) встроить часть проверки DSL в парсер. Но у меня возникли проблемы с тем, чтобы это работало с типом, тело которого должно быть синтаксическим анализатором, возвращающим функцию.

      data Location = Location { owners :: PartySet, source :: SourcePos } deriving (Eq, Ord, Show)
type Located = (,) Location
type Parser = Parsec String (Map Variable PartySet)

-- Pair a parsed thing with it's position in the source file
positioned :: Parser a -> Parser (SourcePos, a)
positioned p = do source <- getPosition
                  (source,) <$> p

chooseOf :: (TokenParser st -> t -> Parsec.Parser a) -> [t] -> Parser (SourcePos, a)
chooseOf cls subcls = choice $ [positioned $ cls tokenizer sc | sc <- subcls]

-- Define parser for Algebra
algebraParser :: Parser (Located (Algebra Located))
algebraParser = buildExpressionParser ops terms

terms = parens tokenizer algebraParser <|> litParser <|> varParser

-- Parse a Literal Bit (0 or 1)
litParser = do (source, b) <- (const (Bit True) <$$> chooseOf reserved trueNames)
                               <|> (const (Bit False) <$$> chooseOf reserved falseNames)
               let loc = Location{source, owners=top}
               return (loc, Literal (loc, b))

-- Parse a variable as they appear in algebra terms
varParser = do (loc, var) <- boundVariable
               return (loc, Var (loc, var))

-- Step 1 for building the Operator objects
biOpParser :: (Located (Algebra Located) -> Located (Algebra Located) -> Algebra Located)
              -> SourcePos
              -> (Located (Algebra Located), Located (Algebra Located))
              -> Parser (Located (Algebra Located))
biOpParser constructor source (alg1@(Location{owners=o1}, _), alg2@(Location{owners=o2}, _)) =
  do let mowners = o1 `intersect` o2
     maybe (parserFail "Can't compute binary operator. Nobody owns both arguments")
           (\owners -> return (Location{source, owners}, constructor alg1 alg2))
           mowners

-- Step 2, broken out for the XOR case.
xorParser :: Parser (Located (Algebra Located) -> Located (Algebra Located) -> Located (Algebra Located))
xorParser = do (source, _) <- chooseOf reservedOp xorNames
               curry <$> sequence (biOpParser Xor source)
ops :: OperatorTable String (Map Variable PartySet) Identity (Located (Algebra Located))
ops = [ [Prefix $ do (source, _) <- chooseOf reservedOp notNames
                     return \alg@(loc, _) -> (loc{source}, Not alg)]
       ,[Infix xorParser AssocLeft]
       -- Step 3; the AND case has step 2 inlined.
       ,[Infix (do (source, _) <- chooseOf reservedOp andNames
                   curry <$> sequence (biOpParser And source)) AssocLeft] ]

Я могу добавить больше кода, если это будет полезно; или я мог бы попытаться свести это к более чистой ситуации.

Проблема внутриalgebraParser; я хочу использоватьbuildExpressionParser, для чего требуется таблицаOperatorс.
Суть проблемы в том, parserFail "Can't XOR. Nobody owns both arguments"внутри biOpParser.
Операционный термин (например,XOR) может быть действительным, а может и не быть действительным в зависимости от «типа» (владения) его аргументов. Я пытаюсь использовать «состояние пользователя» монады Parser для хранения прав собственности и (соответственно) хочу, чтобы нарушения отображались как ошибки синтаксического анализатора. Это означает, что тест должен быть написан внутри монады Parser, чтобы я мог использоватьparserFail, но это противоречит необходимости получения парсером функции op .

Фактическая ошибка, показанная для приведенного выше кода, относится кsequence (biOpParser Xor source)внутриxorParser:

      No instance for (
  Traversable (
    (->) (Located (Algebra Located), Located (Algebra Located))
  )
) arising from a use of ‘sequence’

Я понимаю, что невозможно/неразумно инвертировать произвольные пары вложенных монад; насколько я могу судить, Distributive тоже не поможет, верно?

Есть ли легкое решение? Есть ли разумное изменение в моем подходе, которое может сработать? Есть ли еще какая-то фундаментальная вещь, которую я неправильно использовал или неправильно понял?

Answer 1

Два комментария к вашему вопросу уже дают вам ответ: вы не можете написать функцию типа(a -> Parser b) -> Parser (a -> b). Чтобы понять почему, рассмотрим, что означает этот тип. Я даю вам способ, учитывая значение типа, проанализировать другое значение типа. Исходя из этого, вы должны вернуть мне синтаксический анализатор, который создает функцию от до . Важно соблюдать эти две вещи:

1. Парсер, который вы мне возвращаете в результате, не имеетaзначения для просмотра, поэтому вы не сможете вызвать функцию, которую я вам передал.
2. Функция, возвращаемая вашим анализатором, не должна выполнять синтаксический анализ . Это простая функция типаa -> b: нет никакихParserгде угодно, так что это просто скучная чистая функция. Вы не можете реализовать эту функцию так: «Сначала вызовитеa -> Parser bфункцию, которую мне дали, а затем проанализироватьb, а затем верните это", потому что ему запрещено ничего анализировать.

Я надеюсь, что из этих двух пунктов становится яснее, что с этой сигнатурой не существует никакой возможной функции.

Answer 2

ТвойbiOpParserв конечном итоге используетo1иo2значения, передаваемые ему через аргументы, чтобы решить, потерпеть ли неудачу сparseFailили для успешного анализа. Говоря о конверсии, которую вы упомянули в заголовке вопроса, она использует для определения эффектов вa -> Parser b.Parser (a -> b)не позволяет этого сделать, так как у такого типа эффекты задаются изначально и не могут зависеть отaценности. В таком случае вы не сможете реализовать свой комбинатор с другой сигнатурой, и преобразование вам не поможет.

В более общем смысле, разница между и сводится к увеличению мощности при переключении с аппликативного интерфейса на монадический. С помощью аппликативов вы можете комбинировать эффекты, используя, например,(<*>)...

      (<*>) :: Applicative m => m (a -> b) -> m a -> m b

... но вы не можете генерировать эффекты из простых значений, поскольку позволяет монадическая привязка:

      (=<<) :: Monad m => (a -> m b) -> m a -> m b

Функторы особенны тем, что их аппликативные и монадные экземпляры эквивалентны, и поэтому с их помощью вы можете a -> m bв m (a -> b)ничего не теряя при этом . Однако все дистрибутивные функторы изоморфны функциям (т.((->) r)функтор, для некоторого конкретного выбораr). Одним из последствий этого является то, что дистрибутивы не могут выражать сбой или эффекты состояния, и поэтомуParserнельзя датьDistributiveпример.