Haskell - some, many implementation

Question

In the article: "Write you a Haskell" (page 34) the following interpretation of "some" and "many" is given:

Derived automatically from the Alternative typeclass definition are the many and some functions. many takes a single function argument and repeatedly applies it until the function fails, and then yields the collected results up to that point. The some function behaves similar except that it will fail itself if there is not at least a single match.

-- | One or more.
some :: f a -> f [a]
some v = some_v
  where
    many_v = some_v <|> pure []
    some_v = (:) <$> v <*> many_v

-- | Zero or more.
many :: f a -> f [a]
many v = many_v
  where
    many_v = some_v <|> pure []
    some_v = (:) <$> v <*> many_v

I have been trying to understand this implementation for a while.

I dont understand how "many" and "some" could be applied to "lists" or "Maybe".

Also I am not sure about (:) <$> v <*> many_v.

How does one derive this?

Answer 1

From ghc/libraries/base/GHC/Base.hs there is this recursive declaration:

    ... :: f a -> f [a]
    ...
        many_v = some_v <|> pure []
        some_v = liftA2 (:) v many_v  -- (:) <$> v <*> many_v

The argument v must be a value of a type that is instance of Alternative (and Applicative and Functor). v is lifted already and just needs to be applied (<*>). The application results in a lifted list.

some and many make recursive applications of the constructor of v, and put the constructed values into a list.

• some stops application, when the first empty is constructed
• many continues application beyond that

[] is instance of Alternative:

instance Alternative [] where
    empty = []
    (<|>) = (++)

some tries with list:

  av = [[2], [2,3], [], [2,3,5]]
  some av                      -- no error, but never stops
  do {v <- some av; return v;} -- no error, but never stops

Comparing to letter in What are Alternative's "some" and "many" useful for?:

  import Control.Monad(Functor(..))
  import Control.Applicative
  import Data.Char
  newtype P a = P { runP :: String -> [(a,String)] }
  instance Functor P where
    fmap f (P q) = P (\s -> [ (f y,ys) | (y,ys) <- q s])
  instance Applicative P where
    pure x = P (\s -> [(x,s)])
    P p <*> P q = P (\s -> [(x y, ys) | (x,xs) <- p s, (y,ys) <- q xs])
  letter = P p where
    p (x:xs) | isAlpha x = [(x,xs)]
    p _ = []
  instance Alternative P where
    P p <|> P q = P (\s-> p s ++ q s)
    empty = P (\s-> [])

with usage:

  runP (many letter) "ab123"

letter is a smart constructor, that constructs a value of P with field runP using local variable p. (The result of the accessor) runP is a function. P is a type implementing Alternative as well as a constructor. P stands for parser.

fmap is not used in some and many. <*> leads to an application of the function runP, whose argument is not yet here. Basically some and many construct a program that will eat from its argument. The argument must be a list. Due to laziness the recursion stops at the first constructor.

  p = some letter -- constructs a program accessed via @runP@
  runP p "a1" -- [("a","1")]

  q = some [2] -- basically also a program
  q -- never stops

Recursive application is not empty ([] for list), because there is no source of criteria to stop, i.e. no input.

These stop:

  some [] -- []
  many [] -- [[]]
  some Nothing -- Nothing
  many Nothing -- Just []

There are more requirements on the argument of some and many (v).

• v is value of a type that is instance of Alternative.
• The recursive application of the constructor of the v type must stop with empty.
• v must contain a function applied during construction with <*> to have stop criteria.

Conclusion: some and many cannot be applied to list values, even though list implements Alternative.

Why does list implement Alternative? I think, it is to add the Monoid interface <|> and empty on top of Applicative, not because of some and many.

  foldr (<|>) [] [[2],[],[3,4]] -- [2,3,4]

some and many seem to be just for parser construction or more generally construction of a program consuming input and producing more outputs, of which some can be empty. That is quite general already. But the place in Alternative is only justified, if most of Alternative instances have a sensible usage for it. That is not the case.