Description
The goal of this homework is to better understand the state monad.
https://hackage.haskell.org/package/mtl-2.2.1/docs/Control-Monad-State-Lazy.html
The goal is to solve the same problem with and without using
the state monad.
You are given an arbitrary tree (Tree a) and you have to transform it
into a tree of integers (Tree Int) in which the original values stored
in the nodes are replaced by integers, starting from 0. The same value has to be
replaced by the same number at every occurrence.
For instance,
getLabeledTree Nil ~~> Nil
getLabeledTree (Node “Haskell” Nil Nil) ~~> Node 0 Nil Nil
getLabeledTree (Node “Haskell” (Node “is” Nil Nil) (Node “fun” Nil Nil)) ~~>
Node 0 (Node 1 Nil Nil) (Node 2 Nil Nil)
getLabeledTree (Node ‘a’ (Node ‘a’ Nil Nil) (Node ‘b’ (Node ‘a’ Nil Nil) (Node ‘d’ Nil Nil))) ~~>
Node 0 (Node 0 Nil Nil) (Node 1 (Node 0 Nil Nil) (Node 2 Nil Nil))
To solve this problem, it is helpful to use the functions get and put.
Problem 1:
———-
Implement the function
labelValue :: Ord a => a -> (Store a Int) -> (Int, Store a Int)
in TreeLabelWithoutStateMonad.hs
Problem 2:
———-
Implement the function
labelValue :: Ord a => Tree a -> State (Store a Int) (Tree Int)
in TreeLabelWithStateMonad.hs
Problem 3:
———-
a) Give 5 examples of Haskell classes (for instance, Eq).
b) Give the signature of the functions (>>=) and return in the class definition of a monad.
c) Give the kind of the type constructor Either and of the partially applied type constructor Either Int.
d) Give the type of the functions zip and the partially applied function zip “abc”.
e) Give a definition of a higher-order function?
f) What does it mean that a data structure is persistent?
g) Assume that ErrorType is some user defined type that describes errors that can occur in computations.
How would you endow Either ErrorType with a monadic structure? Give the definition of return and (>>=).
instance Monad Either ErrorType where
return
(>>=)
