Zadania (Haskell)

1. Jakie są wartości następujących wyrażeń?
   
   

   > 10 
   
   
   > 5 + 3 + 4 
   
   
   > 9 - 1  
   
   
   > 6 / 2 
   
   
   > 2 * 3 + 4 * 6 
   
   
   > let a = 3 in a + 1 
   
   
   > let a = 1 in let b = a + 1 in a + b + a * b 
   
   
   > let square n = n * n in square 4 
   
   
   > let fac n = if n == 0 then 1 else n * fac (n-1) in fac 5 
   
   
   
   

2. Proszę napisać funkcje smaller x y, greater x y, equal x y, smaller_equal x y, greater_equal x y oraz not_equal x y. Należy z wbudowanych funkcji używać wyłącznie funckcję < (oraz predykaty oczywiście).
   
   
3. Proszę napisać funkcję call_with_5 f, której wartość jest wartością funkcji f dla argumentu 5.

   Przykład: > call_with_5 square
             25
   

   Jaka jest wartość wyrażenia call_with_5 call_with_5?
   
   
4. Proszę napisać funkcję same_values p1 p2 x y, której wartość jest True, jeżeli p1(x,y) i p2(x,y) mają tą samą wartość i False w przecziwnym przypadku.

   Przykłady: > same_values plus times 2 3
              False
              > same_values plus times 2 2
              True
              > same_values equal not_equal 2 4
              False
   

5. Proszę napisać funkcje odd n oraz even n, które sprawdzają, czy liczba naturalna n jest nieparzysta względnie parzysta. Należy używać wyłącznie funkcje True, False, 0, 1 oraz "-1".
   
   
6. Proszę napisać funkcje nwd a b oraz nww a b, których wartościami są największy wspólny dzielnik i najmniejsza wspólna wielokrotność.
   
   
7. Proszę napisać funkcję kwad a b c, która obliczy miejsca zerowe równania kwadratowego ax^2 + bx + c dla danych a, b i c.
   
   
8. Proszę napisać rekurencyjną oraz iteracyną funkcję fib n, która obliczy n-tą liczbę Fibonacci.
   
   
9. Proszę napisać funkcję Hanoi n, która rozwiązuje problem Wieży Hanoi dla n krążków.
   
   
10. Proszę napisać funkcję Pascal n, której wartością jest n-ty wiersz trójkąta Pascala.
    
    
11. Potęgowanie b^e można szybko wykonać używając b^e = (b^(e/2))^2. Proszę napisać rekurencyjną oraz iteracyjną funkcję exp b e na podstawie tej właściwości.
    
    
12. Proszę napisać następujące funkcje dla list:
    
    a) append l m, która konkatenuje listy l i m.
    
    b) member x , która sprawdza, czy x jest lementem listy l
    
    c)reverse l, która przewraca listę l.
    
    d) last l, która znajduje ostatni element w liscie l.
    
    e) delete x l, która skasuje element x z listy l.
    
    
13. Proszę napisać funkcję my_map f l, której wartością jest lista wartości f(e) dla wszystkich elementów e w liscie l.
    
    
14. a) Proszę napisać funkcję permutation l, której wartością jest lista wszystkich permutacji elementów listy l.
    
    b) Proszę napisać funkcję PythagoreanTriple n, której wartością jest lista wartości (x,y,z) takie że x^2 + y^2 = z^2 oraz 1 <= x,y,z <= n.
    
    
15. Proszę napisać funkcję Iter n f dla jednoargomentowej funkcji f i liczby naturalnej x. Wartością funkcji jest funckją, która obliczy fⁿ.

    Przykłady: > iter 2 square 3
               81
               > let f = iter 2 square
               > f 5
               625
               > iter 0 square 7
               7 

16. Proszę zdefiniować funkcję filter pred l, której wartością jest lista wszystkich elementów listy l, które spełnią predykat pred.
    Jaki ma typ funkcja filter?
    
    
17. a) Proszę zdefiniować funkcję foldr analogicznie do funkcji foldl.
    
    b) Proszę zdefiniować funkcje length, and (dla listy wartości boole'owskich), sum, prod, map i reverse używając funkcje foldl i foldr.
    
    
18. a) Proszę zdefiniować funkcję map2 f l1 l2, która zastosuje dwuargumentową funkcję f do wszystkich elementów list l1 i l2.

       Przykład: > map2 (+) [1,2,3] [8,9,10]
                [9,11,13]
    

      Jaki ma typ funkcja map2?
    
    b) Proszę przy pomocy map2 (i innych kombinatorów) zrealizować produkt wektorowy.
    
    
19. Funkcja flatten :: [[a]] -> [a] transformuje listę list do zwykłej listy.

    Przykład: > flatten [[1,2,3], [8,9], [4,6]]
              [1,2,3,8,9,4,6]
    

    Proszę tą funkcję napisać raz "ręcznie" i raz używając funkcje fold z zadania 17.
    
    
20. a) Proszę zdefiniować funkcję insertionsort :: [a] -> [a].
    
    b) Proszę zdefiniować funkcję insertionsort :: (a -> a -> Bool) -> [a] -> [a].
    
    Proszę wykonywać a) i b) raz "ręcznie" i raz używając funkcje fold z zadania 17.
    
    
21. Proszę napisać funkcję dz, która realizuje schemat do rozwiązania problemów typu "dziel i zwyciężaj" (divide and conquer) na abstrakcyjnym pożomie. dz ma używać następujące argumenty:
    
    
    1. test, który sprawdza czy przypadek jest triwialny
    2. koniec, który rozwiązuje triwialny przypadek
    3. dziel, który dzieli problem do podproblemow
    4. połącz, który połączy rozwiązania podproblemów.
    
    Używając funkcję dz proszę zdefiniować funkcję mergesort oraz mnożenie według Karatsuby.
    
    
22. Proszę implementować arytmetykę liczb zespolonych
    
    a) używając metodę "mainfest types".
    
    b) używając metodę "message passing".
    
    
23. Jaki typ mają następują wyrażenia?
    
    a)   add
    b)   add 37
    c)   f 7
    d)   \f -> f 7
    e)   add (f x) (g x)
    f)   f 7 (g 'x')
    g)   \f -> f (g x)
    
    
24. Proszę obliczyć mgu dla następujących wyrażeń.
    
    a)   f(x,g(b))                         f(a,y)
    b)   f(h(x,b),y)                      f(h(a,y),x)
    c)   f(x,y)                              f(h(x,b),y)
    d)   g(x,h(x,y),h(y,h(x,y)))     g(x,y',h(z,y'))
    e)   g(x,h(x,y),h(y,h(x,y)))     g(x,y',h(y',z))
    f)   f(a,x,h(g(y)))                   f(z,h(z),h(z'))
    
    
25. Proszę obliczyczyć typ następujących wyrażeń.

    a) \x -> 2 * x
    b) \x -> x x
    c) \f -> f x
    d) append [] l     = l                        
       append (x:xs) l = x : (append xs l)   
    e) fun []     = 0
       fun (x:xs) = 1 + (fun x) + (fun xs)
    

26. a) Proszę napisać funkcję pozycja, która znajduje pozycję elementu x w liście l.
    
    b) Proszę napisać funkcję drop, która eliminuje pierwsze n elementy z listy l.
    
    Należy używać typ Maybe a.
    
    
27. Niech będzie dany następujący typ dla drzew binarnych.

     data BinTree a = Leaf a | Node (BinTree a) (BinTree a)
    

    Proszę napisać moduł BinTree z funkcjami
    
      a) heightBinTree, która obliczy głębokość drzewa.
    
      b) sizeBinTree, która obliczy ilość węzłów w drzewie.
    
      c) sumBinTree, która obliczy sumę elementów w drzewie.
    
      d) preBinTree, której wartością jest lista elementów drzewa w porząku prefiksowym.
    
    Należy do tego używać nadające się funkcje mapBinTree i foldBinTree.
    
    
28. Niech będzie dany następujący typ dla drzew ogólnych.

     data Tree a = Node a [Tree a]
    

    Proszę napisać moduł Tree z funkcjami
    
      a) sizeTree, która obliczy ilość węzłów w drzewie.
    
      b) sumTree, która obliczy sumę elementów w drzewie.
    
      c) postTree, której wartością jest lista elementów drzewa w porząku postfiksowym.
    
      d) inTree, której wartością jest lista elementów drzewa w porząku infiksowym.
    
    Należy do tego używać nadające się funkcje mapTree i foldTree.
    
    
29. Proszę napisać moduł Set z funkcjami member, subset, union, intersection oraz delete.
    
    
30. Proszę zdefiniować drzewa z zbiorami na węzłach przy pomocy modułów Tree i Set oraz funkcje
    
      a) deleteTree, która eliminuje dany element x z każdego zbioru w drzewa.
    
      b) unionTree, której wartością jest lista wszystkich elementów drzewa.
    
      c) allTree, która sprawdza, czy dany element x znajduje się w każdym zbiorze w drzewa.
    
    
31. Proszę zdefiniować typ drzew binarnych BinTree z zadania 27 jako instancję klas Show, Eq oraz Ord.
    
    
32. a) Proszę zdefiniować klasę Queue kolejek z zwykłami operacjami isEmptyQueue, enQueue, deqQueue oraz getFrontQueue.
        Proszę też zdefiniować funkcję showQueue razem z default-implementację.
    
    b) Proszę zdefiniować instancję klasy Queue używając konstruktory.
    
    c) Proszę zdefiniować instancję klasy Queue używając listy jako reprezentację kolejki.
    
    
33. Zostało już zdefiniowane parę funkcji map i fold dla list i różnych dzrew.
    Przy pomocy klasy typów proszę zastosować mechanism overloading do tych funkcji. Proszę też zdefiniować funkcje map i fold dla zbiorów z zadania 29.
    
    
34. Niech będzie dany λ-term N º λx. (λx. xy) (x (λx. λy. yzx)). Proszę obliczyć zbiór wolnych zmiennych termu N.
    
    
35. Proszę ewaluować następujące λ-termy.
    
    a) (λx. x) (xy)
    
    b) (λx. xy) (λx. xz)
    
    c) (λx. λy. xy) (xy)
    
    
36. a) Niech będą dane następujące λ-termy.
    
          true º λx. λy. x
    
          false º λx. λy. y
    
        Proszę znaleźć λ-termy not i xor realizujące operacje bool'owskie negację i xor.
    
    b) Niech będzie λf. λx. fⁿ x reprezentacją liczby naturalnej n.
        Proszę znaleźć λ-termy add i mult realizujące operacje dodawanie i mnożenie dwuch liczb naturalnych.
    
    
37. Niech będą dane λ-termy A º λx. λy. y(xxy) oraz Z º AA. Proszę pokazać, że ZF redukuje się do F(ZF).
    Czy to też prawda dla kombinatora punktu stałego Y?
    
    
38. Dla dowolnych funkcji g(x), f(x,y,z) i h(x,y) schematy rekursji prostej i minimalizacji są dane przez

    primRek(x,y) = g(x),                    jeżeli y = 0                 μh(x) = min{ i | h(x,i) = 0 }, jeżeli minimum to istnieje
    primRek(x,y) = f(x,y-1,primRek(x,y-1)), jeżeli y > 0                 μh(x)↑,                        w przeciwnym przypadku.
    

    Proszę napisać w Hakell'u funkcje (Rek g f) i (mu h), których wartości są funkcjami realizującymi te schematy.
    Użwając te schematy proszę zdefiniować dodawania i mnożenia.
    
    
39. Proszę pokazać, że wszystkie funkcje pierwotnie rekurencyjne można zdefiniować w λ-rachunku.