What are Alternative’s “some” and “many” useful for?

by

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

More Related Contents:

  1. Distinction between typeclasses MonadPlus, Alternative, and Monoid?
  2. ‘some’ and ‘many’ functions from the ‘Alternative’ type class [duplicate]
  3. Good examples of Not a Functor/Functor/Applicative/Monad?
  4. Applicatives compose, monads don’t
  5. Confused by the meaning of the ‘Alternative’ type class and its relationship to other type classes
  6. Applicative functor evaluation is not clear to me
  7. Difference between Monad and Applicative in Haskell
  8. How to interpret bind/>>= of the function instance?
  9. Why should Applicative be a superclass of Monad?
  10. Monoidal Functor is Applicative but where is the Monoid typeclass in the definition of Applicative?
  11. How to handle side effect with Applicative?
  12. functions as applicative functors (Haskell / LYAH)
  13. How to run a for loop in Haskell
  14. Getting started with Haskell
  15. How is this fibonacci-function memoized?
  16. runST and function composition
  17. Explain this chunk of haskell code that outputs a stream of primes
  18. What does (f .) . g mean in Haskell?
  19. foldl versus foldr behavior with infinite lists
  20. What is the purpose of Rank2Types?
  21. What are paramorphisms?
  22. Generating Fibonacci numbers in Haskell?
  23. Is there a way to place some impure code inside pure functions?
  24. How to increment a variable in functional programming?
  25. What part of Hindley-Milner do you not understand?
  26. foldl Implementation with Runtime Errors
  27. Exception handling in Haskell
  28. Functional lenses
  29. How to reuse a type variable in an inner type declaration
  30. How does Haskell printf work?

Leave a Comment