module L3.Parse.Parser where

import Control.Applicative (Alternative (empty, (<|>)))
import Control.Monad (MonadPlus (..))

newtype Parser i o = Parser {Parser i o -> i -> [(o, i)]
parse :: i -> [(o, i)]}

bind :: Parser i o -> (o -> Parser i o') -> Parser i o'
bind :: Parser i o -> (o -> Parser i o') -> Parser i o'
bind Parser i o
p o -> Parser i o'
f = (i -> [(o', i)]) -> Parser i o'
forall i o. (i -> [(o, i)]) -> Parser i o
Parser ((i -> [(o', i)]) -> Parser i o')
-> (i -> [(o', i)]) -> Parser i o'
forall a b. (a -> b) -> a -> b
$ \i
s -> ((o, i) -> [(o', i)]) -> [(o, i)] -> [(o', i)]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (\(o
a, i
s') -> Parser i o' -> i -> [(o', i)]
forall i o. Parser i o -> i -> [(o, i)]
parse (o -> Parser i o'
f o
a) i
s') ([(o, i)] -> [(o', i)]) -> [(o, i)] -> [(o', i)]
forall a b. (a -> b) -> a -> b
$ Parser i o -> i -> [(o, i)]
forall i o. Parser i o -> i -> [(o, i)]
parse Parser i o
p i
s

unit :: o -> Parser i o
unit :: o -> Parser i o
unit o
a = (i -> [(o, i)]) -> Parser i o
forall i o. (i -> [(o, i)]) -> Parser i o
Parser (\i
s -> [(o
a, i
s)])

combine :: Parser i o -> Parser i o -> Parser i o
combine :: Parser i o -> Parser i o -> Parser i o
combine Parser i o
p Parser i o
q = (i -> [(o, i)]) -> Parser i o
forall i o. (i -> [(o, i)]) -> Parser i o
Parser (\i
s -> Parser i o -> i -> [(o, i)]
forall i o. Parser i o -> i -> [(o, i)]
parse Parser i o
p i
s [(o, i)] -> [(o, i)] -> [(o, i)]
forall a. [a] -> [a] -> [a]
++ Parser i o -> i -> [(o, i)]
forall i o. Parser i o -> i -> [(o, i)]
parse Parser i o
q i
s)

failure :: Parser i o
failure :: Parser i o
failure = (i -> [(o, i)]) -> Parser i o
forall i o. (i -> [(o, i)]) -> Parser i o
Parser ([(o, i)] -> i -> [(o, i)]
forall a b. a -> b -> a
const [])

option :: Parser i o -> Parser i o -> Parser i o
option :: Parser i o -> Parser i o -> Parser i o
option Parser i o
p Parser i o
q = (i -> [(o, i)]) -> Parser i o
forall i o. (i -> [(o, i)]) -> Parser i o
Parser ((i -> [(o, i)]) -> Parser i o) -> (i -> [(o, i)]) -> Parser i o
forall a b. (a -> b) -> a -> b
$ \i
s ->
  case Parser i o -> i -> [(o, i)]
forall i o. Parser i o -> i -> [(o, i)]
parse Parser i o
p i
s of
    [] -> Parser i o -> i -> [(o, i)]
forall i o. Parser i o -> i -> [(o, i)]
parse Parser i o
q i
s
    [(o, i)]
res -> [(o, i)]
res

instance Functor (Parser i) where
  fmap :: (a -> b) -> Parser i a -> Parser i b
fmap a -> b
f (Parser i -> [(a, i)]
cs) = (i -> [(b, i)]) -> Parser i b
forall i o. (i -> [(o, i)]) -> Parser i o
Parser (\i
s -> [(a -> b
f a
a, i
b) | (a
a, i
b) <- i -> [(a, i)]
cs i
s])

instance Applicative (Parser i) where
  pure :: a -> Parser i a
pure = a -> Parser i a
forall o i. o -> Parser i o
unit
  (Parser i -> [(a -> b, i)]
left) <*> :: Parser i (a -> b) -> Parser i a -> Parser i b
<*> (Parser i -> [(a, i)]
right) = (i -> [(b, i)]) -> Parser i b
forall i o. (i -> [(o, i)]) -> Parser i o
Parser (\i
s -> [(a -> b
f a
a, i
s2) | (a -> b
f, i
s1) <- i -> [(a -> b, i)]
left i
s, (a
a, i
s2) <- i -> [(a, i)]
right i
s1])

instance Monad (Parser i) where
  >>= :: Parser i a -> (a -> Parser i b) -> Parser i b
(>>=) = Parser i a -> (a -> Parser i b) -> Parser i b
forall i a b. Parser i a -> (a -> Parser i b) -> Parser i b
bind

instance MonadPlus (Parser i) where
  mzero :: Parser i a
mzero = Parser i a
forall i a. Parser i a
failure
  mplus :: Parser i a -> Parser i a -> Parser i a
mplus = Parser i a -> Parser i a -> Parser i a
forall i a. Parser i a -> Parser i a -> Parser i a
combine

instance Alternative (Parser i) where
  empty :: Parser i a
empty = Parser i a
forall (m :: * -> *) a. MonadPlus m => m a
mzero
  <|> :: Parser i a -> Parser i a -> Parser i a
(<|>) = Parser i a -> Parser i a -> Parser i a
forall i a. Parser i a -> Parser i a -> Parser i a
option