FP Laboratory 4/cs

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

• 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

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

zipThem:: [a] -> [b] -> [(a,b)]
zipThem (x:xs) (y:ys) = (x,y) : zipThem xs ys
zipThem _ _ = []

• 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 funkci filter.

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]