4 Nov

# Format

There will be 4 exercises. Each of them will specify which method you must to use:

1. recursion
2. list comprehension
3. higher order functions (map, filter, fold)
4. any method you want

The exam will last for one hour.

# Warm-up example

For given list, increment positive numbers and remove negative ones

``````> incrPos [1, -17, 0, 3]
[2, 4]
``````

## Recursion

``````incrPos (x:xs)
| x > 0       = x + 1 : incrPos xs
| otherwise   = incrPos xs
incrPos [] = []  -- base case
``````

## List comprehension

``````incrPos l = [x + 1 | x <- l, x > 0]
``````

## Higher order functions

``````incrPos l = map incr (filter isPos l)
where incr x = x + 1
isPos x = x > 0
``````

Shorter, equivalent forms:

``````incrPos l = map (\x -> x+1) (filter (\x -> x>0) l)  -- lambdas
incrPos l = map (+1) (filter (>0) l)                -- slices
incrPos l = map (+1) . filter (>0) \$ l              -- composition
incrPos = map (+1) . filter (>0)                    -- implicit arguments
incrPos = filter (>0) >>> map (+1)                  -- import Control.Arrow
``````

# Variant A

## 1 Divisors

List of divisors of given number, using recursion

``````> divisors 6
[1, 2, 3, 6]
``````
Solution
``````divisors :: Int -> [Int]
where helper cand
| n `mod` cand == 0  = cand : helper (cand+1)  -- is a divisor, keep it
| cand > n           = []  -- candidate incremented up to n
| otherwise          = helper (cand+1)  -- just move to the next candidate
``````

## 2 Odd divisors

List of divisors of given number, using list comprehension

``````> oddDivisors 6
[1, 3]
``````
Solution
``````oddDivisors :: Int -> [Int]
oddDivisors n = [ cand | cand <- [1..n], n `mod` cand == 0, odd cand ]
``````

Bonus using higher order functions:

``````oddDivisors n = filter isOddDivisor [1..n]
where isOddDivisor cand = n `mod` cand == 0 && odd cand

oddDivisors n = filter (\cand -> n `mod` cand == 0 && odd cand) [1..n] -- or with lambdas
``````

## 3 Perfect

Whether given number is perfect (equal to the sum of its divisors except itself), using higher order functions

``````> isPerfect 6
True   -- 6  == 1 + 2 + 3

> isPerfect 10
False  -- 10 \= 1 + 2 + 5
``````
Solution
``````isPerfect :: Int -> Bool
isPerfect n = n == sum properDivisors  -- or just n == sum (divisors n) - n
where properDivisors = filter (\cand -> n `mod` cand == 0) [1..n-1]
``````

## 4 Perfect differences

Whether the sum of differences of consecutive elements is a perfect number

``````> perfDiffs [3, 4, 9]
True   -- [4-3, 9-4] ~> [1, 5] ~> 6

> perfDiffs [1, 5, 8, 20]
False  -- [5-1, 8-5, 20-8] ~> [4, 3, 12] ~> 19
``````
Solution
``````perfDiffs :: [Int] -> Bool
perfDiffs l = isPerfect (sum (consecDiffs l)
where consecDiffs []  = []  -- no elements
consecDiffs [_] = []  -- just one element
consecDiffs (first:second:rest) = second - first : consecDiffs (second:rest)
``````

Bonus using higher order functions:

``````perfDiffs = consecPairs >>> map pairDiff >>> sum >>> isPerfect
where consecPairs l = tail l `zip` l  -- [1, 2, 3] ~> [2, 3] `zip` [1, 2, 3] ~> [(2, 1), (3, 2)]
pairDiff (a, b) = a - b  -- equivalent to pairDiff = uncurry (-)
``````

Composition without `Control.Arrow`:

``````perfDiffs l = isPerfect . sum . map pairDiff \$ consecPairs
where ...  -- same as above
``````

With parentheses:

``````perfDiffs l = isPerfect(sum(map pairDiff consecPairs))
where ...  -- same as above
``````

# Variant B

## 1 Product of differences

Product of the differences between consecutive elements, using recursion

``````> diffsProd [3, 1, 4, 2]
-12  -- [3, 1, 4, 2] ~> (3-1) * (1-4) * (4-2) ~> -12
``````
Solution
``````diffsProd :: [Int] -> Int
diffsProd []  = 1  -- multiplication identity
diffsProd [_] = 1  -- only one element left, can't compute any more differences
diffsProd (first:second:rest) = (first - second) * diffsProd rest
``````

## 2 Signs inside an interval

Signs of numbers in given list that belong inside the interval [-9, 9], using list comprehension

``````> signsInterv [5, 19, -2, 0]
"+-0"
``````
Solution
``````signsInterv :: [Int] -> String
signsInterv l = [sign x | x <- l, isInInterval x]
where sign x
| x > 0     = '+'
| x < 0     = '-'
| x == 0    = '0'
isInInterval x = x >= -9 && x <= 9
``````

Bonus using recursion:

``````signsInterv [] = ""
signsInterv (x:xs)
| isInInterval x   = sign x : signsInterv xs
| otherwise        = signsInterv xs
where ... -- same as above
``````

Bonus using higher order functions:

``````signsInterv = map sign . filter isInInterval

signsInterv = filter isInInterval >>> map sign  -- equivalent
``````

## 3 Vowels in even words

Total number of vowels in words of even length, using higher order functions

``````> evenVowels ["ana", "are", "mere", "si", "pere"]
5  -- ["ana", "are", "mere", "si", "pere"] ~> ["mere", "si", "pere"] ~> ["ee", "i", "ee"] ~> [2, 1, 2] ~> 5
``````
Solution
``````evenVowels :: [String] -> Int
evenVowels = filter (even . length) >>> map onlyVowels >>> map length >>> sum
where onlyVowels = filter isVowel
isVowel = (`elem` "aeiou")
``````

## 4 Prime factors

List of prime factors of given number

``````> primeFactors 315
[3, 3, 5, 7]  -- 315/3 ~> 105/3 ~> 35/5 ~> 7/7 ~> 1
``````
Solution
``````primeFactors :: Int -> [Int]
primeFactors 1 = []  -- 1 has no factors but it is not prime
primeFactors n
| factors == []   = [n]  -- no factors, the number is prime: primeFactors 11 = [11]
| otherwise       = smFact : primeFactors (n `div` smFact)  -- keep the factor continue after we divided by it
where smFact  = head factors  -- smallest factor (if n is divisible by 4 then it is surely divisible by 2)
factors = factors = tail (divisors n) -- divisors except 1, or: facotrs = filter (\d -> (n `mod` d) == 0) [2..n-1]
``````