Informatyka MIMUW

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)