Difference between revisions of "FP Laboratory 4/cs"

From Marek Běhálek Wiki
Jump to navigation Jump to search
(Created page with "Funkce která nalezne všechny celočíselné dělitele daného čísla.")
(Updating to match new version of source page)
 
(21 intermediate revisions by 2 users not shown)
Line 40: Line 40:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
Funkce která najde nejmenší prvek v seznamu. Jaké bude omezení na vstupu?
+
* 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 60: Line 60:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
Funkce která nalezne všechny celočíselné dělitele daného čísla.  
+
* Funkce která nalezne všechny celočíselné dělitele daného čísla.  
  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/8iKGkcOlzpI]]</div>
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/8iKGkcOlzpI]]</div>
Line 87: Line 87:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
== Functions working with lists and tuples ==
+
== Funkce pracující se seznamy a n-ticemi ==
Implement following functions:
+
Implementujte následující funkce:
* Create a function that merge two lists into one list of tuples.
+
* Funkce která sloučí dva seznamy do jednoho seznamu dvojic.
  
 
<syntaxhighlight lang="Haskell">zipThem:: [a] -> [b] -> [(a,b)]</syntaxhighlight>
 
<syntaxhighlight lang="Haskell">zipThem:: [a] -> [b] -> [(a,b)]</syntaxhighlight>
Line 107: Line 107:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Create a function that compute Cartesian product of two vectors.
+
* Funkce která spočítá Kartézský součin dvou vektorů.
  
 
<syntaxhighlight lang="Haskell">dotProduct :: [a] -> [b] -> [(a,b)]</syntaxhighlight>
 
<syntaxhighlight lang="Haskell">dotProduct :: [a] -> [b] -> [(a,b)]</syntaxhighlight>
Line 135: Line 135:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Create a function that computes n-th number in the Fibonacci sequence. The function should use tuples in the solution.
+
* 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>
  
== High-order functions ==
+
== Funkce vyššího řádu ==
* Create a function that takes a string and converts all characters to upper case letters.
+
* 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>
  
* Implement the [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>] algorithm. As a pivot use always the first element in the list. For dividing the list, use the function
+
* 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>.
  
<code>filter</code>. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sj8cbRv89To]]</div>
+
<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

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]
take' :: Int -> [a] -> [a]
take' 0 _ = []
take' _ [] = []
take' n (x:xs) = x: take' (n-1) xs
Try it!
  • Funkce která vrátí zbytek seznamu po odebrání prvních n prvků.
drop' :: Int -> [a] -> [a]
*Main> drop' 2 [1,2,3]
[3]
drop' :: Int -> [a] -> [a]
drop' 0 x = x
drop' _ [] = []
drop' n (_:xs) = drop' (n-1) xs
Try it!
  • 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)
Try it!
  • Funkce která nalezne všechny celočíselné dělitele daného čísla.
Video logo.png
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]
Try it!

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')]
zipThem:: [a] -> [b] -> [(a,b)]
zipThem (x:xs) (y:ys) = (x,y) : zipThem xs ys
zipThem _ _ = []
Try it!
  • 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))
Try it!
  • Funkce která spočítá n-tý člen Fibonacciho posloupnosti. V řešení využijte n-tice.
Video logo.png
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))
Try it!

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
Try it!
  • Implementujte quicksort algoritmus. Jako pivot využijte vždy první prvek v seznamu. Pro rozdělení seznamu použijte funkci filter.
Video logo.png
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
Try it!

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]