FP Laboratory 5/en - Revision history

FuzzyBot: Updating to match new version of source page

2023-10-10T06:45:34Z

Updating to match new version of source page

FuzzyBot: Updating to match new version of source page

2021-10-19T10:29:18Z

Updating to match new version of source page

FuzzyBot: Updating to match new version of source page

2021-10-19T09:17:53Z

Updating to match new version of source page

FuzzyBot: Updating to match new version of source page

2021-10-19T08:04:02Z

Updating to match new version of source page

New page

== List comprehension ==
Using the list comprehension implement following functions:
* Create a function that generates a list of all odd numbers in given interval.
<syntaxhighlight lang="Haskell">oddList :: Int -> Int -> [Int]</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark">
*Main> oddList 1 10
[1,3,5,7,9]
</syntaxhighlight>

<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
oddList :: Int -> Int -> [Int]
oddList a b = [ x |x<-[a..b], odd x]
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/TXOOI93332]]
</div>
<div style="clear:both"></div>

* Create a function that removes all upper case letters from a string.
<syntaxhighlight lang="Haskell">removeAllUpper :: String -> String</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark">
*Main> removeAllUpper "ABCabcABC"
"abc"
</syntaxhighlight>

<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
import Data.Char

removeAllUpper :: String -> String
removeAllUpper xs = [ x |x<-xs, not (isUpper x)]
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/TXOOI93332]]
</div>
<div style="clear:both"></div>

* Create functions that computes union and intersection of two sets.
<syntaxhighlight lang="Haskell">
union :: Eq a => [a] -> [a] -> [a]
intersection :: Eq a => [a] -> [a] -> [a]
</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark">
*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]
</syntaxhighlight>

<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
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]
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/TXOOI93332]]
</div>
<div style="clear:both"></div>

== More complex functions ==

* Create a function that count the number of occurrences of all characters from a given string. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/B2LFNJfC-TU]]</div>
<syntaxhighlight lang="Haskell">countThem :: String -> [(Char, Int)]</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark">
*Main>countThem "hello hello hello"
[('h',3),('e',3),('l',6),('o',3),(' ',2)]
</syntaxhighlight>

<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
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]
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/UVITE26792]]
</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. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/ncjM2Ki65Vc]]</div>
<syntaxhighlight lang="Haskell">goldbach :: Int-> [(Int, Int)]</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark">
*Main>goldbach 28
[(5, 23),(11,17)]
</syntaxhighlight>

<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
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)]
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/WERCTD69700]]
</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. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/qIdHcI_8jms]]</div>
<syntaxhighlight lang="Haskell">goldbachList :: Int -> Int-> Int -> [(Int, Int)]</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark">
*Main>goldbachList 4 2000 50
[(73,919),(61,1321),(67,1789),(61,1867)]
</syntaxhighlight>

<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
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]
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/CIOER71292]]
</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. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/-muPoJucLyI]]</div>
<syntaxhighlight lang="Haskell">combinations :: Int -> String -> [String]</syntaxhighlight>
<syntaxhighlight lang="Haskell" class="myDark">
*Main> combinations 3 "abcdef"
["abc","abd","abe",...]
</syntaxhighlight>

<div class="mw-collapsible mw-collapsed" data-collapsetext="Hide solution" data-expandtext="Show solution">
<syntaxhighlight lang="Haskell">
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)
</syntaxhighlight>
[[File:Tryit.png|center|60px|Try it!|link=https://rextester.com/RTRV90066]]
</div>
<div style="clear:both"></div>

← Older revision		Revision as of 06:45, 10 October 2023
Line 157:		Line 157:
	</div>		</div>
	<div style="clear:both"></div>		<div style="clear:both"></div>
		+
		+	== Additional exercises ==
		+	* Create your own implementation of the map function using [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>

@@ Line 35: / Line 35: @@
 * Create functions that computes union and intersection of two sets.
 <syntaxhighlight lang="Haskell">
 union :: Eq a => [a] -> [a] -> [a]
@@ Line 60: / Line 61: @@
 == More complex functions ==
-* Create a function that count the number of occurrences of all characters from a given string. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/B2LFNJfC-TU]]</div>
+* Create a function that count the number of occurrences of all characters from a given string.
 <syntaxhighlight lang="Haskell">countThem :: String -> [(Char, Int)]</syntaxhighlight>
 <syntaxhighlight lang="Haskell" class="myDark">
@@ Line 87: / Line 90: @@
 <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. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/ncjM2Ki65Vc]]</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.
 <syntaxhighlight lang="Haskell">goldbach :: Int-> [(Int, Int)]</syntaxhighlight>
 <syntaxhighlight lang="Haskell" class="myDark">
@@ Line 107: / Line 112: @@
 <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. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/qIdHcI_8jms]]</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.
 <syntaxhighlight lang="Haskell">goldbachList :: Int -> Int-> Int -> [(Int, Int)]</syntaxhighlight>
 <syntaxhighlight lang="Haskell" class="myDark">
@@ Line 130: / Line 137: @@
 <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. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/-muPoJucLyI]]</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.
 <syntaxhighlight lang="Haskell">combinations :: Int -> String -> [String]</syntaxhighlight>
 <syntaxhighlight lang="Haskell" class="myDark">

@@ Line 16: / Line 16: @@
 </div>
 <div style="clear:both"></div>
 * Create a function that removes all upper case letters from a string.
 <syntaxhighlight lang="Haskell">removeAllUpper :: String -> String</syntaxhighlight>