functions 'some' and 'many' from the class 'Alternative'

Why are some and many functions in the Alternative class of types? The docs give a recursive definition that I could not understand.

+17
functional-programming haskell typeclass
06 Oct '11 at 6:45
source share
2 answers

some and many can be defined as:

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

Perhaps this helps to see how some will be written with the monadic do syntax:

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

So some f runs f once, then many times, and saves the results. many f starts f several times, or alternatively just returns an empty list. The idea is that they both start f as often as possible until they “fail”, collecting the results in a list. The difference is that some f fails if f fails immediately and many f succeeds and returns an empty list. But what it all means depends exactly on how <|> defined.

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

First Maybe . Nothing means failure, so some Nothing also fails and evaluates to Nothing , and many Nothing fails with the Just [] error. Both some (Just ()) and many (Just ()) never return, because Just () will never work! In a sense, they evaluate the value of Just (repeat ()) .

For lists, [] means failure, so some [] evaluates to [] (no answers), and many [] evaluates to [[]] (there is one answer, and this is an empty list). Again, some [()] and many [()] not returned. Extending instances of some [()] means fmap (():) (many [()]) and many [()] means some [()] ++ [[]] , so you can say that many [()] same as tails (repeat ()) .

For STM failure means the transaction must be retried. This way some retry will try again, and many retry will just return an empty list. some f and many f will run f several times until it retries. I am not sure if this is a useful thing, but I assume that it is not.

So for Maybe , [] and STM many and some do not seem to be that useful. This is only useful if there is some kind of condition in the applicative state that makes failure more likely when repeating the same subject over and over. For parsers, this is an input that decreases with each successful match.

+34
Oct 06 2018-11-11T00:
source share

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

+8
Oct 06 '11 at 7:12
source share



All Articles