How can I get from `a -> Parser b` to `Parser (a -> b)`?

Question

I'm trying to update a parsec parser that uses buildExpressionParser from Text.Parsec.Expr. I'm trying (and possibly this is ill-advised, but it looks like it's supposed to be practical) to build part of the DSL verification into the parser. But I'm having trouble getting this to work with the Operator type, who's body needs to be a parser that yields a function.

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] ]

I can add more of the code if that's helpful; or I could try to reduce this to a more pure situation.

The problem is inside algebraParser; I want to use buildExpressionParser, which requires a table of Operators.
The heart of the problem is parserFail "Can't XOR. Nobody owns both arguments" inside biOpParser.
An op-term (like XOR) may or may not be valid depending on the "type" (ownership) of its arguments. I'm trying to use the "user state" of the Parser monad to store ownerships, and (correspondingly) I'd like violations to show up as parser errors. That means the test needs to be written inside the Parser monad so I can use parserFail, but that conflicts with the need for the "op function" to be yielded by the parser.

The actual error shown for the code above is for sequence (biOpParser Xor source) inside xorParser:

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

I understand that it's not possible/sensible to invert arbitrary pairs of nested monads; as far as I can tell Distributive wouldn't help either, right?

Is there an easy fix? Is there a reasonable change to my approach that's likely to work? Is there some other fundamental thing I've misused or misunderstood?

[`Distributive` would allow doing that](https://stackoverflow.com/q/75928651/2751851), but `Parser` isn't distributive. — duplode, Apr 12 '23 at 16:58
I'm curious if anyone has suggestions about making an `instance Distributive Parser`. Probably it would already exist if it were possible... — ShapeOfMatter, Apr 12 '23 at 17:51

amalloy · Answer 1 · 2023-04-13T00:19:28.077

Two comments on your question already give you the answer: You cannot write a function of type (a -> Parser b) -> Parser (a -> b). To see why, consider what that type means. I give you a way, given a value of type a, to parse another value of type b. From that, you must give me back a parser that produces a function from a to b. Importantly, observe these two things:

The parser you give me back as a result has no a values to look at, so you can't call the function I passed you.
The function your parser returns must do no parsing. It's a simple function of type a -> b: there's no Parser in there anywhere, so it's just a boring pure function. You can't have the implementation of that function be "First, call the a -> Parser b function I was given, and then parse a b, and then return that", because it's not allowed to parse anything.

From these two points I hope it is more clear that there's no possible function with this signature.

duplode · Answer 2 · 2023-04-12T22:07:05.800

Your biOpParser ultimately uses the o1 and o2 values passed to it through its arguments to decide whether to fail with parseFail or to produce a successful parse. Speaking in terms of the conversion you mention in the question title, it uses the a to decide the Parser effects in a -> Parser b. Parser (a -> b) doesn't allow for that, as with such a type the Parser effects are given at the outset, and can't depend on the a values. That being so, you can't implement your combinator with the other signature, and the conversion wouldn't help you.

More generally, the difference between m (a -> b) and a -> m b amounts, in a nutshell, to the increase in power when you switch from an applicative interface to a monadic one. With applicatives, you can combine effects using, for instance, (<*>)...

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

... but you can't generate effects out of plain values, as monadic bind allows:

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

Distributive functors are special in that their applicative and monad instances are equivalent, and so with them you can turn a -> m b into m (a -> b) without losing anything in the process. Distributive functors, however, are all isomorphic to functions (the ((->) r) functor, for some specific choice of r). One consequence of that is that distributives can't express failure or state effects, and so Parser cannot be given a Distributive instance.

How can I get from `a -> Parser b` to `Parser (a -> b)`?

2 Answers2