Informatyka MIMUW

Zadanie 1. Monada List

Funkcja

allPairs :: [a] -> [a] -> [[a]]
allPairs xs ys = [[x,y] | x <- xs, y <- ys]

daje listę wszystkich list dwuelementowych, gdzie pierwszy element należy do pierwszego argumentu, drugi do drugiego, np.

*Main> allPairs [1,2,3] [4,5]
[[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]

• przepisz na notację monadyczną
• uogólnij te funkcję do allCombinations :: [[a]] -> [[a]], która dla n-elementowej listy list da listę wszystkich n-elementowych list takich, że i-ty element należy do i-tego elementu argumentu, np

  Main> allCombinations [[1,2], [4,5], [6], [7]]
  [[1,4,6,7],[1,5,6,7],[2,4,6,7],[2,5,6,7]]

Zadanie 2. Reader

a. data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Eq, Ord, Show)

Napisz funkcję

renumber :: Tree a -> Tree Int

która dla danego drzewa da drzewo, gdzie w każdym węźle przechowywana będzie głębokość tego węzła (odległość od korzenia).

Porównaj rozwiązania z użyciem monady Reader i bez.

b. Dane typy dla wyrażeń arytmetycznych

data Exp = IntE Int
     | OpE  Op Exp Exp
     | VarE String
     | LetE String Exp Exp  -- let var = e1 in e2
 
type Op = Int -> Int -> Int

Napisz funkcję

evalExp :: Exp -> Int

ktora obliczy wartość takiego wyrażenia, np

--
--      let x =
--          let y = 5 + 6
--          in y / 5
--      in x * 3
-- 
-- ==>  6
--
test = LetE "x" (LetE "y" (OpE (+) (IntE 5) (IntE 6))
          (OpE div y (IntE 5)))
        (OpE (*) x (IntE 3))
where x = VarE "x"
      y = VarE "y"

Zadanie 3

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Eq, Ord, Show)

Napisz funkcję

renumberTree :: Tree a -> Tree Int

która ponumeruje wezly drzewa tak, ze kazdy z nich bedzie mial inny numer. Porownaj rozwiazania z uzyciem monady State i bez.

możliwe dodatkowe wymaganie: ponumeruj wezly drzewa w kolejnosci infiksowej. (toList $ renumber $ fromList "Learn Haskell") == [0..12]

Zadanie 4. Transformatory monad

1. Zaimplementuj moduły StateTParser i SimpleParsers z wykładu
2. Zaimplementuj moduł IdentityTrans dostarczający identycznościowego transformatora IdentityT:

newtype IdentityT = ...
instance (Functor m) => Functor (IdentityT m) where
instance (Monad m) => Monad (IdentityT m) ...
instance MonadTrans IdentityT ...
instance MonadPlus m => MonadPlus (IdentityT m) ...

3. Zaimplementuj moduł MaybeTrans dostarczający transformatora MaybeT - analogicznie jak wyżej, za wyjatkiem

instance MonadPlus (MaybeT m) ...

4. Zaimplementuj moduł StateTParser2 z wykładu i przetestuj go z SimpleParsers (zastępując import StateTParser przez import StateTParser2)