- 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ść.
- Używając reprezentacji (a,b) dla liczby wymiernej a/b proszę zdefiniować dodawanie, odejmowanie, mnożenie i dzielenie dla liczb wymiernych.
- 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ć funkcję Pascal n, której wartością jest n-ty wiersz trójkąta Pascala.
- Proszę napisać funkcję Hanoi n, która rozwiązuje problem Wieży Hanoi dla n krążków.
- Proszę napisać rekurencyjną oraz iteracyną funkcję fib n, która obliczy n-tą liczbę Fibonacci.
- Potęgowanie b^e można szybko wykonać używając b^e = (b^(e/2))^2.
Proszę napisać rekurencyjną oraz iteracyjną 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 l, która sprawdza, czy x jeste 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.
- 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.
- Proszę napisać funkcję permutation l, której wartością jest lista wszystkich permutacji elementów listy l.
- Proszę implementować arytmetykę liczb zespolonych
a) używając metodę "mainfest types".
b) używając metodę "message passing".
- Proszę napisać funkcję product term a next b analogicznie do funkcji sum z wykładu.
Proszę pokazywać, jak używając product można definiować funkcję silnia oraz przybliżać p na podstawie formuły
p/4 = 2 · 4 · 4 · 6 · 6 · 8 ··· / 3 · 3 · 5 · 5 · 7 · 7 ··· .
- Proszę napisać funkcję accumulate combiner null-value term a next b, która jest uogólnieniem funkcji sum i prod.
Argumenty term, next, a i b zachowują to same znaczenie niż w funkcjach sum i prod.
combiner jest dwuargumentową funkcją, która opisuje, jak term a zostaje dodane do akkumulacji dalszych termów.
null-value jest wartością inicjalną do używania w końcowym przypadku.
Proszę pokazywać, jak można definiować funkcje sum i prod używając accumulate.
Proszę też napisać iteracyjną wersję funkcji accumulate.
- Nawet funkcję accumulate można dalej uogólnić.
Proszę napisać funkcję filter_accumulate, która ma dodatkowy argument pred.
pred jest (jednoargumentowym) predykatem a filter_accumulate dodaje term a do wynika tylko, jeżeli a spełnie predykat pred.
Używając filter_accumulate proszę obliczyć sumę kwadratów liczb pierwszych w interwale [a,b]
oraz produkt wszystkich liczb naturalnych i mniejsze niż n, takie że nwd(i,n) = 1.
- W Haskell już zdefiniowane są funkcje foldl i
foldr przez
foldl f e [] = e foldr f e [] = e
foldl f e (x:xs) = foldl f (f e x) xs foldr f e (x:xs) = f x (foldr f e xs)
Proszę zdefiniować funkcje length, and (dla listy wartości boole'owskich), sum, prod, map i reverse używając funkcje foldl i foldr.
- 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 20.
- 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 20.
- 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.
Proszę zdefiniować funkcje quicksort i mergesort używając funkcję dz.
- Niech będą dane następujące wyrażenia.
a) f 7
b) f 7 (g 'x')
c) f (g x)
d) add (f x) (g x)
Proszę obliczyć typy tych wyrażeń używając inferencję typów.
- Niech będą dane następujące definicje.
a) append [] l = l b) fun [] = []
append (x:xs) l = x : (append xs l) fun (x:xs) = 1 + (fun x) + (fun xs)
Proszę obliczyć typy tych funkcji używając inferencję typów.
- Pary i ich selektory można zdefiniować bez konstruktorów:
mkPair a b sel = sel a b
first p = p (\x y -> x)
second p = p (\x y -> y)
Niech też będzie dana następująca funkcja.
pairId p = mkPair (first p) (second p)
Proszę obliczyć typ funkcji pairId używając inferencję typów.
Można używać następujące założenia.
first :: ((a1 -> b1 -> a1) -> c1) -> c1
second :: ((a2 -> b2 -> b2) -> c2) -> c2
mkPair :: a3 -> b3 -> (a3 -> b3 -> c3) -> c3
Dodoatkowo proszę pokazać, że first :: ((a1 -> b1 -> a1) -> c1) -> c1.
- 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) postBinTree, której wartością jest lista elementów drzewa w porząku postfiksowym.
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 28 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.
- Niech będzie dany λ-term
N º λx. (λx. xy) (x (λx. λy. yzx)).
Proszę obliczyć zbiór wolnych zmiennych termu N.
- Proszę ewaluować następujące λ-termy.
a) (λx. x) (xy)
b) (λx. xy) (λx. xz)
c) (λx. λy. xy) (xy)
- Zadanie to zajmuje się implementacją ewaluacji λ-termów w Haskell'u.
a) Proszę zdefiniować typ reprezentujący λ-termy.
b) Proszę zdefiniować funkcję subst, która
realizuje substytucję M[x/N].
Można założyć, ż nie ma wolnych zmiennych.
c) Proszę zdefiniować funkcję ewal, która ewaluuje λ-termy.
- 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ę znaleźć λ-termy add i mult
realizujące operacje dodawanie i mnożenie dwuch liczb naturalnych.
- 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,Rek(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.