Difference between revisions of "FP Laboratory 5"
Jump to navigation
Jump to search
(Marked this version for translation) |
|||
Line 179: | Line 179: | ||
<translate> | <translate> | ||
− | == Additional exercises == | + | == Additional exercises == <!--T:9--> |
* Create your own implementation of the map function using [http://zvon.org/other/haskell/Outputprelude/foldr_f.html <code>foldr</code>]. | * Create your own implementation of the map function using [http://zvon.org/other/haskell/Outputprelude/foldr_f.html <code>foldr</code>]. | ||
</translate> | </translate> | ||
Line 192: | Line 192: | ||
<translate> | <translate> | ||
+ | <!--T:10--> | ||
* 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>]. | * 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>]. | ||
</translate> | </translate> | ||
Line 204: | Line 205: | ||
<translate> | <translate> | ||
+ | <!--T:11--> | ||
* 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. | * 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. | ||
</translate> | </translate> | ||
Line 216: | Line 218: | ||
<translate> | <translate> | ||
+ | <!--T:12--> | ||
* The function split is the right inverse of zip: it takes a list of pairs and returns a pair of lists. | * The function split is the right inverse of zip: it takes a list of pairs and returns a pair of lists. | ||
</translate> | </translate> | ||
Line 227: | Line 230: | ||
<translate> | <translate> | ||
+ | <!--T:13--> | ||
* Create a function that divides a list of elements into the list of n-elements lists. Extra elements should be forgotten. | * Create a function that divides a list of elements into the list of n-elements lists. Extra elements should be forgotten. | ||
</translate> | </translate> | ||
Line 239: | Line 243: | ||
<translate> | <translate> | ||
+ | <!--T:14--> | ||
* Given a list of elements and a single element el, create a function that returns sequences of elements greater than el. | * Given a list of elements and a single element el, create a function that returns sequences of elements greater than el. | ||
</translate> | </translate> |
Latest revision as of 06:42, 10 October 2023
List comprehension
Using the list comprehension implement following functions:
- Create a function that generates a list of all odd numbers in given interval.
oddList :: Int -> Int -> [Int]
*Main> oddList 1 10
[1,3,5,7,9]
- Create a function that removes all upper case letters from a string.
removeAllUpper :: String -> String
*Main> removeAllUpper "ABCabcABC"
"abc"
import Data.Char
removeAllUpper :: String -> String
removeAllUpper xs = [ x |x<-xs, not (isUpper x)]
- Create functions that computes union and intersection of two sets.
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]
More complex functions
- Create a function that count the number of occurrences of all characters from a given string.
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]
- 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.
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)]
- 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.
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]
- 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.
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)
Additional exercises
- Create your own implementation of the map function using
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]]