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

Accentor

Although there are some nice answers here, however this question is a possible duplicate of this, this and this – Hemipterous

they are what it says: combinators for multiple application of (e.g.) a parser, collecting the results in a list. I provided the elementary example where the definitions are easily followed. – Heaton

@WillNess Thank, I didn't think about parsers. Still what puzzles me is why they're included in Alternative, when these functions are undefined for the basic classes. – Accentor

A duplicate question got this very nice answer. – Ligniform

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 (<|>).

Protuberancy

Answer 2

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

Heaton

Good explanation! – Citrate

Off-topic, meta question: I noticed you have created the missing [haskell-alternative] tag. Some time ago, I had thought of doing the same, and even compiled a list of questions we might want to add it to, but got stuck pondering whether to combine MonadPlus and Alternative into a single tag (my instinctive inclination) or to keep them apart, and what to name the tag(s) (I had originally thought of [monadplus-and-alternative]). I would appreciate your opinion on those issues -- it could help me to finally make up my mind :) – Plautus

@Plautus I used "haskell-" there since "alternative" by itself seemed too vague and too general. with "monadplus-and-" there's indeed no need for it from that perspective. as to whether to join them together, do you have in your list many questions that would need both haskell-alternative and haskell-monadplus? if not, you could define the latter and tag those few with the both of them. if yes, you could rename the current tag (by simply retagging its current 11 question) to either monadplus-and-alternative or haskell-monadplus-and-alternative. or is your list too short (contd.) – Heaton

... to be a valid indicator? – Heaton

@WillNess Checking my spreadsheet, I found 20 Alternative candidates that are also on the MonadPlus list, out of a total of 93. While that's significant overlap, it should be workable to have separate tags. And yes, the Alternative tag sure need a prefix. Ideally, I'd have something other than "haskell-" for the benefit of hypothetical PureScript/Scala/etc. questions (I'll likely use [monadplus] for the other tag for that reason), but I can't think of anything better ([alternative-typeclass], in particular, isn't very good). Anyway, I'll get on with the retagging soon. Thanks! – Plautus

@Plautus maybe functor-alternative? (and even functor-monadplus??) – Heaton

@WillNess Good idea, [alternative-functor] sounds great! – Plautus

@WillNess Retagging done! With 64 questions so far, alternative-functor has come along nicely. At 39 questions, 14 of them shared with [alternative-functor], monadplus doesn't feel as solid, though this gem of an unresolved controversy is perhaps worth the price of admission already. – Plautus

@Plautus great and necessary (and thankless) work! the numbers are quite nice, BTW, the both of them; I've encountered quite a few tags with a dozen questions or less, which felt necessary nevertheless, so 39 is not a small number at all. :) – Heaton

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.

Tachycardia

Neat, never thought about that! – Chassidychassin

Answer 4

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.

Parlous

I understand all that. To clarify, the definitions of some and many for the most basic types such as [] and Maybe just loop. So although the definition of some and many for them is valid, it has no meaning. – Accentor

@PetrPudlák I really liked this answer (thanks, is7s). – Heaton

@WillNess Indeed, this answer is very nice. – Accentor

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.

Mitochondrion