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

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 2

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 3

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.

Answer 4

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

Answer 5

The regex-applicative package defines a custom many method for the RE (regular expression) type. Regular expressions, and therefore RE parsers, must be finite in size, so using default definitions for both some and many would lead to infinite loops! Fortunately, many is just the classic regular expression *.

The package also includes a definition of some, but that looks too much like the default definition to be anything interesting.