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ć funkcję fib n, która obliczy n-tą liczbę Fibonacci'ego.
   
   
3. 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ę <.
   
   
4. 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 

5. Proszę napisać funkcję gcd n m, której wartością jest największy spólny dzielnik dla n i m.
   
   
6. 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".
   
   
7. 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?
   
   
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ę hanoi n, która rozwiązuje problem wieży Hanoi.
   
   
10. Proszę napisać funkcję nww n m, której wartością jest najmniejsza spólna wielokrotność dla n i m.
    
    
11. Proszę napisać funkcję silnia n, która obliczy n!.
    Proszę podać dwie wersje tej funkcji: jedną rekurencyjną a jedną używając akumulator.
    
    
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 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.
    
    
13. Proszę napisać funkcję filter p l, której wartością jest lista wszystkich elementów listy l, które spełnią predykat p.
    
    
14. 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.
    
    
15. a) 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. Jaki ma typ funkcja my_map?
    
    b) Proszę zdefiniować funkcję my_foldr analogicznie do funkcji foldl. Jaki ma typ funkcja foldr?
    
    
16. 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
    
    
17. 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ć iloczyn skalarny.
    
    
18. Proszę zdefiniować funkcję iter f n, której wartością jest funkcja fⁿ.
    
    
19. Używając funkcje foldl i foldr proszę zdefiniować funkcje
    
    a) filter pred l
    
    b) forall pred l .
    
    
20. Proszę zdefiniować funkcję insertionsort :: (a -> a -> Bool) -> [a] -> [a].
    
    Proszę wykonywać zadanie raz "ręcznie" i raz używając funkcje fold.
    
    
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 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.
    
    
22. 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)
    
    
23. 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 x -> f (f x)
    e) (\f x -> f (f x)) square
    f) \x -> x x
    g) f 7 (g 'a')
    

    Można używać map :: (a -> b) -> [a] -> [b] oraz square :: Int -> Int.
    
    
24. Proszę obliczyć typ następujących funkcji.

    a) append []     l = l
       append (x:xs) l = x : (append xs l)
    
    b) map f []     = []
       map f (x:xs) = (f x) : (map f xs)
    
    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)
    

25. 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? W trakcie odpowiedzi należy obliczyć typ funkcji sum.
    Proszę poprawić definicję funkcji sum tak, aby wyrażenie sum length [1,2] ['a','b'] było poprawnie.
    
    
26. 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].
    
    
27. 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) sumBinTree, która obliczy sumę elementów 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.
    
    
28. 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) 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.
    
    Proszę także zrealizować funkcje te 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. 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.
    
    
32. Proszę zdefiniować typ drzew binarnych BinTree z zadania 27 jako instancję klas Show, Eq oraz Ord.
    
    
33. 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ę stoów.
    
    
34. 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.