PFP Laboratory 2

From Marek Běhálek Wiki
Revision as of 10:48, 29 September 2022 by Beh01 (talk | contribs)
Jump to navigation Jump to search

More Functions

Implement following functions:

  • Term combination is a selection of items from a collection, such that (unlike permutations) the order of elements in this selection does not matter. Compute the number of possible combinations if we are taking k things from the collection of n things.
combinations :: Int -> Int -> Int
*Main> combinations 8 5
56
factorial  :: Int -> Int
factorial  0 = 1
factorial  n = n * factorial  (n-1)

combinations :: Int -> Int -> Int
combinations n k = factorial n `div` (factorial k * factorial (n-k))

combinations' :: Int -> Int -> Int
combinations' n k = fromIntegral(factorial n) `div` fromIntegral(factorial k * factorial (n-k))
Try it!
  • Implement a function that computes the number of solutions for a quadratic equation. This quadratic equation will be given using standard coefficients: a, b, c.
numberOfRoots :: Int -> Int -> Int -> Int
-- To simplify the solution, let construct can be used
f x y = let a = x + y
        in a * a
*Main> numberOfRoots 1 4 2
2
numberOfRoots :: Int -> Int -> Int -> Int
numberOfRoots a b c = let d = b*b - 4 * a *c
                      in if d<0 then 0 else if d == 0 then 1 else 2
Try it!
  • Implement a function that computes greatest common divider for two given numbers.
    Video logo.png
gcd' :: Int -> Int -> Int
*Main> gcd' 30 18
6
gcd' :: Int -> Int -> Int
gcd' a b | a > b = gcd' (a-b) b
         | a < b = gcd' a (b-a)
         | a==b = a

gcd2 :: Int -> Int -> Int         
gcd2 a 0 = a
gcd2 a b = gcd2 b (a `mod` b)
Try it!
  • Implement a function that compute, if a given number is a prime number.
    Video logo.png
isPrime :: Int -> Bool
*Main> isPrime 7
True
isPrime :: Int -> Bool
isPrime 1 = False
isPrime y = isPrimeTest y (y-1) where
  isPrimeTest _ 1 = True 
  isPrimeTest n x | n `mod` x ==0 = False
                  | otherwise = isPrimeTest n (x-1)
Try it!

Simple functions working with list

Implement following functions:

  • Create a function that computes length of a list.
length' :: [a] -> Int
*Main> length' "ABCD"
4
length' :: [a] -> Int
length' []  = 0
length' (_:xs) = 1 + length' xs
Try it!
  • Create a function that sums the list of integers.
Video logo.png
sumIt :: [Int] -> Int
*Main> sumIt [1,2,3]
6
sumIt :: [Int] -> Int
sumIt []  = 0
sumIt (x:xs) = x + sumIt xs
Try it!
  • Create a function that returns the first element in the list.
getHead :: [a] -> a
*Main> getHead [1,2,3]
1
getHead :: [a] -> a
getHead (x:_) = x
Try it!
  • Create a function that returns the last element in the list.
Video logo.png
getLast :: [a] -> a
*Main> getLast [1,2,3]
3
getLast :: [a] -> a
getLast [x] = x
getLast (x:xs) = getLast xs

getLast' :: [a] -> a
getLast' (x:xs) | length xs == 0 = x
                | otherwise = getLast' xs
Try it!
  • Create a function that checks if an element is a member of the list.
isElement :: Eq a => a -> [a] -> Bool
*Main> isElement 2 [1,2,3]
True
isElement :: Eq a => a -> [a] -> Bool
isElement _ [] = False
isElement a (x:xs) | a == x = True 
                   | otherwise = isElement a xs
Try it!
  • Create a function that returns the list without the last element.
Video logo.png
getInit :: [a] -> [a]
*Main> getInit [1,2,3]
[1,2]
getInit :: [a] -> [a]
getInit [_] = []
getInit (x:xs) = x : getInit xs
Try it!
  • Create a function that merge two lists into one list.
Video logo.png
combine :: [a] -> [a] -> [a]
*Main> combine [1,2,3] [4,5]
[1,2,3,4,5]
combine :: [a] -> [a] -> [a]
combine [] y = y
combine (x:xs) y = x : combine xs y
Try it!
  • Create a function that finds the maximum in the list of integers.
Video logo.png
max' :: [Int] -> Int
*Main> max' [3,1,7,5]
7
max' :: [Int] -> Int
max' [x] = x
max' (x:y:z) | x > y = max' (x:z)
             | otherwise = max' (y:z)

max'' :: [Int] -> Int
max'' (y:ys) = tmp y ys where
   tmp a [] = a
   tmp a (x:xs) | x > a = tmp x xs 
                |otherwise = tmp a xs
Try it!
  • Create a function that reverse a list.
Video logo.png
reverse' :: [a] -> [a]
*Main> reverse' [3,1,7,5]
[5,7,1,3]
reverse' :: [a] -> [a]             
reverse' [] = []
reverse' (x:xs) = (reverse' xs) ++ [x]

reverse'' :: [a] -> [a] 
reverse'' n = tmp n  []
  where tmp [] ys = ys 
        tmp (x:xs) ys = tmp xs (x:ys)
Try it!

Advanced 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!