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]
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]