[SOLVED] What is the meaning of the definitions for the "some" and "many" functions in the Haskell Alternative

What is the meaning of the definitions for the "some" and "many" functions in the Haskell Alternative

I've been looking to write a lexer in Haskell and stumbled upon these functions.

If defined, some and many should be the least solutions of the equations:

some v = (:) <$> v <*> many v

many v = some v <|> pure []

I get that the (:) in some gets lifted and applied to the value of v in order to prepend it to the list returned in many v.

But why does the definition of many start with some? And why does it get concatenated with pure []?

What is the relationship or difference between these two functions? What does it mean for some and many to be the least solutions of those equations? And how does the recursion ever stop? Help!

Solution

some p means one or more match of p
many p means zero or more more match of p

For input "abc", many letter and some letter will both parse abc.

But for input "123", many letter will output empty string "". some letter will report error.

According to the definition. some v needs at least 1 match of v, so we can first parse v then we need 0 or more match of v, which is many v. It is something like :

some v = do
    first_match <- v
    rest_matches <- many v
    return $ first_match : rest_matches

which is the same as some v = (:) <$> v <*> many v.

But for many v. It will either match some v (1 or more) or nothing (pure []).

many v = if matches (some v) then return (some v) else return nothing.

You can try solve writing applicative parsers from scratch from codewars.

Functional pearls is also a very good reference about parse combinators.