workSheet4.lhs

> import Text.Yoda
> import Data.Char

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

- parse (word ⟨∼⟩ number ) "hello234 parser" = [("hello", 234), " parser"]
- parse (word ⟨∼⟩ number ) "hello 123" = []
- parse (word ∗⟩ number ) "Dog14a" = [14, "a"]
- ((++) ⟨$⟩ word ⟨∗⟩ pure " world") "hello parser" = ["hello world", " parser"]
- (42 ⟨$ word) "hello world" = [42, " world"]

- Given the parser digits :: Parser String which reads one or more digits from the input stream, define
the number :: Parser Int parser using digits and (⟨$⟩).
read :: Read a => String -> a to convert string to Int
digits s = [String, String]

- parse (word ⟨|⟩ string "abc" ⟨|⟩ pure "7") "abcd" = [("abcd", ""), ("abc", "d"), ("7", "abcd")]
- parse (number ⟨+⟩ word) "hello123" = [(Right "hello", "123")]

- Mov 10 (Rt (Lt (Stop)))

> data Robot = Mov Int Robot
>            | Rt Robot
>            | Lt Robot
>            | Stop

> digits :: Parser String
> digits = cull (some (oneOf ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']))

- robot ::= "f" [" "] number ", " robot
            | "r, " robot
            | "l, " robot
            | "stop."

- robot ::= ("f" [" "] number | "r" | "l") ", " robot
            | "stop."

> number :: Parser Int
> number = read <$> digits

robot :: Parser Robot
robot = Mov ⟨$ char 'f' ⟨∗ optional (char ' ') ⟨∗⟩ number ⟨∗ string ", " ⟨∗⟩ robot
⟨|⟩ Rt ⟨$ string "r, " ⟨∗⟩ robot
⟨|⟩ Lt ⟨$ string "l, " ⟨∗⟩ robot
⟨|⟩ Stop ⟨$ string "stop."

> robot' :: Parser Robot
> robot' = (Mov <$ char 'f' <* optional (char ' ') <*> number
>         <|> Rt <$ string "r"
>         <|> Lt <$ string "l") <* string ", " <*> robot'
>         <|> Stop <$ string "stop."

- BranFlakes ::= "+" BranFlakes
               | "-" BranFlakes
               | ">" BranFlakes
               | "<" BranFlakes
               | "[" BranFlakes "]" BranFlakes

> data Bran = Inc Bran
>           | Dec Bran
>           | Rgt Bran
>           | Lft Bran
>           | Par Bran Bran
>           | Halt
>   deriving Show

> branflakes :: Parser Bran
> branflakes = pure Halt
>             <|> Rgt <$ char '>' <*> branflakes
>             <|> Lft <$ char '<' <*> branflakes
>             <|> Inc <$ char '+' <*> branflakes
>             <|> Dec <$ char '-' <*> branflakes
>             <|> Par <$ char '[' <*> branflakes <* char ']' <*> branflakes
>             <|> noneOf "><+-[]" *> branflakes

Abstract Compbinators ----------------------------------------------------------

Write a combinator between::Parser o → Parser c → Parser a → Parser a such that between open close p
attempts to parse open, then p, then finally close returning the result provided by p.

between :: Parser o -> Parser c -> Parser a -> Parser a
between open close p = open *> p <* close

Write a combinator choice :: [Parser a] → Parser a which succeeds if any parser in the given list
succeeds and returns all the successful results.

choice :: [Parser a] -> Parser a
choice = foldr (<|>) empty

Write a combinator oneOf :: [Char ] → Parser Char which succeeds if it reads any of the characters
found in the provided list.

oneOf :: [Char] -> Parser Char
oneOf = satisfy . flip elem

px ⟨∗∗⟩ pf first performs px, then pf, then applies the function from pf to the value from px .

(<**>) :: Parser a → Parser (a → b) → Parser b
px <**> pf = Parser (\ ts -> [(f x, ts'')
                    | (x, ts') <- px ts
                    | (f, ts'') <- pf ts')
or

px <**> pf = flip ($) <$> px <∗> pf

px ⟨:⟩ pxs parses px and adds its result onto the front of the list generated by parsing pxs

(<:>) :: Parser a -> Parser [a] -> Parser [a]
px <:> pxs =  (:) <$> px <*> pxs

sequence takes a list of parsers and executes them in sequence, combining all their results into a list.

> sequence' :: [Parser a ] -> Parser [a]
> sequence' []       = empty
> sequence' (px:pxs) = px <:> sequence' pxs

> traverse' :: (a -> Parser b) -> [a] -> Parser [b]
> traverse' f = sequence . map f

reads a given string from the input stream and returns that same string

> string' :: String → Parser String
> string' = traverse char

(⟨∼⟩) in terms of (⟨$⟩) and (⟨∗⟩)

> (<~>) :: Parser a -> Parser b -> Parser (a, b)
> pa <~> pb = (,) <$> pa <*> pb

(⟨∗⟩) in terms of (⟨$⟩) and (⟨∼⟩).

> (<*>) :: Parser (a -> b) -> Parser a -> Parser b
> pf <*> pa = uncurry ($) <$> pf <~> pa