FP Laboratory 4

From Marek Běhálek Wiki
Revision as of 09:14, 24 September 2020 by Beh01 (talk | contribs)
Jump to navigation Jump to search

Functions working with lists

Implement following functions:

  • Create a function that takes first n elements of the list.
take' :: Int -> [a] -> [a]
take' :: Int -> [a] -> [a]
take' 0 _ = []
take' _ [] = []
take' n (x:xs) = x: take' (n-1) xs
  • Create a function that takes the remaining list after the first n elements.
drop' :: Int -> [a] -> [a]
drop' :: Int -> [a] -> [a]
drop' 0 x = x
drop' _ [] = []
drop' n (_:xs) = drop' (n-1) xs
  • Create a function that find the smallest element in the list. Consider input restrictions.
minimum' :: [a] -> a -- Is this right?
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]
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)]
zipThem:: [a] -> [b] -> [(a,b)]
zipThem (x:xs) (y:ys) = (x,y) : zipThem xs ys
zipThem _ _ = []
  • Create a function that compute Cartesian product of two vectors.
dotProduct :: [a] -> [b] -> [(a,b)]
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
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
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]
quicksort :: (Ord a) => [a] -> [a]
quicksort (x:xs) = let lp = filter (< x) xs
                       rp = filter (>= x) xs
                   in quicksort lp ++ [x] ++ quicksort rp