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. Używając reprezentacji (a,b) dla liczby wymiernej a/b proszę zdefiniować dodawanie, odejmowanie, mnożenie i dzielenie dla liczb wymiernych.

  8. 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.

  9. Proszę napisać funkcję Pascal n, której wartością jest n-ty wiersz trójkąta Pascala.

  10. Proszę napisać funkcję Hanoi n, która rozwiązuje problem Wieży Hanoi dla n krążków.

  11. Proszę napisać rekurencyjną oraz iteracyną funkcję fib n, która obliczy n-tą liczbę Fibonacci.

  12. 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.

  13. Proszę napisać następujące funkcje dla list:

    a) append l m, która konkatenuje listy l i m.

    b) member x l, która sprawdza, czy x jeste elementem 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.

  14. 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.

  15. Proszę napisać funkcję permutation l, której wartością jest lista wszystkich permutacji elementów listy l.

  16. Proszę implementować arytmetykę liczb zespolonych

    a) używając metodę "mainfest types".

    b) używając metodę "message passing".

  17. Proszę napisać funkcję product term a next b analogicznie do funkcji sum z wykładu. Proszę pokazywać, jak używając product można definiować funkcję silnia oraz przybliżać p na podstawie formuły   p/4 = 2 · 4 · 4 · 6 · 6 · 8 ··· / 3 · 3 · 5 · 5 · 7 · 7 ··· .

  18. Proszę napisać funkcję accumulate combiner null-value term a next b, która jest uogólnieniem funkcji sum i prod. Argumenty term, next, a i b zachowują to same znaczenie niż w funkcjach sum i prod. combiner jest dwuargumentową funkcją, która opisuje, jak term a zostaje dodane do akkumulacji dalszych termów. null-value jest wartością inicjalną do używania w końcowym przypadku.
    Proszę pokazywać, jak można definiować funkcje sum i prod używając accumulate. Proszę też napisać iteracyjną wersję funkcji accumulate.

  19. Nawet funkcję accumulate można dalej uogólnić. Proszę napisać funkcję filter_accumulate, która ma dodatkowy argument pred. pred jest (jednoargumentowym) predykatem a filter_accumulate dodaje term a do wynika tylko, jeżeli a spełnie predykat pred.
    Używając filter_accumulate proszę obliczyć sumę kwadratów liczb pierwszych w interwale [a,b] oraz produkt wszystkich liczb naturalnych i mniejsze niż n, takie że nwd(i,n) = 1.

  20. W Haskell już zdefiniowane są funkcje foldl i foldr przez
    foldl f e []     = e                          foldr f e []     = e
    foldl f e (x:xs) = foldl f (f e x) xs         foldr f e (x:xs) = f x (foldr f e xs)
    
    Proszę zdefiniować funkcje length, and (dla listy wartości boole'owskich), sum, prod, map i reverse używając funkcje foldl i foldr.

  21. 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 20.

  22. 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 20.

  23. 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.

    Proszę zdefiniować funkcje quicksort i mergesort używając funkcję dz.

  24. Niech będą dane następujące wyrażenia.

    a)   f 7
    b)   f 7 (g 'x')
    c)   f (g x)
    d)   add (f x) (g x)

    Proszę obliczyć typy tych wyrażeń używając inferencję typów.

  25. Niech będą dane następujące definicje.
     a) append [] l     = l                         b) fun []     = []
        append (x:xs) l = x : (append xs l)            fun (x:xs) = 1 + (fun x) + (fun xs)
    
    Proszę obliczyć typy tych funkcji używając inferencję typów.

  26. Pary i ich selektory można zdefiniować bez konstruktorów:
     mkPair a b sel = sel a b
     first p        = p (\x y -> x)
     second p       = p (\x y -> y) 
    
    Niech też będzie dana następująca funkcja.
     pairId p = mkPair (first p) (second p)
    
    Proszę obliczyć typ funkcji pairId używając inferencję typów. Można używać następujące założenia.
     first  :: ((a1 -> b1 -> a1) -> c1) -> c1
     second :: ((a2 -> b2 -> b2) -> c2) -> c2
     mkPair :: a3 -> b3 -> (a3 -> b3 -> c3) -> c3
    
    Dodoatkowo proszę pokazać, że first :: ((a1 -> b1 -> a1) -> c1) -> c1.

  27. 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.

  28. 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) postBinTree, której wartością jest lista elementów drzewa w porząku postfiksowym.

    Należy do tego używać nadające się funkcje mapBinTree i foldBinTree.

  29. 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.

  30. Proszę napisać moduł Set z funkcjami member, subset, union, intersection oraz delete.

  31. 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.

  32. Proszę zdefiniować typ drzew binarnych BinTree z zadania 28 jako instancję klas Show, Eq oraz Ord.

  33. 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.

  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. Zadanie to zajmuje się implementacją ewaluacji λ-termów w Haskell'u.

    a) Proszę zdefiniować typ reprezentujący λ-termy.

    b) Proszę zdefiniować funkcję subst, która realizuje substytucję M[x/N]. Można założyć, ż nie ma wolnych zmiennych.

    c) Proszę zdefiniować funkcję ewal, która ewaluuje λ-termy.

  37. 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. fn x reprezentacją liczby naturalnej n.
        Proszę znaleźć λ-termy add i mult realizujące operacje dodawanie i mnożenie dwuch liczb naturalnych.

  38. 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?

  39. 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,Rek(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.

  40. Proszę pokazać, że wszystkie funkcje pierwotnie rekurencyjne można zdefiniować w λ-rachunku.