## 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 **

**(>>=) **