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 p₁ p₂ x y, której wartość jest True, jeżeli p₁(x,y) i p₂(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ę 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.
   
   
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ć 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. 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?
    
    
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) length
    
    b) and (dla listy wartości boole'owskich)
    
    c) prod
    
    d) nwd (dla listy liczb naturalnych)
    
    e) delete
    
    f) map
    
    g) reverse
    
    h) filter pred l
    
    i) forall pred l .
    
    Proszę też podać typy zdefiniowanych funkcji.
    
    
15. 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 podproblemo
    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.
    
    
16. Jaki typ mają następują wyrażenia?
    
    a)   add
    b)   add 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)   add (f x) (g x)
    m)   f 7 (g 'x')
    n)   \f -> f (g x)
    o)   (\f -> f (g x)) square
    
    
17. 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'))
    
    
18. 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.
    
    
19. 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)
    

20. 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.
    
    
21. 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].
    
    
22. 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.
    
    
23. 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.
    
    
24. Proszę napisać typ Set z funkcjami member, subset, union, intersection oraz delete.
    
    
25. 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.
    
    
26. 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.
    
    
27. Proszę zdefiniować typ drzew binarnych BinTree z zadania 22. jako instancję klas Show, Eq oraz Ord.
    
    
28. 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.