22

What are the functions some and many in the Alternative type class useful for? Docs provide a recursive definition which I was unable to comprehend.

duplode
  • 33,731
  • 7
  • 79
  • 150
missingfaktor
  • 90,905
  • 62
  • 285
  • 365

2 Answers2

44

some and many can be defined as:

some f = (:) <$> f <*> many f
many f = some f <|> pure []

Perhaps it helps to see how some would be written with monadic do syntax:

some f = do
  x <- f
  xs <- many f
  return (x:xs)

So some f runs f once, then "many" times, and conses the results. many f runs f "some" times, or "alternatively" just returns the empty list. The idea is that they both run f as often as possible until it "fails", collecting the results in a list. The difference is that some f immediately fails if f fails, while many f will still succeed and "return" the empty list in such a case. But what all this exactly means depends on how <|> is defined.

Is it only useful for parsing? Let's see what it does for the instances in base: Maybe, [] and STM.

First Maybe. Nothing means failure, so some Nothing fails as well and evaluates to Nothing while many Nothing succeeds and evaluates to Just []. Both some (Just ()) and many (Just ()) never return, because Just () never fails! In a sense they evaluate to Just (repeat ()).

For lists, [] means failure, so some [] evaluates to [] (no answers) while many [] evaluates to [[]] (there's one answer and it is the empty list). Again some [()] and many [()] don't return. Expanding the instances, some [()] means fmap (():) (many [()]) and many [()] means some [()] ++ [[]], so you could say that many [()] is the same as tails (repeat ()).

For STM, failure means that the transaction has to be retried. So some retry will retry itself, while many retry will simply return the empty list. some f and many f will run f repeatedly until it retries. I'm not sure if this is useful thing, but I'm guessing it isn't.

So, for Maybe, [] and STM many and some don't seem to be that useful. It is only useful if the applicative has some kind of state that makes failure increasingly likely when running the same thing over and over. For parsers this is the input which is shrinking with every successful match.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Sjoerd Visscher
  • 11,840
  • 2
  • 47
  • 59
  • 1
    It's a bit misleading to say that `some (Just ())` evaluates to `Just (repeat ())` (even with the "in a sense" caveat), because that made me wonder if an expression like `some (Just ()) >>= return . head` might behave like `Just (repeat 1) >>= return . head`, but it doesn't; the latter terminates and the former doesn't. – Ose Feb 15 '22 at 16:32
8

E.g. for parsing (see the "Applicative parsing by example" section).

Alexey Romanov
  • 167,066
  • 35
  • 309
  • 487
  • 2
    I am not familiar with Parsec. I'd appreciate some explanation. – missingfaktor Oct 06 '11 at 07:41
  • 2
    As far as I understand, if you have a parser `p` for X, then `some p` is a parser for 0 or more X and `many p` is a parser for 1 or more X. – Ingo Oct 06 '11 at 09:08
  • 2
    @missingfaktor `some` and `many` are implementaed in terms of `<|>`. This combinator is useful also in other ways. Consider `Either`: `Just 0 <|> Just 1 = Just 0`, `Nothing <|> Just 2 = Just 2`, `Just 3 <|> Nothing = Just 3`, `Nothing <|> Nothing = Nothing` – fuz Oct 06 '11 at 10:17
  • @Ingo: I understood their use with respect to parsers, thanks. Still I am curious what these functions are useful for _in general_. – missingfaktor Oct 06 '11 at 11:05
  • @FUZxxl: See my above comment. – missingfaktor Oct 06 '11 at 11:05
  • 1
    @missingfaktor: that is the usual application; I'm not sure if `Alternative` is used for anything else. You could say that "in general", `some` is used whenever you want something to run multiple times (but doesn't **have** to run), and `many` to run at least once. – ivanm Oct 06 '11 at 11:24
  • 3
    @Ingo @ivanm Note that you have `some` and `many` backwards. `some` is one or more (i.e. `+` in regexps) and `many` is zero or more (i.e. `*`). – Sjoerd Visscher Oct 06 '11 at 20:24
  • 1
    @Ingo just for the record, it's the other way around: `some` is one or more, `many` is 0 or more results collected from performing the same computation over and over. so 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. – Will Ness Jun 16 '20 at 05:23