haskell - What are Alternative's "some" and "many" useful for?

Question

Alternative, an extension of Applicative, declares empty, <|> and these two functions:

One or more:

some :: f a -> f [a]

Zero or more:

many :: f a -> f [a]

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

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

many v = some v <|> pure []

I couldn't find an instance for which some and many are defined. What is their meaning and practical use? Are they used at all? I've been unable to grasp their purpose just from this definition.

Update: I'm not asking what is Alternative, just what are some and many

Answer 1

TL;DR: some is one or more, many is 0 or more results collected from performing the same computation over and over by the familiar maximal munch rule. For this to make sense, some state passing (and alteration) must take place reducing the domain of possibilities somehow, otherwise it will repeat ad infinitum. And state passing and parsing are closely related.

---

An elementary example instance: with

import Control.Monad(Functor(..))
import Control.Applicative
import Data.Char

-- char string parser
newtype P a = P { runP :: String -> [(a,String)] }

-- runP (P p) s = p s

instance Functor P where
  -- fmap :: (a -> b) -> f a -> f b
  fmap f (P q) = P (s -> [ (f y,ys) | (y,ys) <- q s])

instance Applicative P where
  -- pure :: a -> f a
  pure x = P (s -> [(x,s)])
  -- (<*>) :: f (a -> b) -> f a -> f b
  P p <*> P q = P (s -> [(x y, ys) | (x,xs) <- p s, (y,ys) <- q xs])

letter = P p where      -- sample parser
  p (x:xs) | isAlpha x = [(x,xs)]
  p _ = []

we have

*Main Data.Char> runP letter "123"
[]
*Main Data.Char> runP letter "a123"
[('a',"123")]
*Main Data.Char> runP ( (:) <$> letter <*> pure []) "a123"
[("a","123")]
*Main Data.Char> runP ( (:) <$> letter <*> ((:)<$>letter <*> pure []) ) "a123"
[]
*Main Data.Char> runP ( (:) <$> letter <*> ((:)<$>letter <*> pure []) ) "ab123"
[("ab","123")]   -- NOT NICE ^^^^^^^^^^^^^^^^^^^^ -}

Then, with

instance Alternative P where
  -- (<|>) :: f a -> f a -> f a
  P p <|> P q = P (s-> p s ++ q s)
  -- empty :: f a   -- the identity of <|>
  empty = P (s-> [])

we get

*Main Data.Char> runP (many letter) "ab123"
[("ab","123"),("a","b123"),("","ab123")]
*Main Data.Char> runP (some letter) "ab123"
[("ab","123"),("a","b123")]

*Main Data.Char> runP (optional letter) "ab123"
[(Just 'a',"b123"),(Nothing,"ab123")]
*Main Data.Char> runP (optional letter) "123"
[(Nothing,"123")]

Prelude Main Data.Traversable> runP (sequenceA $ replicate 2 letter) "ab123"
[("ab","123")]               --  NICE  ^^^^^^^^^^^^^^^^^^^
-}