Difference between revisions of "FP Laboratory 5/cs"

From Marek Běhálek Wiki
Jump to navigation Jump to search
(Created page with "== Komplexnější funkce ==")
(Created page with "* Při zadání seznamu prvků a jediného prvku <code>el</code> vytvořte funkci, která vrátí posloupnost prvků větších než <code>el</code>.")
 
(20 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Generátory seznamů ==
 
== Generátory seznamů ==
Implementujte následující funkce s využitím genrátoru seznamu:
+
Implementujte následující funkce s využitím generátorů seznamů:
* Vytvořte funkci, která vygeneruje seznam všech lichých čísel v daném intervalu.
+
* Funkce, která vygeneruje seznam všech lichých čísel v daném intervalu.
 
<syntaxhighlight lang="Haskell">oddList :: Int -> Int -> [Int]</syntaxhighlight>
 
<syntaxhighlight lang="Haskell">oddList :: Int -> Int -> [Int]</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
Line 16: Line 16:
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
* Vztvořte funkci která odstraní všechna velká písmena z řetězce.
+
* Funkce, která odstraní všechna velká písmena z řetězce.
 
<syntaxhighlight lang="Haskell">removeAllUpper :: String -> String</syntaxhighlight>
 
<syntaxhighlight lang="Haskell">removeAllUpper :: String -> String</syntaxhighlight>
 
<syntaxhighlight lang="Haskell" class="myDark">
 
<syntaxhighlight lang="Haskell" class="myDark">
Line 34: Line 34:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Vytvořte funkci která spočítá sjednocení a průnik dvou množin.
+
* Funkce, která spočítá sjednocení a průnik dvou množin.
  
 
<syntaxhighlight lang="Haskell">
 
<syntaxhighlight lang="Haskell">
Line 61: Line 61:
 
== Komplexnější funkce ==
 
== Komplexnější funkce ==
  
* Create a function that count the number of occurrences of all characters from a given string.
+
* Funkce, která spočítá počet výskytů všech znaků v řetězci.
  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/B2LFNJfC-TU]]</div>  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/B2LFNJfC-TU]]</div>  
Line 90: Line 90:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case yet. Create a function, that computes for a given even integer number the list of pairs of primes, that satisfies the rule of Goldbach's conjecture.  
+
* Goldbachova hypotéza říká, že každé kladné sudé číslo větší než 2 lze vyjádřit jako součet dvou prvočísel. Příklad: 28 = 5 + 23. Je to jedna z nejslavnějších hypotéz v teorii čísel, která však ještě nebyla dokázána. Vytvořte funkci, která pro dané celé číslo spočítá seznam dvojic prvočísel, které splňují Goldbachovu hypotézu.  
  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/ncjM2Ki65Vc]]</div>  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/ncjM2Ki65Vc]]</div>  
Line 112: Line 112:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. We will be searching for cases that violates this rule. Create a function, that has three parameters. First two defines an interval, where we will be searching for Goldbach numbers. The last parameter is the limit. For each number in this interval, find Goldbach's pair with smallest prime number. If this smallest number is bigger than given limit, the corresponding pair will be in the result.
+
* Ve většině případů, pokud je sudé číslo zapsáno jako součet dvou prvočísel, jedno z nich je velmi malé. Budeme hledat případy, které tohle pravidlo nesplňují. Vytvořte funkci která má tři parametry. První dva definují interval, kde budeme hledat Goldbachova čísla. Poslední parametr je limit. Pro každé číslo v intervalu nalezněte Goldbachovu dvojici s nejmenším prvočíslem. Pokud je nejmenšé prvočíslo větší než daný limit, přislušná dvojice bude obsažena ve výsledku.
  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/qIdHcI_8jms]]</div>  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/qIdHcI_8jms]]</div>  
Line 137: Line 137:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
* Create a function that generates all combinations of given length from the characters from given string. You can assume, that all character are unique and the given length is not bigger then the length of this string.
+
* Funkce, která generuje všechny kombinace dané délky ze znaků z daného řetězce. Můžete předpokládat, že všechny znaky jsou jedinečné a daná délka není větší než délka tohoto řetězce.
  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/-muPoJucLyI]]</div>  
 
<div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/-muPoJucLyI]]</div>  
Line 157: Line 157:
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
 +
 +
== Doplňková cvičení ==
 +
* Vytvořte vlastní implementaci funkce map pomocí [http://zvon.org/other/haskell/Outputprelude/foldr_f.html <code>foldr</code>].
 +
 +
<syntaxhighlight lang="Haskell">foldrMap :: (a -> b) -> [a] -> [b]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> foldrMap odd [1,2,3,4,5,6]
 +
[True,False,True,False,True,False]
 +
*Main> foldrMap (*2) [1,2,3,4,5,6]
 +
[2,4,6,8,10,12]
 +
</syntaxhighlight>
 +
 +
* Vytvořte si vlastní implementaci funkce [http://zvon.org/other/haskell/Outputprelude/concatMap_f.html <code>concatMap</code>] s použitím [http://zvon.org/other/haskell/Outputprelude/foldl_f.html <code>foldl</code>].
 +
 +
<syntaxhighlight lang="Haskell">foldlConcatMap :: (a -> [b]) -> [a] -> [b]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> foldlConcatMap divisors [9,21,36]
 +
[1,3,9,1,3,7,21,1,2,3,4,6,9,12,18,36]
 +
*Main> foldlConcatMap (\x -> replicate 3 x) [9,21,36]
 +
[9,9,9,21,21,21,36,36,36]
 +
</syntaxhighlight>
 +
 +
* Pro libovolný typ <code>a</code>, testovací funkci typu <code>a -> Bool</code> a seznamu prvků typu <code>a</code> by měla funkce vrátit dvojici seznamů. Prvním členem dvojice je podseznam původního seznamu obsahující prvky, které testu vyhovují testovací funkci, a druhým je podseznam obsahující prvky, které testu nevyhovují.
 +
 +
<syntaxhighlight lang="Haskell">partition :: (a -> Bool) -> [a] -> ([a],[a])</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> partition odd [1,2,3,4,5,6]
 +
([1,3,5],[2,4,6])
 +
*Main> partition (\x -> False) [5,9,0]
 +
([],[5,9,0])
 +
</syntaxhighlight>
 +
 +
* Funkce split je inverzí funkce zip: přijímá seznam dvojic a vrací dvojici seznamů.
 +
 +
<syntaxhighlight lang="Haskell">split :: [(a,b)] -> ([a],[b])</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> split [(1,False),(2,False)]
 +
([1,2],[False,False])
 +
</syntaxhighlight>
 +
 +
 +
* Vytvořte funkci, která rozdělí seznam prvků na seznam n-prvkových seznamů. Prvky navíc by se měly zahodit.
 +
 +
<syntaxhighlight lang="Haskell">divideList :: [a] -> Int -> [[a]]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> divideList "I love functional programming!" 5
 +
["I lov","e fun","ction","al pr","ogram","ming!"]
 +
*Main> divideList [1..20] 3
 +
[[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]
 +
</syntaxhighlight>
 +
 +
* Při zadání seznamu prvků a jediného prvku <code>el</code> vytvořte funkci, která vrátí posloupnost prvků větších než <code>el</code>.
 +
<syntaxhighlight lang="Haskell">sequences :: Ord a => [a] -> a -> [[a]]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> sequences [4,5,6,8,4,1,0,2,5,8,4,5,5,3,5,8] 4
 +
[[5,6,8],[5,8],[5,5],[5,8]]
 +
</syntaxhighlight>

Latest revision as of 06:51, 10 October 2023

Generátory seznamů

Implementujte následující funkce s využitím generátorů seznamů:

  • Funkce, která vygeneruje seznam všech lichých čísel v daném intervalu.
oddList :: Int -> Int -> [Int]
*Main> oddList 1 10   
[1,3,5,7,9]
oddList :: Int -> Int -> [Int]
oddList a b = [ x |x<-[a..b], odd x]
Try it!
  • Funkce, která odstraní všechna velká písmena z řetězce.
removeAllUpper :: String -> String
*Main> removeAllUpper "ABCabcABC"
"abc"
import Data.Char

removeAllUpper :: String -> String
removeAllUpper xs = [ x |x<-xs, not (isUpper x)]
Try it!
  • Funkce, která spočítá sjednocení a průnik dvou množin.
union :: Eq a => [a] -> [a] -> [a]
intersection :: Eq a => [a] -> [a] -> [a]
*Main> union [1..5] [3..10]
[1,2,3,4,5,6,7,8,9,10]
*Main> intersection [1..5] [3..10]
[3,4,5]
union :: Eq a => [a] -> [a] -> [a]
union xs ys = xs ++ [y| y<-ys, not (elem y xs)]

intersection ::  Eq a =>  [a] -> [a] -> [a]
intersection xs ys = [y| y<-ys, elem y xs]
Try it!

Komplexnější funkce

  • Funkce, která spočítá počet výskytů všech znaků v řetězci.
Video logo.png
countThem :: String -> [(Char, Int)]
*Main>countThem "hello hello hello"
[('h',3),('e',3),('l',6),('o',3),(' ',2)]
unique :: String -> String
unique n = reverse(tmp n "") where
  tmp [] store = store
  tmp (x:xs) store | x `elem` store = tmp xs store
                   | otherwise = tmp xs (x:store)

unique' :: String -> String                   
unique' [] = []
unique' (x:xs) = x: unique' (filter (/=x)xs)

countThem :: String -> [(Char, Int)]
countThem xs = let u = unique xs
               in [(x, length (filter (==x) xs)) |x<-u]
Try it!
  • Goldbachova hypotéza říká, že každé kladné sudé číslo větší než 2 lze vyjádřit jako součet dvou prvočísel. Příklad: 28 = 5 + 23. Je to jedna z nejslavnějších hypotéz v teorii čísel, která však ještě nebyla dokázána. Vytvořte funkci, která pro dané celé číslo spočítá seznam dvojic prvočísel, které splňují Goldbachovu hypotézu.
Video logo.png
goldbach :: Int-> [(Int, Int)]
*Main>goldbach 28
[(5, 23),(11,17)]
isPrime :: Int -> Bool
isPrime n = null [x |x<-[2..ceiling (sqrt (fromIntegral n)::Double)], n `mod` x == 0]

goldbach :: Int-> [(Int, Int)]
goldbach n = let primes = [x |x<-[2..(n `div` 2)], isPrime x]
             in [(x,n-x) |x<-primes, isPrime (n-x)]
Try it!
  • Ve většině případů, pokud je sudé číslo zapsáno jako součet dvou prvočísel, jedno z nich je velmi malé. Budeme hledat případy, které tohle pravidlo nesplňují. Vytvořte funkci která má tři parametry. První dva definují interval, kde budeme hledat Goldbachova čísla. Poslední parametr je limit. Pro každé číslo v intervalu nalezněte Goldbachovu dvojici s nejmenším prvočíslem. Pokud je nejmenšé prvočíslo větší než daný limit, přislušná dvojice bude obsažena ve výsledku.
Video logo.png
goldbachList :: Int -> Int-> Int -> [(Int, Int)]
*Main>goldbachList 4 2000 50
[(73,919),(61,1321),(67,1789),(61,1867)]
isPrime :: Int -> Bool
isPrime n = null [x |x<-[2..ceiling (sqrt (fromIntegral n)::Double)], n `mod` x == 0]

goldbach :: Int-> [(Int, Int)]
goldbach n = let primes = [x |x<-[2..(n `div` 2)+1], isPrime x]
             in [(x,n-x) |x<-primes, isPrime (n-x)]

goldbachList :: Int -> Int-> Int -> [(Int, Int)]
goldbachList a b limit = filter (\(x,_)-> x>limit) [head (goldbach x) | x<-[a..b], even x]
Try it!
  • Funkce, která generuje všechny kombinace dané délky ze znaků z daného řetězce. Můžete předpokládat, že všechny znaky jsou jedinečné a daná délka není větší než délka tohoto řetězce.
Video logo.png
combinations :: Int -> String -> [String]
*Main> combinations 3 "abcdef"
["abc","abd","abe",...]
combinations :: Int -> String -> [String]
combinations 1 xs = [[x]| x<-xs]
combinations n (x:xs) | n == length (x:xs) = [(x:xs)]
                      |otherwise = [[x] ++ y |y<-combinations (n-1) xs ] 
                                    ++ (combinations n xs)
Try it!

Doplňková cvičení

  • Vytvořte vlastní implementaci funkce map pomocí foldr.
foldrMap :: (a -> b) -> [a] -> [b]
*Main> foldrMap odd [1,2,3,4,5,6]
[True,False,True,False,True,False]
*Main> foldrMap (*2) [1,2,3,4,5,6]
[2,4,6,8,10,12]
  • Vytvořte si vlastní implementaci funkce concatMap s použitím foldl.
foldlConcatMap :: (a -> [b]) -> [a] -> [b]
*Main> foldlConcatMap divisors [9,21,36]
[1,3,9,1,3,7,21,1,2,3,4,6,9,12,18,36]
*Main> foldlConcatMap (\x -> replicate 3 x) [9,21,36]
[9,9,9,21,21,21,36,36,36]
  • Pro libovolný typ a, testovací funkci typu a -> Bool a seznamu prvků typu a by měla funkce vrátit dvojici seznamů. Prvním členem dvojice je podseznam původního seznamu obsahující prvky, které testu vyhovují testovací funkci, a druhým je podseznam obsahující prvky, které testu nevyhovují.
partition :: (a -> Bool) -> [a] -> ([a],[a])
*Main> partition odd [1,2,3,4,5,6]
([1,3,5],[2,4,6])
*Main> partition (\x -> False) [5,9,0]
([],[5,9,0])
  • Funkce split je inverzí funkce zip: přijímá seznam dvojic a vrací dvojici seznamů.
split :: [(a,b)] -> ([a],[b])
*Main> split [(1,False),(2,False)] 
([1,2],[False,False])


  • Vytvořte funkci, která rozdělí seznam prvků na seznam n-prvkových seznamů. Prvky navíc by se měly zahodit.
divideList :: [a] -> Int -> [[a]]
*Main> divideList "I love functional programming!" 5
["I lov","e fun","ction","al pr","ogram","ming!"]
*Main> divideList [1..20] 3
[[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]
  • Při zadání seznamu prvků a jediného prvku el vytvořte funkci, která vrátí posloupnost prvků větších než el.
sequences :: Ord a => [a] -> a -> [[a]]
*Main> sequences [4,5,6,8,4,1,0,2,5,8,4,5,5,3,5,8] 4
[[5,6,8],[5,8],[5,5],[5,8]]