Search code examples
parsinghaskellparsec

Is it possible to express chainl1 using applicative?

Is it possible to express the chainl1 combinator from Parsec not using the Monad instance defined by parsec?

chainl1 p op =
  do x <- p
     rest x
  where
    rest x = do f <- op
                y <- p
                rest (f x y)
          <|> return x
Solution

  • Yes, it is:

    chainl1 p op = foldl (flip ($)) <$> p <*> many (flip <$> op <*> p)

    The idea is that you have to parse p (op p)* and evaluate it as (...(((p) op p) op p)...).

    It might help to expand the definition a bit:

    chainl1 p op = foldl (\x f -> f x) <$> p <*> many ((\f y -> flip f y) <$> op <*> p)

    As the pairs of op and p are parsed, the results are applied immediately, but because p is the right operand of op, it needs a flip.

    So, the result type of many (flip <$> op <*> p) is f [a -> a]. This list of functions is then applied from left to right on an initial value of p by foldl.