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.

    g) quadrat(L), którą wartocią zawiera quadraty elementów listy L1.

    h) combine(L1,L2), którą wartością zawiera pary elementów z list L1 i L2.
    Przykład:
     > combine([1,2,3,4],[a,b,c,d]).
     [[1,a],[2,b],[3,c],[4,d]] 
    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 funkcję fold 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. 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.

  17. Proszę implementować arytmetykę liczb zespolonych

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

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

  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ć 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) (\f x -> f (f x)) (\x -> x)
    h) \x -> x x
    i) f 7 (g 'a')
    
    Można używać map :: (a -> b) -> [a] -> [b] oraz square :: Int -> Int.

  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. Proszę obliczyć typ następujących funkcji.
    c) length []     = 0
       append (x:xs) = 1 + (length 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)
    
  22. 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].

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

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

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

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