What are Alternative's “some” and “many” usefu

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

Will provided a good example motivating the use of those methods, but you seem to still have a misunderstanding about type classes.

A type class definition lists the type signatures for the methods that exist for all instances of the type class. It may also provide default implementations of those methods, which is what is happening with Alternative's some and many methods.

In order to be valid instances, all of the methods have to be defined for the instance. So the ones that you found that did not specifically define instances for some or many used the default implementations, and the code for them is exactly as listed in your question.

So, just to be clear, some and many are indeed defined and can be used with all Alternative instances thanks to the default definitions given with the type class definition.

Answer 2

I tend to see them in Applicative parser combinator libraries.

a :: Parser [String]
a = some (string "hello")

and I see many used for purpose in the default definitions of Parsing in parsers.

I think Parsec being the primary example of a parser combinator library hides the use of some/many since it redefines things like (<|>).

Answer 3

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

Answer 4

In the STM Applicative, some would mean: Keep trying until it succeeds at least once, and then keep doing it until it fails. many would mean: Do this as many times as you can until failure.