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
andmany
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
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 ^^^^^^^^^^^^^^^^^^^ -}