4 Nov

# Format

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

- recursion
- list comprehension
- higher order functions (map, filter, fold)
- 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]
divisors n = helper 1 -- start with candidate 1
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]
```