Conditional looping in an Applicative Functor

Question

Suppose that Parser x is a parser that parses an x. This parser probably possesses a many combinator, that parses zero or more occurrences of something (stopping when the item parser fails).

I can see how one might implement that if Parser forms a monad. I can't figure out how to do it if Parser is only an Applicative Functor. There doesn't seem to be any way to check the previous result and decide what to do next (precisely the notion that monads add). What am I missing?

Answer 1

The Alternative type class provides the many combinator:

class Applicative f => Alternative f where
    empty :: f a
    (<|>) :: f a -> f a -> f a
    many  :: f a -> f [a]
    some  :: f a -> f [a]

    some = some'
    many = many'

many' a = some' a <|> pure []
some' a = (:) <$> a <*> many' a

1. The many a combinator means “zero or more” a.
2. The some a combinator means “one or more” a.

Hence:

1. The some a combinator returns a list of one a followed by many a (i.e. 1 + (0 or more)).
2. The many a combinator returns either some a or an empty list (i.e. (1 or more) | 0).

The many combinator depends upon the (<|>) operator which can be viewed as the default operator in languages like JavaScript. For example, consider the Alternative instance of Maybe:

instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

Essentially the (<|>) should return the left hand side value if it's truthy. Otherwise it should return the right hand side value.

A Parser is a data structure which is defined similarly to Maybe (the idea of applicative lexer combinators and parser combinators is essentially the same):

data Lexer a = Fail | Ok (Maybe a) (Vec (Lexer a))

If parsing fails, the Fail value is returned. Otherwise an Ok value is returned. Since Fail <|> pure [] is pure [], this is how the many combinator knows when to stop and return an empty list.

Answer 2

It can't be done just by using what is provided by Applicative. But Alternative has a function that gives you power beyond Applicative:

(<|>) :: f a -> f a -> f a

This function lets you "combine" two Alternatives without any restriction whatsoever on the a. But how? Something intrinsic to the particular functor f must give you a means to do that.

Typically, Alternatives require some notion of failure or emptiness. Like for parsers, where (<|>) means "try to parse this, if it fails, try this other thing". But this "dependence on a previous value" is hidden in the machinery implementing (<|>). It is not available to the external interface, so to speak.

From (<|>), one can implement a zero-or-one combinator:

optional :: Alternative f => f a -> f (Maybe a)
optional v = Just <$> v <|> pure Nothing

The definitions of some an many are similar but they require mutually recursive functions.

Notice that there are Applicatives that aren't Alternatives. You can't make the Identity functor an Alternative, for example. How would you implement empty?