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 boolowskie 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ę <.

  3. 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
    jeżeli
     plus x y  = x + y
     times x y = x * y 
  4. 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".

  5. Proszę napisać funkcję gcd n m, której wartością jest największy spólny dzielnik dla (liczb naturalnych) n i m.

  6. Proszę napisać funkcję lcm n m, której wartością jest najmniejsza spólna wielokrotność dla n i m.

  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ć funkcję silnia n, która obliczy n! oraz funkcję fib n, która obliczy n-tego elementu ciągu Fibonacci'ego.
    Proszę podać dwie wersje tych funkcji: jedną rekurencyjną a jedną używając akumulator.

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

    f) split x l, która podzieli listę l do dwóch list l1 i l2. l1 zawiera elementy mniejsze niż x a l2 elementy większe niż x.

    Jakie są typy tych funkcji?

  10. Proszę zdefiniować funkcję insertionsort :: (a -> a -> Bool) -> [a] -> [a].

  11. 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ę zdefiniować funkcję pairing l1 l2, która zmienia dwuch list l1 i l2 do listy par.
      Przykład: > pairing [1,2,3] [a,b,c]
               [(1,a),(2,b),(3,c)] 
    c) Proszę przy pomocy map2 (i innych kombinatorów) zrealizować iloczyn skalarny.

  12. Proszę napisać funkcję filter p l, której wartością jest lista wszystkich elementów listy l, które spełnią predykat p. Jaki ma typ funkcja filter?

  13. Proszę zdefiniować funkcję foldr analogicznie do funkcji foldl. Jaki ma typ funkcja foldr?

  14. Używając funkcje foldl i foldr proszę zdefiniować funkcje

    a) prod

    b) length

    c) and (dla listy wartości boole'owskich)

    d) nwd (dla listy liczb naturalnych)

    e) delete

    f) map

    g) reverse

    h) filter pred l

    i) forall pred l .

  15. Proszę zdefiniować funkcję insertionsort :: (a -> a -> Bool) -> [a] -> [a] przy pomocy kombinatora.

  16. a) 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.

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

  17. 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 podproblemów
    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.

  18. Jaki typ mają następują wyrażenia?

    a)   +
    b)   + 37
    c)   append
    d)   append [1,2]
    e)   map
    f)   map square [1,2,3,4,5]
    g)   foldl
    h)   foldl (++)
    i)   foldl (++) []
    j)   f 7
    k)   \f -> f 7
    l)   + (f x) (g x)
    m)   f 7 (g 'x')
    n)   \f -> f (g x)
    o)   (\f -> f (g x)) square

  19. Proszę obliczyć najbardziej ogólny unifikator 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'))

  20. Proszę obliczyć typ następujących wyrażeń.
    a) map square [1,2,3]
    b) map square ['a','b','c']
    c) \x -> 2 * x
    d) \f -> f 3
    e) \f x -> f (f x)
    f) (\f x -> f (f x)) square
    g) \x -> x x
    h) f 7 (g 'a')
    
    Można używać map :: (a -> b) -> [a] -> [b] oraz square :: Int -> Int.

  21. Proszę obliczyć typ następujących funkcji.
    a) map f []     = []
       map f (x:xs) = (f x) : (map f xs)
    
    b) append []     l = l
       append (x:xs) l = x : (append xs l)
    
    c) sum f []     = 0
       sum f (x:xs) = (f x) + (f xs)
    
    d) member x []     = False
       member x (y:ys) = (x == y) || (member x ys)
    
  22. Niech będzie dana następująca definicja.
    sum f l1 l2 = (f l1) + (f l2)
    
    Dlaczego wyrażenie sum length [1,2] ['a','b'] jest błędne? Proszę poprawić definicję funkcji sum tak, aby wyrażenie sum length [1,2] ['a','b'] było poprawnie.

  23. a) Proszę napisać funkcję pozycja, która znajduje pozycję elementu x w liście l. Należy używać typ Maybe a.

    b) Proszę napisać funkcję drop, która eliminuje pierwsze n elementy z listy l. Należy używać typ Maybe a.

    c) Proszę napisać funkcję sum, która sumuje elementy listy typu [Maybe Int] używać odpowiedniege operatora +.

  24. Niech będzie dany następujący typ dla drzew binarnych.
     data BinTree a = Leaf a | Node (BinTree a) (BinTree a)
    Proszę napisać następujące funkcje

      a) heightBinTree, która obliczy głębokość drzewa.

      b) sizeBinTree, która obliczy ilość węzłów w drzewie.

      c) maxBinTree, która obliczy największy element w drzewie.

      d) preBinTree, której wartością jest lista elementów drzewa w porządku prefiksowym.

    Proszę także zrealizować funkcje te używać nadające się funkcje mapBinTree i foldBinTree.

  25. Niech będzie dany następujący typ dla drzew ogólnych.
     data Tree a = Node a [Tree a]
    
    Proszę napisać następujące funkcje

      a) sizeTree, która obliczy ilość węzłów w drzewie.

      b) sumTree, która obliczy sumę elementów w drzewie.

      c) preTree, której wartością jest lista elementów drzewa w porząku prefiksowym.

    Proszę także zrealizować funkcje te używać nadające się funkcje mapTree i foldTree.

  26. Proszę napisać typ Set z funkcjami member, subset, union, intersection oraz delete.

  27. Proszę zdefiniować drzewa z zbiorami na węzłach przy pomocy typów Tree i Set oraz funkcje

      a) allTree, która sprawdza, czy dany element x znajduje się w każdym zbiorze w drzewa.

      b) deleteTree, która eliminuje dany element x z każdego zbioru w drzewa.

      c) unionTree, której wartością jest lista wszystkich elementów drzewa.

  28. Niech będzie dany następujący typ danych dla wyrażeń boolowskich.
     data BoolExpr = Value Bool
                   | And BoolExpr BoolExpr
                   | Not BoolExpr
    
    a) Jak zostaje reprezentowane wyrażenie (¬ False ∧ True) ∧ True ?

    b) Proszę napisać funkcję eval :: BoolExpr -> Bool, która ewaluuje wyrażenie BoolExpr.

    c) Proszę napisać funkcję foldBoolExpr, która kompresuje wyrażenia boolowskie. Jaki ma typ funkcja foldBoolExpr?

    d) Proszę zdefiniować funkcję eval używając foldBoolExpr.

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

  30. a) Proszę zdefiniować klasę Stack opisującą stosy.

    b) Proszę zdefiniować instancję klasy Stack używając konstruktory.

    c) Proszę zdefiniować instancję klasy Stack używając listy jako reprezentację stosu.

  31. Zostało już zdefiniowane parę funkcji map dla list i różnych dzrew.
    Przy pomocy klasy typów proszę zastosować mechanism overloading do tych funkcji. Proszę też zdefiniować funkcje map dla zbiorów z zadania 26.

  32. Niech będzie dany λ-term N λx. (λx. xy) (x (λx. λy. yzx)). Proszę obliczyć zbiór wolnych zmiennych termu N.

  33. Proszę ewaluować następujące λ-termy.

    a) (λx. x) (xy)

    b) (λx. xy) (λx. xz)

    c) (λx. λy. xy) (xy)

    d) (λx. (λf. f (f x)) (λx. x * x + 1)) 2

  34. 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ę pokazać, że λ-termy λn. λf. λx. n f (f x) i λm. λn. λf. λx. m f (n f x) realizują funkcje s i +.
        Jaką operację realizuje λ-term λn. n (λn. False) True?

  35. 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 generatora punktu stałego Y z wykładu?

  36. Dla danych 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                 μ(x) = min{ i | h(x,i) = 0 ∧ ∀ k < i: h(x,k)↓}, jeżeli minimum to istnieje
    primRek(x,y) = f(x,y-1,primRek(x,y-1)), jeżeli y > 0                 μ(x) = ↑                                       , w przeciwnym przypadku.
    
    Proszę napisać w Hakell'u funkcje (PrimRek 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.