Difference between revisions of "FP Laboratory 5/cs"
Jump to navigation
Jump to search
(Created page with "== Doplňková cvičení == * Vytvořte vlastní implementaci funkce map pomocí [http://zvon.org/other/haskell/Outputprelude/foldr_f.html <code>foldr</code>].") |
|||
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> | ||
+ | |||
+ | * Create your own implementation of the [http://zvon.org/other/haskell/Outputprelude/concatMap_f.html <code>concatMap</code>] function using [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> | ||
+ | |||
+ | * Given an arbitrary type a, a test predicate of type a → Bool and a list of elements of type a, the partition function should return a pair of lists. The first member of the pair is the sublist of the original list containing the elements that satisfy the test, and the second is the sublist containing those that fail the test. | ||
+ | |||
+ | <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> | ||
+ | |||
+ | * The function split is the right inverse of zip: it takes a list of pairs and returns a pair of lists. | ||
+ | |||
+ | <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> | ||
+ | |||
+ | |||
+ | * Create a function that divides a list of elements into the list of n-elements lists. Extra elements should be forgotten. | ||
+ | |||
+ | <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> | ||
+ | |||
+ | * Given a list of elements and a single element el, create a function that returns sequences of elements greater than el. | ||
+ | <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> |
Revision as of 06:43, 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]
- 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)]
- 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]
Komplexnější funkce
- Funkce, která spočítá počet výskytů všech znaků v řetězci.
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]
- 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.
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)]
- 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.
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]
- 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.
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)
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]
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]
- Given an arbitrary type a, a test predicate of type a → Bool and a list of elements of type a, the partition function should return a pair of lists. The first member of the pair is the sublist of the original list containing the elements that satisfy the test, and the second is the sublist containing those that fail the test.
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])
- The function split is the right inverse of zip: it takes a list of pairs and returns a pair of lists.
split :: [(a,b)] -> ([a],[b])
*Main> split [(1,False),(2,False)]
([1,2],[False,False])
- Create a function that divides a list of elements into the list of n-elements lists. Extra elements should be forgotten.
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]]
- Given a list of elements and a single element el, create a function that returns sequences of elements greater than 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]]