Difference between revisions of "FP Laboratory 4"
Jump to navigation
Jump to search
Line 1: | Line 1: | ||
+ | <translate> | ||
== Functions working with lists == | == Functions working with lists == | ||
Implement following functions: | Implement following functions: | ||
* Create a function that takes first n elements of the list. | * Create a function that takes first n elements of the list. | ||
+ | </translate> | ||
+ | |||
<syntaxhighlight lang="Haskell">take' :: Int -> [a] -> [a]</syntaxhighlight> | <syntaxhighlight lang="Haskell">take' :: Int -> [a] -> [a]</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> | ||
Line 20: | Line 23: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
+ | <translate> | ||
* Create a function that takes the remaining list after the first n elements. | * Create a function that takes the remaining list after the first n elements. | ||
+ | </translate> | ||
+ | |||
<syntaxhighlight lang="Haskell">drop' :: Int -> [a] -> [a]</syntaxhighlight> | <syntaxhighlight lang="Haskell">drop' :: Int -> [a] -> [a]</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> | ||
Line 38: | Line 44: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
+ | <translate> | ||
* Create a function that find the smallest element in the list. Consider input restrictions. | * Create a function that find the smallest element in the list. Consider input restrictions. | ||
+ | </translate> | ||
+ | |||
<syntaxhighlight lang="Haskell">minimum' :: [a] -> a -- Is this right?</syntaxhighlight> | <syntaxhighlight lang="Haskell">minimum' :: [a] -> a -- Is this right?</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> | ||
+ | |||
*Main> minimum' [1,3,4,0] | *Main> minimum' [1,3,4,0] | ||
0 | 0 | ||
Line 56: | Line 66: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | * Find all integer divisors of a given number. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/8iKGkcOlzpI]]</div> | + | <translate> |
+ | * Find all integer divisors of a given number. | ||
+ | </translate> | ||
+ | |||
+ | <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/8iKGkcOlzpI]]</div> | ||
<syntaxhighlight lang="Haskell">divisors :: Int -> [Int]</syntaxhighlight> | <syntaxhighlight lang="Haskell">divisors :: Int -> [Int]</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> | ||
Line 81: | Line 95: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | + | <translate> | |
== Functions working with lists and tuples == | == Functions working with lists and tuples == | ||
Implement following functions: | Implement following functions: | ||
* Create a function that merge two lists into one list of tuples. | * Create a function that merge two lists into one list of tuples. | ||
+ | </translate> | ||
+ | |||
<syntaxhighlight lang="Haskell">zipThem:: [a] -> [b] -> [(a,b)]</syntaxhighlight> | <syntaxhighlight lang="Haskell">zipThem:: [a] -> [b] -> [(a,b)]</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> | ||
Line 101: | Line 117: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
+ | <translate> | ||
* Create a function that compute Cartesian product of two vectors. | * Create a function that compute Cartesian product of two vectors. | ||
+ | </translate> | ||
+ | |||
<syntaxhighlight lang="Haskell">dotProduct :: [a] -> [b] -> [(a,b)]</syntaxhighlight> | <syntaxhighlight lang="Haskell">dotProduct :: [a] -> [b] -> [(a,b)]</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> | ||
Line 128: | Line 147: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | * Create a function that computes n-th number in the Fibonacci sequence. The function should use tuples in the solution. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sge0DXXI36k]]</div> | + | <translate> |
+ | * Create a function that computes n-th number in the Fibonacci sequence. The function should use tuples in the solution. | ||
+ | </translate> | ||
+ | |||
+ | <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sge0DXXI36k]]</div> | ||
<syntaxhighlight lang="Haskell">fibonacci :: Int -> Int</syntaxhighlight> | <syntaxhighlight lang="Haskell">fibonacci :: Int -> Int</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> | ||
Line 147: | Line 170: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
+ | <translate> | ||
== High-order functions == | == High-order functions == | ||
* Create a function that takes a string and converts all characters to upper case letters. | * Create a function that takes a string and converts all characters to upper case letters. | ||
+ | </translate> | ||
+ | |||
<syntaxhighlight lang="Haskell">allToUpper :: String -> String</syntaxhighlight> | <syntaxhighlight lang="Haskell">allToUpper :: String -> String</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> | ||
Line 169: | Line 195: | ||
<div style="clear:both"></div> | <div style="clear:both"></div> | ||
− | * Implement the [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>] algorithm. As a pivot use always the first element in the list. For dividing the list, use the function <code>filter</code>. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sj8cbRv89To]]</div> | + | <translate> |
+ | * Implement the [https://en.wikipedia.org/wiki/Quicksort <code>quicksort</code>] algorithm. As a pivot use always the first element in the list. For dividing the list, use the function | ||
+ | </translate> | ||
+ | |||
+ | <code>filter</code>. <div style="float: right"> [[File:Video logo.png|80px|link=https://youtu.be/Sj8cbRv89To]]</div> | ||
<syntaxhighlight lang="Haskell">quicksort :: (Ord a) => [a] -> [a]</syntaxhighlight> | <syntaxhighlight lang="Haskell">quicksort :: (Ord a) => [a] -> [a]</syntaxhighlight> | ||
<syntaxhighlight lang="Haskell" class="myDark"> | <syntaxhighlight lang="Haskell" class="myDark"> |
Revision as of 20:10, 19 October 2021
Functions working with lists
Implement following functions:
- Create a function that takes first n elements of the list.
take' :: Int -> [a] -> [a]
*Main> take' 2 [1,2,3]
[1,2]
- Create a function that takes the remaining list after the first n elements.
drop' :: Int -> [a] -> [a]
*Main> drop' 2 [1,2,3]
[3]
- Create a function that find the smallest element in the list. Consider input restrictions.
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)
- Find all integer divisors of a given number.
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]
Functions working with lists and tuples
Implement following functions:
- Create a function that merge two lists into one list of tuples.
zipThem:: [a] -> [b] -> [(a,b)]
*Main> zipThem [1,2,3] "ABCD"
[(1,'A'),(2,'B'),(3,'C')]
- Create a function that compute Cartesian product of two vectors.
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))
- Create a function that computes n-th number in the Fibonacci sequence. The function should use tuples in the solution.
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))
High-order functions
- Create a function that takes a string and converts all characters to upper case letters.
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
- Implement the
quicksort
algorithm. As a pivot use always the first element in the list. For dividing the list, use the function
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]