Is it possible to express chain1 using the applicative?

Question

Is it possible to express the chainl1 combinator without using the Monad instance defined by the parsec?

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

Answer 1

Yes this:

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

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

This may help expand the definition a bit:

 chainl1 p op = foldl (\xf -> fx) <$> p <*> many ((\fy -> flip fy) <$> op <*> p) 

When the op and p pairs are parsed, the results are applied immediately, but since p is the correct operand of op , it needs 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 the initial value of p on foldl .

Answer 2

An ugly but equivalent Applicative definition:

 chainl1 p op = p <**> rest where rest = flip <$> op <*> p <**> pure (.) <*> rest <|> pure id 

Instead of passing the left argument x explicitly to the right side of op this applicative form of the “chain” op partially applies to their right argument (hence, flip <$> op <*> p ) through the raised combinator (.) , And then applies the leftmost p through (<**>) to the resulting rest :: Alternative f => f (a -> a) .