parser.hs

import Control.Applicative
import Control.Monad

newtype Parser a = Parser (String -> [(String, a)])

run :: Parser a -> String -> [(String, a)]
run (Parser pf) = pf

instance Functor Parser where
  fmap f (Parser pf) = Parser $ \s -> fmap (fmap f) (pf s)
  -- Identity
  -- fmap id = id
  -- Composition
  -- fmap f . fmap g = fmap (f . g)

instance Applicative Parser where
  pure x = Parser $ \s -> [(s, x)]
  (Parser a2b_pf) <*> ap = Parser $ \s -> a2b_pf s >>= (\(rest, a2b) -> run (fmap a2b ap) rest)
  -- Identity
  -- pure id <*> v = v
  -- Homomorphism
  -- pure f <*> pure x = pure (f x)
  -- Interchange
  -- u <*> pure y = pure ($ y) <*> u
  -- Composition
  -- pure . <*> u <*> v <*> w = u <*> (v <*> w)

instance Monad Parser where
  return = pure
  (Parser apf) >>= a2_bpf = Parser $ \s -> apf s >>= (\(rest, a) -> run (a2_bpf a) rest)
  -- Left identity
  -- return a >>= f = f a
  -- Right identity
  -- m >>= return = m
  -- Associativity
  -- (m >>= f) >>= g = m >>= (\x -> f x >>= g)