CS计算机代考程序代写 \begin{code}

\begin{code}
{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE KindSignatures #-}
module Mar02 where

\end{code}

Learning objectives:
\begin{itemize}
\item Monad, Applicative
\iterm parsing
\end{itemize}

What about (>>) and fail ?

Q: is (->) a Monad? A: No, but (e ->) is, i.e. Reader. ((->) a) b

\begin{code}
(>>) :: Monad m => m a -> m b -> m b
m >> f = m >>= \ _ -> f

fail :: Monad m => String -> m a
fail s = error s

fmap’ :: Monad m => (a -> b) -> m a -> m b
fmap’ f c = c >>= \x -> return $ f x
\end{code}

\begin{spec}
class Functor f => Applicative (f :: * -> *) where
pure :: a -> f a — is basically return
(<*>) :: f (a -> b) -> f a -> f b
\end{spec}
<*> is kind of sequencing, where order doesn’t matter.

Also useful: <\$> which is an alias for fmap

Parsing! As a list of successful parses
\begin{code}
type Parse a b = [a] -> [(b, [a])]
\end{code}

You won’t be surprised that this is a Monad…

First, some basic parsers:
\begin{code}
none :: Parse a b
none _ = []

succeed :: b -> Parse a b
succeed x inp = [(x, inp)]

token :: Eq a => a -> Parse a a
token _ [] = []
token a (x : xs)
| a == x = [(x, xs)]
| otherwise = []

spot :: (a -> Bool) -> Parse a a
spot _ [] = []
spot p (x : xs)
| p x = [(x, xs)]
| otherwise = []

token’ :: Eq a => a -> Parse a a
token’ x = spot (== x)

newtype MP a b = MP { mp :: Parse a b }

instance Functor (MP c) where
fmap f (MP p) = MP $ \s -> map (\(x, y) -> (f x, y)) (p s)

instance Applicative (MP a) where
instance Monad (MP a) where
\end{code}