PFP Laboratory 2
Jump to navigation
Jump to search
Contents
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))
- 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
- Implement a function that computes greatest common divider for two given numbers.
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)
- Implement a function that compute, if a given number is a prime number.
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)
Simple functions working with list
Implement following functions:
- Create a function that computes length of a list.
length' :: [a] -> Int
*Main> length' "ABCD"
4
- Create a function that sums the list of integers.
sumIt :: [Int] -> Int
*Main> sumIt [1,2,3]
6
- Create a function that returns the first element in the list.
getHead :: [a] -> a
*Main> getHead [1,2,3]
1
- Create a function that returns the last element in the list.
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
- 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
- Create a function that returns the list without the last element.
getInit :: [a] -> [a]
*Main> getInit [1,2,3]
[1,2]
- Create a function that merge two lists into one list.
combine :: [a] -> [a] -> [a]
*Main> combine [1,2,3] [4,5]
[1,2,3,4,5]
- Create a function that finds the maximum in the list of integers.
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
- Create a function that reverse a list.
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)
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]
- 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