Difference between revisions of "FP Laboratory 4"

From Marek Běhálek Wiki
Jump to navigation Jump to search
 
(18 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Functions working with lists ==
+
<translate>
 +
== Functions working with lists == <!--T:1-->
 
Implement following functions:
 
Implement following functions:
  
 +
<!--T:2-->
 
* 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 24:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
 +
<translate>
 +
<!--T:3-->
 
* 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 46:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
 +
<translate>
 +
<!--T:4-->
 
* 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 69:
 
<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>
 +
<!--T:5-->
 +
* 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 99:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
 
+
<translate>
== Functions working with lists and tuples ==
+
== Functions working with lists and tuples == <!--T:6-->
 
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 121:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
 +
<translate>
 +
<!--T:7-->
 
* 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 152:
 
<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>
 +
<!--T:8-->
 +
* 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 176:
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
  
== High-order functions ==
+
<translate>
 +
== High-order functions == <!--T:9-->
 
* 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 201:
 
<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>
 +
<!--T:10-->
 +
* 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>.
 +
</translate>
 +
 
 +
<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">
Line 191: Line 228:
 
</div>
 
</div>
 
<div style="clear:both"></div>
 
<div style="clear:both"></div>
 +
 +
<translate>
 +
=Additional exercises= <!--T:11-->
 +
* Create a function that removes the first occurrence of a given element from a list.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">removeOne :: Eq a => a -> [a] -> [a]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> removeOne 4 [1,4,6,8,4,5,4,7]
 +
[1,6,8,4,5,4,7]
 +
*Main> removeOne 'e' "Ahoj"
 +
"Ahoj"
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:12-->
 +
* Create a function that removes all occurrences of a given element from a list.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">removeAll :: Eq a => a -> [a] -> [a]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> removeAll 4 [1,4,6,8,4,5,4,7]
 +
[1,6,8,5,7]
 +
*Main> removeAll 'e' "Ahoj"
 +
"Ahoj"
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:13-->
 +
* Create your own implementation of the [http://zvon.org/other/haskell/Outputprelude/replicate_f.html <code>replicate</code>] function.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">replicate' :: Int -> a -> [a]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> replicate' 4 8
 +
[8,8,8,8]
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:14-->
 +
* Create a function that realizes the left rotation of a list by n elements. Function [http://zvon.org/other/haskell/Outputprelude/iterate_f.html <code>iterate</code>] might be helpful.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">rotateLeftN :: [a] -> Int -> [a]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*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]
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:15-->
 +
* Create a function that realizes the right rotation of a list by n elements.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">rotateRightN :: [a] -> Int -> [a]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*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]
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:16-->
 +
* Create function alternate, which interleaves two lists into one, alternating between elements taken from the first list and elements from the second.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">alternate :: [a] -> [a] -> [a]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*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]
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:17-->
 +
* Use filter to create a non-recursive function that takes a list of integers as input and returns a list of those that are even and greater than 7.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">filterEvenGt7 :: [Int] -> [Int]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*Main> filterEvenGt7 [1,2,6,9,10,3,12,8]
 +
[10,12,8]
 +
*Main> filterEvenGt7 [5,2,6,19,129]
 +
[]
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:18-->
 +
* Create a function that splits a list of numbers into a list of triples. Extra elements should be forgotten.
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">makeTriples :: [a] -> [(a,a,a)]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*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)]
 +
</syntaxhighlight>
 +
 +
 +
<translate>
 +
<!--T:19-->
 +
* Create a function that inserts an element into a list on the specific index. 
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">insertOnIndex :: [a] -> a -> Int -> [a]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*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]
 +
</syntaxhighlight>
 +
 +
<translate>
 +
<!--T:20-->
 +
* Create a function that joins the list of lists into one list using a separator. 
 +
</translate>
 +
 +
<syntaxhighlight lang="Haskell">join :: [[a]] -> a -> [a]</syntaxhighlight>
 +
<syntaxhighlight lang="Haskell" class="myDark">
 +
*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]
 +
</syntaxhighlight>

Latest revision as of 05:56, 10 October 2023

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]
take' :: Int -> [a] -> [a]
take' 0 _ = []
take' _ [] = []
take' n (x:xs) = x: take' (n-1) xs
Try it!
  • Create a function that takes the remaining list after the first n elements.
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
Try it!
  • 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)
Try it!
  • Find all integer divisors of a given number.
Video logo.png
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]
Try it!

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')]
zipThem:: [a] -> [b] -> [(a,b)]
zipThem (x:xs) (y:ys) = (x,y) : zipThem xs ys
zipThem _ _ = []
Try it!
  • 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))
Try it!
  • Create a function that computes n-th number in the Fibonacci sequence. The function should use tuples in the solution.
Video logo.png
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))
Try it!

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
Try it!
  • Implement the quicksort algorithm. As a pivot use always the first element in the list. For dividing the list, use the function filter.
Video logo.png
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
Try it!

Additional exercises

  • Create a function that removes the first occurrence of a given element from a list.
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"
  • Create a function that removes all occurrences of a given element from a list.
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"
  • Create your own implementation of the replicate function.
replicate' :: Int -> a -> [a]
*Main> replicate' 4 8 
[8,8,8,8]
  • Create a function that realizes the left rotation of a list by n elements. Function iterate might be helpful.
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]
  • Create a function that realizes the right rotation of a list by n elements.
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]
  • Create function alternate, which interleaves two lists into one, alternating between elements taken from the first list and elements from the second.
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]
  • Use filter to create a non-recursive function that takes a list of integers as input and returns a list of those that are even and greater than 7.
filterEvenGt7 :: [Int] -> [Int]
*Main> filterEvenGt7 [1,2,6,9,10,3,12,8]
[10,12,8]
*Main> filterEvenGt7 [5,2,6,19,129]
[]
  • Create a function that splits a list of numbers into a list of triples. Extra elements should be forgotten.
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)]


  • Create a function that inserts an element into a list on the specific 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]
  • Create a function that joins the list of lists into one list using a separator.
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]