Laboratorium 2

Zadanie 1

Ćwiczymy funkcje wyzszego rzedu

1. Napisz funkcje
   

   incAll :: [[Int]] -> [[Int]]

   która zwiększy o 1 każdy element każdego elementu swojego argumentu, np

   *Main Data.List> incAll $ inits [1..3]
   [[],[2],[2,3],[2,3,4]]

2. Napisz przy pomocy foldl/foldr
   1. silnie
   2. concat :: [[a]] -> [a]
3. Napisz nub przy pomocy filter

Zadanie 2

Rozważmy typ drzew troche inny niz na wykladzie

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

1. skonstruuj instancje klasy Functor:
   

   -- class  Functor f  where
   --    fmap :: (a -> b) -> f a -> f b
    
   instance Functor Tree where...
    
   *Tree> fmap (+1) $ Node 1 Empty Empty
   Node 2 Empty Empty

2. Napisz funkcje
   

   toList :: Tree a -> [a]

   ktora zamieni drzewo w liste elementow drzewa (w porzadku infiksowym)

3. zaimplementuj drzewa BST z funkcjami
   

   insert :: (Ord a) => a -> Tree a -> Tree a
   contains :: (Ord a) -> a -> Tree a -> Bool
   fromList :: (Ord a) => [a] -> Tree a

4. Stwórz modul drzew BST i wykorzystaj go w innym module do sortowania [Int]
   1. przy pomocy ghci
   2. przy pomocy ghc --make

Zadanie 3

1. Uzupełnij instancje klasy Functor dla Either e:
   

   instance Functor (Either e) where
     -- fmap :: (a -> b) -> Either e a -> Either e b

2. napisz funkcje
   

   reverseRight :: Either e [a] -> Either e [a]

   odwracajaca liste zawarta w Right
   (dwie wersje, bezposrednio i z uzyciem fmap)

3. Zdefiniuj klasę Pointed (funkcyjnych pojemników z singletonem)
   

   class Functor f => Pointed f where
     pure :: a -> f a

   i jej instancje dla list, Maybe, Tree

Zadanie 4.

Importy i moduły biblioteczne, np. przecwiczyć http://learnyouahaskell.com/modules

1. Napisz funkcję
   

   readInts :: String -> [Int]

   która odczyta z napisu występujące w nim liczby naturalne, np

   *Main> readInts "1 23 456 7.8 abc 9"
   [1,23,456,9]
   *Main> readInts "foo"
   []

   użyj funkcji isDigit z modulu Data.Char oraz funkcji map, filter, all z Prelude

2. Napisz podobną funkcję readInts2 :: String -> Either String [Int] która da listę liczb, jeśli wszystkie slowa jej argumentu są liczbami a komunikat o błędzie w przeciwnym przypadku

   Może sie przydać funkcja reverseRight z zad. 3b (lub fmap dla Either)

   *Main> readInts2  "1 23 456 foo 9"
   Left "Not a number: foo"
   *Main> readInts2  "1 23 456"     
   Right [1,23,456]

3. Napisz funkcję
   

   sumInts :: String -> String

   1. jesli wszystkie slowa jej argumentu są liczbami da reprezentacje ich sumy
   2. wpp komunikat o bledzie

   stwórz program uruchamiający funkcję sumInts przy pomocy interact.

Zadanie 5

Rozważmy typ dla wyrażeń arytmetycznych z let:

data Exp = IntE Int            -- stała całkowita
        | OpE  Op Exp Exp      -- operacja, np e1 + e2
        | VarE String          -- zmienna
        | LetE String Exp Exp  -- let var = e1 in e2
 
type Op = (Int -> Int -> Int, String) -- (działanie, nazwa)

1. Napisz instancje Eq oraz Show dla Exp
2. Napisz instancje Num dla Exp tak, żeby można było napisać
   

   testExp2 :: Exp
   testExp2 = (2 + 2) * 3

   (metody abs i signum mogą mieć wartość undefined)

Laboratorium 3

Zadanie 1

W poprzednim tygodniu pisaliśmy funkcje

readInts2 :: String -> Either String [Int]
sumInts :: String -> String

Przepisz funkcje readInts2, sumInts na notację monadyczną

(Uwaga: w tym zadaniu raczej nadal tworzymy funkcje String -> String i korzystamy z interact niz bezposrednio z IO, chyba ze ktos bardzo chce)

Zadanie 2 - IO

1. Napisz program który wypisze swoje argumenty, każdy w osobnej linii
2. Napisz program, który będzie pytał użytkownika o ulubiony język programowania, tak długo aż odpowiedzią będzie 'Haskell' ;)
3. Napisz uproszczoną wersję programu wc (wypisującą ilość linii, słów i znaków w pliku o nazwie podanej jako argument)

Zadanie 3.

Uzupełnić przykład z wykładu:

data ParseError = Err {location::Int, reason::String}
instance Error ParseError ...
type ParseMonad = Either ParseError
parseHexDigit :: Char -> Int -> ParseMonad Integer
parseHex :: String -> ParseMonad Integer
toString :: Integer ->; ParseMonad String
 
-- convert zamienia napis z liczba szesnastkowa 
--   na napis z liczba dziesietna
convert :: String -> String
convert s = str where
 (Right str) = tryParse s `catchError` printError
 tryParse s = do {n <- parseHex s; toString n}
 printError e = ...

Zadanie 4. Operacje monadyczne

Napisz własną implementację funkcji

sequence :: Monad m => [m a] -> m [a] 
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
forM :: Monad m => [a] -> (a -> m b) -> m [b]

Zadanie 5. (opcjonalne)

Nieco inny od monad model obliczeń reprezentuje klasa Applicative:

class Functor f => Applicative f where
  pure :: a -> f a
  (>*>) :: f(a->b) -> f a -> f b

1. pure to to samo co return
2. Operator (<*>) reprezentuje sekwencjonowanie obliczeń podobne do (=<<)
   z tym, że kolejne obliczenie nie zależy od wyniku poprzedniego (choć jego wynik oczywiście może).
3. Dla każdej monady można zdefiniować instancję Applicative:
   

   pure = return
   mf <*> ma =  do { f <- mf; a <- ma; return mf ma }

1. Zdefiniuj instancje Applicative dla Maybe i Either
2. Zdefiniuj operację *> będącą analogiem >> (czyli ignorującą wynik pierwszego obliczenia):

(*>) :: f a -> f b -> f b

3. Zdefiniuj analogiczną operację ignorującą wynik drugiego obliczenia:

(<*) :: f a -> f b -> f a

4. Spróbuj wykonać zadanie 3 używając Applicative zamiast Monad

Laboratorium 4

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)

Laboratorium 5

Zadanie 1

Dana składnia abstrakcyjna wyrażeń arytmetycznych (jak w 3. tygodniu)

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

a. zaprojektuj składnię konkretną
Sugestie: standardowa notacja infiksowa oraz notacja prefiksowa a la Lisp: (* (+ 1 2) 3)

b. napisz parser dla tej składni przy uzyciu Text.ParserCombinators.Parsec

UWAGA: Ze względów wydajnościowych, operator (<|>) z biblioteki Parsec jest prawie deterministyczny i nie będzie działać dobrze dla produkcji, które mają wspólny (niepusty) prefiks.

Możemy odzyskać niedeterminizm przy pomocy kombinatora try, np.

try p<|> q

Zadanie 2

Napisz własne wersje kombinatorów parsujących użytych w poprzednim zadaniu

Sugestie:

newtype Parser a = Parser { runParser :: String -> [(a,String)] }
newtype Parser a = Parser { 
  runParser :: String -> [Either ErrorMessage (a,String)] 
}

albo, używając transformatorów monad

type Parser a = StateT [Char] (ErrorT String []) a

Laboratorium 6

Zadanie 1.

1. Napisz lekser dla składni konkretnej wyrażeń zaprojektowanej w poprzednim tygodniu.
2. Zmodyfikuj swoj parser tak by działał na poziomie leksemów, a nie pojedynczych znaków.
3. Rozszerz lekser i parser o literały dla liczb zmiennoprzecinkowych (wystarczy format 123.456, ale dla bardziej ambitnych także 1.2e-3)

Zadanie 2

Napisz parser dla składni konkretnej wyrażeń zaprojektowanej w poprzednim tygodniu przy uzyciu BNFC (lub, jeśli ktoś bardzo chce, innego generatora parserów).

Składnia abstrakcyjna może być nieco inna (np. BNFC w pewnym sensie narzuca składnię abstrakcyjną).