Here is the last part of the chapter 10's exercises. Previous part:
Abstract Machine
Extend the abstract machine to support the use of multiplication.
The code adapted to deal with multiplication:
data Expr = Val Int | Add Expr Expr | Mult Expr Expr deriving Show data Op = EVALM Expr | EVALA Expr | MUL Int | ADD Int deriving Show type Cont = [Op] eval :: Expr -> Cont -> Int eval (Val n) c = exec c n eval (Mult x y) c = eval x (EVALM y : c) eval (Add x y) c = eval x (EVALA y : c) exec :: Cont -> Int -> Int exec [] n = n exec (EVALM y : c) n = eval y (MUL n : c) exec (EVALA y : c) n = eval y (ADD n : c) exec (MUL m : c) n = exec c (n * m) exec (ADD m : c) n = exec c (n + m) val :: Expr -> Int val e = eval e []
Output:
*AbstractMachine> val (Mult (Val 10) (Val 5)) 50 *AbstractMachine> val (Add (Mult (Val 10) (Val 5)) (Val 100)) 150
Instance
Complete the following instance declarations: = instance Monad Maybe where ··· instance Monad [] where ··· = In this context, [] denotes the list type [a] without its parameter.
Hint: First write down the types of
returnand>>=for each instance.
May(be)
data
The data May(be) definition:
data May a = Noth | Jus a
inject
To inject a value into the Maybe world, we wrap this value into a Jus and we're done:
return = Jus
bind
- Noth binds to anything is Noth.
- And if it is a value (Jus x)m then we can bind it to the monadic function f (f x).
Noth >>= _ = Noth (Jus x) >>= f = f x
complete
Complete definition:
data May a = Noth | Jus a instance Monad May where return = Jus Noth >>= _ = Noth (Jus x) >>= f = f x
[]
inject
To inject a value in the monadic world of list, just create a singleton list with this value:
-- return :: a -> [a] return x = [x]
bind
To bind a list to the monadic function f, apply the monadic function f to the content of the list (so concatMap):
-- [a] -> (a -> [b]) -> [b] l >>= f = concatMap f l
complete
instance Monad [] where return v = [v] -- m a -> (a -> m b) -> m b -- [a] -> (a -> [b]) -> [b] l >>= f = concatMap f l