FP Laboratory 5/cs

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]

• 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]

• 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]]