Difference between revisions of "FP Laboratory 4/cs"
Jump to navigation
Jump to search
(Updating to match new version of source page) |
|||
(15 intermediate revisions by 2 users not shown) | |||
Line 40: | Line 40: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | * Funkce která | + | * Funkce která nalezne nejmenší prvek v seznamu. Jaké bude omezení na vstupu? |
<syntaxhighlight lang="Haskell">minimum' :: [a] -> a -- Is this right?</syntaxhighlight> | <syntaxhighlight lang="Haskell">minimum' :: [a] -> a -- Is this right?</syntaxhighlight> | ||
Line 135: | Line 135: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | * | + | * Funkce která spočítá n-tý člen Fibonacciho posloupnosti. V řešení využijte n-tice. |
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sge0DXXI36k]]</div> | <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sge0DXXI36k]]</div> | ||
Line 156: | Line 156: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | == | + | == Funkce vyššího řádu == |
− | * | + | * Funkce která převede všechny písmena v daném stringu na velká. |
<syntaxhighlight lang="Haskell">allToUpper :: String -> String</syntaxhighlight> | <syntaxhighlight lang="Haskell">allToUpper :: String -> String</syntaxhighlight> | ||
Line 179: | Line 179: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | * | + | * Implementujte [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>] algoritmus. Jako pivot využijte vždy první prvek v seznamu. Pro rozdělení seznamu použijte funkci <code>filter</code>. |
− | + | <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sj8cbRv89To]]</div> | |
<syntaxhighlight lang="Haskell">quicksort :: (Ord a) => [a] -> [a]</syntaxhighlight> | <syntaxhighlight lang="Haskell">quicksort :: (Ord a) => [a] -> [a]</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> | ||
Line 203: | Line 203: | ||
</div> | </div> | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
+ | |||
+ | =Doplňková cvičení= | ||
+ | * Vytvořte funkci, která odstraní první výskyt daného prvku ze seznamu. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">removeOne :: Eq a => a -> [a] -> [a]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> removeOne 4 [1,4,6,8,4,5,4,7] | ||
+ | [1,6,8,4,5,4,7] | ||
+ | *Main> removeOne 'e' "Ahoj" | ||
+ | "Ahoj" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvoření funkce, která odstraní všechny výskyty daného prvku ze seznamu. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">removeAll :: Eq a => a -> [a] -> [a]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> removeAll 4 [1,4,6,8,4,5,4,7] | ||
+ | [1,6,8,5,7] | ||
+ | *Main> removeAll 'e' "Ahoj" | ||
+ | "Ahoj" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvořte vlastní implementaci funkce [http://zvon.org/other/haskell/Outputprelude/replicate_f.html <code>replicate</code>]. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">replicate' :: Int -> a -> [a]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> replicate' 4 8 | ||
+ | [8,8,8,8] | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * * Vytvořte funkci, která realizuje levé otočení seznamu o n prvků. Funkce [http://zvon.org/other/haskell/Outputprelude/iterate_f.html <code>iterate</code>] může být užitečná. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">rotateLeftN :: [a] -> Int -> [a]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> rotateLeftN [1,2,3,4,5] 2 | ||
+ | [3,4,5,1,2] | ||
+ | *Main> rotateLeftN [1,2,3,4,5] 6 | ||
+ | [2,3,4,5,1] | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvořte funkci, která realizuje pravé otočení seznamu o n prvků. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">rotateRightN :: [a] -> Int -> [a]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> rotateRightN [1,2,3,4,5] 2 | ||
+ | [4,5,1,2,3] | ||
+ | *Main> rotateRightN [1,2,3,4,5] 6 | ||
+ | [5,1,2,3,4] | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvořte funkci <code>alternate</code>, která poskládá dva seznamy do jednoho a střídá prvky z prvního seznamu s prvky z druhého seznamu. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">alternate :: [a] -> [a] -> [a]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> alternate [1,2,3] [4,5,6] | ||
+ | [1,4,2,5,3,6] | ||
+ | *Main> alternate [1,2] [4,5,6] | ||
+ | [1,4,2,5,6] | ||
+ | *Main> alternate [1,2,3] [4] | ||
+ | [1,4,2,3] | ||
+ | *Main> alternate [1,2,3] [] | ||
+ | [1,2,3] | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Pomocí filtru vytvořte nerekurzivní funkci, která jako vstup přijme seznam celých čísel a vrátí seznam těch, která jsou sudá a větší než 7 | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">filterEvenGt7 :: [Int] -> [Int]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> filterEvenGt7 [1,2,6,9,10,3,12,8] | ||
+ | [10,12,8] | ||
+ | *Main> filterEvenGt7 [5,2,6,19,129] | ||
+ | [] | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvořte funkci, která rozdělí seznam čísel na seznam trojic. Prvky navíc budou zahozeny. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">makeTriples :: [a] -> [(a,a,a)]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> makeTriples [1,2,3,4,5,6,7,8,9] | ||
+ | [(1,2,3),(4,5,6),(7,8,9)] | ||
+ | *Main> makeTriples [1,2,3,4,5,6,7,8,9,10,11] | ||
+ | [(1,2,3),(4,5,6),(7,8,9)] | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | |||
+ | * Vytvoření funkce, která vloží prvek do seznamu na určitý index. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">insertOnIndex :: [a] -> a -> Int -> [a]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> insertOnIndex [4,5,6,7,8,9,10] 100 0 | ||
+ | [100,4,5,6,7,8,9,10] | ||
+ | *Main> insertOnIndex [4,5,6,7,8,9,10] 100 3 | ||
+ | [4,5,6,100,7,8,9,10] | ||
+ | *Main> insertOnIndex [4,5,6,7,8,9,10] 100 6 | ||
+ | [4,5,6,7,8,9,100,10] | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * Vytvořte funkci, která spojí seznam seznamů do jednoho seznamu pomocí oddělovače. | ||
+ | |||
+ | <syntaxhighlight lang="Haskell">join :: [[a]] -> a -> [a]</syntaxhighlight> | ||
+ | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | *Main> join ["I","love","functional","programming"] ' ' | ||
+ | "I love functional programming" | ||
+ | *Main> join [[1,2,3],[4,5],[6,7,8],[9]] 0 | ||
+ | [1,2,3,0,4,5,0,6,7,8,0,9] | ||
+ | </syntaxhighlight> |
Latest revision as of 06:27, 10 October 2023
Contents
Funkce pracující se seznamy
Implementujte následující funkce:
- Funkce která odebere prvních n prvků ze seznamu.
take' :: Int -> [a] -> [a]
*Main> take' 2 [1,2,3]
[1,2]
- Funkce která vrátí zbytek seznamu po odebrání prvních n prvků.
drop' :: Int -> [a] -> [a]
*Main> drop' 2 [1,2,3]
[3]
- Funkce která nalezne nejmenší prvek v seznamu. Jaké bude omezení na vstupu?
minimum' :: [a] -> a -- Is this right?
*Main> minimum' [1,3,4,0]
0
minimum' :: Ord a => [a] -> a
minimum' [x] = x
minimum' (x:y:z) | x < y = minimum' (x:z)
| otherwise = minimum' (y:z)
- Funkce která nalezne všechny celočíselné dělitele daného čísla.
divisors :: Int -> [Int]
*Main> divisors 32
[1,2,4,8,16,32]
divisors :: Int -> [Int]
divisors n = tmp n where
tmp 0 = []
tmp x | n `mod` x == 0 = x: tmp (x-1)
| otherwise = tmp (x-1)
divisors' :: Int -> [Int]
divisors' n = filter (\x -> n `mod` x == 0) [1..n]
divisors'' :: Int -> [Int]
divisors'' n = [x | x<-[1..n], n `mod` x == 0]
Funkce pracující se seznamy a n-ticemi
Implementujte následující funkce:
- Funkce která sloučí dva seznamy do jednoho seznamu dvojic.
zipThem:: [a] -> [b] -> [(a,b)]
*Main> zipThem [1,2,3] "ABCD"
[(1,'A'),(2,'B'),(3,'C')]
- Funkce která spočítá Kartézský součin dvou vektorů.
dotProduct :: [a] -> [b] -> [(a,b)]
*Main> dotProduct [1..4] "ABC"
[(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C'),(3,'A'),(3,'B'),(3,'C'),(4,'A'),(4,'B'),(4,'C')]
dotProduct :: [a] -> [b] -> [(a,b)]
dotProduct [] _ = []
dotProduct (x:xs) ys = tmp ys ++ dotProduct xs ys where
tmp [] = []
tmp (b:bs) = (x,b) : tmp bs
dotProduct' :: [a] -> [b] -> [(a,b)]
dotProduct' xs ys = [(x,y)|x<-xs, y<-ys]
dotProduct'' :: [a] -> [b] -> [(a,b)]
dotProduct'' x y =
zip (concat (map (replicate (length y)) x))
(concat (replicate (length x) y))
- Funkce která spočítá n-tý člen Fibonacciho posloupnosti. V řešení využijte n-tice.
fibonacci :: Int -> Int
*Main> fibonacci 12
144
fibonacci :: Int -> Int
fibonacci n = fst (tmp n) where
fibStep (a,b) = (b,a+b)
tmp 0 = (0,1)
tmp x = fibStep (tmp (x-1))
Funkce vyššího řádu
- Funkce která převede všechny písmena v daném stringu na velká.
allToUpper :: String -> String
*Main> allToUpper "aAbc"
"AABC"
import Data.Char
allToUpper :: String -> String
allToUpper xs = [toUpper x |x<-xs]
allToUpper' :: String -> String
allToUpper' xs = map toUpper xs
- Implementujte
quicksort
algoritmus. Jako pivot využijte vždy první prvek v seznamu. Pro rozdělení seznamu použijte funkcifilter
.
quicksort :: (Ord a) => [a] -> [a]
*Main> filter (<5) [1..10]
[1,2,3,4]
*Main> quicksort [1,5,3,7,9,5,2,1]
[1,1,2,3,5,5,7,9]
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = let lp = filter (< x) xs
rp = filter (>= x) xs
in quicksort lp ++ [x] ++ quicksort rp
Doplňková cvičení
- Vytvořte funkci, která odstraní první výskyt daného prvku ze seznamu.
removeOne :: Eq a => a -> [a] -> [a]
*Main> removeOne 4 [1,4,6,8,4,5,4,7]
[1,6,8,4,5,4,7]
*Main> removeOne 'e' "Ahoj"
"Ahoj"
- Vytvoření funkce, která odstraní všechny výskyty daného prvku ze seznamu.
removeAll :: Eq a => a -> [a] -> [a]
*Main> removeAll 4 [1,4,6,8,4,5,4,7]
[1,6,8,5,7]
*Main> removeAll 'e' "Ahoj"
"Ahoj"
- Vytvořte vlastní implementaci funkce
replicate
.
replicate' :: Int -> a -> [a]
*Main> replicate' 4 8
[8,8,8,8]
- * Vytvořte funkci, která realizuje levé otočení seznamu o n prvků. Funkce
iterate
může být užitečná.
rotateLeftN :: [a] -> Int -> [a]
*Main> rotateLeftN [1,2,3,4,5] 2
[3,4,5,1,2]
*Main> rotateLeftN [1,2,3,4,5] 6
[2,3,4,5,1]
- Vytvořte funkci, která realizuje pravé otočení seznamu o n prvků.
rotateRightN :: [a] -> Int -> [a]
*Main> rotateRightN [1,2,3,4,5] 2
[4,5,1,2,3]
*Main> rotateRightN [1,2,3,4,5] 6
[5,1,2,3,4]
- Vytvořte funkci
alternate
, která poskládá dva seznamy do jednoho a střídá prvky z prvního seznamu s prvky z druhého seznamu.
alternate :: [a] -> [a] -> [a]
*Main> alternate [1,2,3] [4,5,6]
[1,4,2,5,3,6]
*Main> alternate [1,2] [4,5,6]
[1,4,2,5,6]
*Main> alternate [1,2,3] [4]
[1,4,2,3]
*Main> alternate [1,2,3] []
[1,2,3]
- Pomocí filtru vytvořte nerekurzivní funkci, která jako vstup přijme seznam celých čísel a vrátí seznam těch, která jsou sudá a větší než 7
filterEvenGt7 :: [Int] -> [Int]
*Main> filterEvenGt7 [1,2,6,9,10,3,12,8]
[10,12,8]
*Main> filterEvenGt7 [5,2,6,19,129]
[]
- Vytvořte funkci, která rozdělí seznam čísel na seznam trojic. Prvky navíc budou zahozeny.
makeTriples :: [a] -> [(a,a,a)]
*Main> makeTriples [1,2,3,4,5,6,7,8,9]
[(1,2,3),(4,5,6),(7,8,9)]
*Main> makeTriples [1,2,3,4,5,6,7,8,9,10,11]
[(1,2,3),(4,5,6),(7,8,9)]
- Vytvoření funkce, která vloží prvek do seznamu na určitý index.
insertOnIndex :: [a] -> a -> Int -> [a]
*Main> insertOnIndex [4,5,6,7,8,9,10] 100 0
[100,4,5,6,7,8,9,10]
*Main> insertOnIndex [4,5,6,7,8,9,10] 100 3
[4,5,6,100,7,8,9,10]
*Main> insertOnIndex [4,5,6,7,8,9,10] 100 6
[4,5,6,7,8,9,100,10]
- Vytvořte funkci, která spojí seznam seznamů do jednoho seznamu pomocí oddělovače.
join :: [[a]] -> a -> [a]
*Main> join ["I","love","functional","programming"] ' '
"I love functional programming"
*Main> join [[1,2,3],[4,5],[6,7,8],[9]] 0
[1,2,3,0,4,5,0,6,7,8,0,9]