- 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
- 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).
- 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?
- 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
- 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".
- 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ść.
- 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.
- Proszę napisać rekurencyjną funkcję fib n, która obliczy n-tą liczbę Fibonacci.
-
Proszę napisać funkcję binom n k, której wartością jest symbol Newtona dla n i k.
- Potęgowanie b^e można szybko wykonać używając b^e = (b^(e/2))^2.
Proszę napisać rekurencyjną funkcję exp b e na podstawie tej właściwości.
- 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 lementem 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.
- a) Proszę napisać funkcję permutation l, której wartością jest lista wszystkich permutacji elementów listy l.
b) 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.
- Proszę napisać funkcję Iter n f dla jednoargomentowej funkcji f i liczby naturalnej x. Wartością funkcji jest funckją, która obliczy fn.
Przykłady: > iter 2 square 3
81
> let f = iter 2 square
> f 5
625
> iter 0 square 7
7
Jaki ma typ funkcja Iter?
- 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?
- Proszę zdefiniować funkcję filter pred l, której wartością jest lista wszystkich elementów listy l, które spełnią predykat pred.
Jaki ma typ funkcja filter?
- a) Proszę zdefiniować funkcję
foldr analogicznie do funkcji foldl.
b) Proszę zdefiniować funkcje length, and (dla listy wartości boole'owskich), sum, prod, map i reverse używając funkcje foldl i foldr.
- 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ć produkt wektorowy.
- 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 17.
- 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 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:
- test, który sprawdza czy przypadek jest triwialny
- koniec, który rozwiązuje triwialny przypadek
- dziel, który dzieli problem do podproblemow
- 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.
- Jaki typ mają następują wyrażenia?
a) add
b) add 37
c) f 7
d) \f -> f 7
e) add (f x) (g x)
f) f 7 (g 'x')
g) \f -> f (g x)
- Proszę obliczyć mgu 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'))
g) h(x,g(y)) h(f(y),g(b))
- Proszę obliczyczyć typ następujących wyrażeń.
a) \x -> 2 * x
b) \x -> x x
c) \f -> f x
d) append [] l = l
append (x:xs) l = x : (append xs l)
e) fun [] = 0
fun (x:xs) = 1 + (fun x) + (fun xs)
- 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.
- 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) preBinTree, której wartością jest lista elementów drzewa w porządku prefiksowym.
Należy do tego używać nadające się funkcje mapBinTree i foldBinTree.
- 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.
- Proszę napisać moduł Set z funkcjami member,
subset, union, intersection oraz delete.
- 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.
- Proszę zdefiniować typ drzew binarnych BinTree z zadania 27 jako
instancję klas Show, Eq oraz Ord.
-
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.
- 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.
- Proszę ewaluować następujące λ-termy.
a) (λx. x) (xy)
b) (λx. xy) (λx. xz)
c) (λx. λy. xy) (xy)
- a) Niech będą dane następujące λ-termy.
true º λx. λy. x
false º λx. λy. y
Proszę pokazać, że λ-termy λx.(x false true) i
λ x. (λ y. (x ( y false true) y ))) implementują funkcje not 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)
λm. λn. λf. λx. m f (n f x) realizują funkcje s i +.
Co implementuje λ-term λn. n (λn. false) true?
- 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?
- 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,primRek(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.
- Proszę pokazać, że wszystkie funkcje pierwotnie rekurencyjne można zdefiniować w λ-rachunku.