-
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
> a
> 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 gcd n m oraz lcm n m (dla liczb naturalnych), których
wartością jest największy spólny dzielnik
oraz najmniejsza wspólna wielokrotność n i m.
-
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ę < oraz operacje boolowskie.
- 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ć 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
- 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.
- Funkcję silnia można zrealizować następująco.
silnia n = silnia_help n 1
where silnia_help 0 acc = acc
silnia_help n acc = silnia_help (n - 1) (n * acc)
W tym przypadku zmienna acc w funkcji silnia_help nazywa się akumulator.
Proszę napisać funkcję
fib n, która obliczy n-tego elementu ciągu Fibonacci'ego.
Proszę podać dwie wersje tej funkcji: jedną rekurencyjną a jedną iteracyjną,
tzn. używając akumulator.
- Potęgowanie b^e (dla liczb naturalnych b i 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 , 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) 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)]
g) 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.
h) map f l , która zastosuje jednoargumentową funkcję f
do wszystkich elementów listy l.
- 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]
b) Proszę napisać funkcję filter p l, której wartością jest lista wszystkich elementów listy l, które
spełnią jednoargumentowy predykat p.
- Jakie mają typy funkcje z zadań 5,6,9 oraz 10?
- Proszę zdefiniować funkcję foldr analogicznie do funkcji foldl.
Jaki ma typ funkcja foldr?
- Używając funkcje foldl i foldr proszę zdefiniować funkcje
a) prod
b) length
c) and (dla list wartości boole'owskich)
d) nwd (dla list liczb naturalnych)
e) delete
f) map
g) reverse
h) filter pred
i) forall pred.
- Proszę zdefiniować funkcję insertionsort :: (a -> a -> Bool) -> [a] -> [a]
przy pomocy kombinatora.
- 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 in f 5
625
> iter 0 square 7
7
- 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 podproblemów
- 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) +
b) + 37
c) append
d) append [1,2]
e) map
f) map square [1,2,3,4,5]
g) map square [['a']]
h) map length [['a']]
i) foldl
j) foldl (++)
k) foldl (++) []
l) f 7
m) \f -> f 7
n) + (f x) (g x)
o) f 7 (g 'x')
p) \f -> f (g x)
q) (\f -> f (g x)) square
- 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'))
- 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.
- 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)
- 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.
- 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].
- Niech będzie dany następujący typ dla drzew binarnych.
data BinTree a = Leaf a | Node a (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.
- 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.
- Proszę napisać typ Set z funkcjami member,
subset, union, intersection oraz delete.
- 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.
- 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.
- Proszę zdefiniować typ drzew binarnych BinTree z zadania 23
oraz typ zbiorów Set z zadania 25 jako
instancję klas Show, Eq oraz Ord.
- 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.
- Zostało już zdefiniowane parę funkcji map dla list i różnych dzrew.
Przy pomocy klasy typów proszę zastosować mechanism overloading do tych funkcji.
Proszę też zdefiniować funkcje map dla zbiorów z zadania 25.
- Proszę ewaluować następujące λ-termy.
a) (λx. x) (xy)
b) (λx. xy) (λx. xz)
c) (λx. λy. xy) (xy)
d) (λx. (λf. f(f(x))) (λx. x * x + 1)) 2