{-
 * Uppsala University - 2017 Fall
 * Program Design and Data Structures, 1DL201
 * Exam 2015-12-18, attempted solutions
 * Copyright 2017 Henrik Alfken(Schulze)
-}
{- rev acc xs
  PRE:  ?PRE?     -- Q 03
  POST: ?POST?    -- Q 04
  EXAMPLES:
    rev [1,2] [3,4]
      == [4,3,1,2]  -- Q 01
-}
-- rev :: [a] -> [a] -> [a]   -- Q 02     :t rev
-- VARIANT: length xs
rev acc [] = acc
rev acc (x:xs) = rev (x:acc) xs


{- Question 1: What is the value of rev [1,2] [3,4] ?
  A [3,4,1,2]    B 10    C [1,2,3,4]    D [4,3,1,2]    E [4,3,2,1]
Answer: D.
  rev [1,2] [3,4] --> rev (3:[1,2]) [4] --> rev (4:3:[1,2]) [] --> [4,3,1,2] = :D
-}


{- Question 2: What is the type (?TYPE?) of rev?
  A [a] -> [b] -> [a]    B [a] -> [a] -> [a]    C ([a],[b]) -> [a]
  D [a] -> [a]           E Int -> Int -> Int
Answer: B   - In GHCi, type <:t rev>
-}


{- Question 3: What is the most appropriate precondition (?PRE?) for rev?
  A True    B False    C acc and xs are lists    D xs is non-empty    E acc is empty
Answer: A? - Isn't E more 'appropriate'? Isn't the purpose of rev to REVerse a list?
-}


{- Question 4: What is the most appropriate postcondition (?POST?) for rev?
  A a non-empty list                        B xs in reverse order
  C xs in reverse order, followed by acc    D True
  E rev applied to (i) the head of xs prepended to acc, and (ii) the tail of xs
Answer: C? - Really? Or B? The answer to this question depends on how you answered Q3!
-}


{- Question 5: Which of the following is a variant (?VARIANT?) for the function rev?
  A length acc    B length xs    C length acc + length xs    D acc == xs    E 0
Answer: B
-}


{- Question 6: The syntax of a programming language ...
  A is usually specified only informally, e.g., in English.
  B describes how expressions in that language are evaluated.
  C defines what combinations of symbols constitute valid programs.
  D defines the meaning of programs.
  E defines the data types and operations that are available in the language.
Answer: C
  The syntax defines the 'grammar' for the programming language. Code that violates
  the rules of the grammar cannot be a valid program. Mr Compiler will complain!
  https://en.wikipedia.org/wiki/Syntax_%28programming_languages%29
-}


{- Question 7: Consider the following text:
  fQ07 x = length x + (x `div` 0)
Compiling this with a Haskell compiler will result in ...
  A a run-time error.    B a type error.    C Infinity    D a syntax error.    E none of these.
fQ07 x = length x + (x `div` 0)
  Running the above line in GHCi gives a type error:
  PKD-2015-12-18.hs:73:22: error:
      • Couldn't match expected type ‘Int’ with actual type ‘t a’
      • In the second argument of ‘(+)’, namely ‘(x `div` 0)’
        In the expression: length x + (x `div` 0)
        In an equation for ‘fQ07’: fQ07 x = length x + (x `div` 0)
      • Relevant bindings include
          x :: t a (bound at PKD-2015-12-18.hs:73:6)
          fQ07 :: t a -> Int (bound at PKD-2015-12-18.hs:73:1)
    |
  73 | fQ07 x = length x + (x `div` 0)
    |                      ^^^^^^^^^
Answer: B a type error.
-}


{- Question 8: Which of the following patterns does NOT match the value (1, [2,3]) ?
  A (_, [2,x])    B (1, [x])    C _    D (1, [2,3])    E (1, x)
Answer: B - the second tuple element, [x], is a list containing only one element.
  (1, [x]) = (1, [2,3])

  A
    (_, [2,x]) = (1, [2,3])     -- ?
    x   -- x == 3
  B
    (1, [x]) = (1, [2,3])       -- ?
    x
*** Exception: <interactive>:15:5-25: Irrefutable pattern failed for pattern (1, [x]) --> B!
  C
    _ = (1, [2,3])              -- ?
    -- OK!
  D
    (1, [2,3]) = (1, [2,3])     -- ?
    -- True
  E
    (1, x) = (1, [2,3])         -- ?
    x   -- x == [2,3]
-}


{- Question 9: Consider the function
  fQ09 x | x<1 = let x=2 in case x*x of x -> x
What is the value of
let x=0 in fQ09 x -- ?
  A 0     B 1     C 2     D 4     E None of these.
Answer: D 4
-}
{- fQ09 x
  PRE:  -
  POST: 4 if x < 1, otherwise ERROR due to 'Non-exhaustive patterns'
  EXAMPLES:
    let x=0 in fQ09 x
      == 4
    fQ09 0
      == 4
    fQ09 (-42)
      == 4
    fQ09 1
*** Exception: PKD-2015-12-18.hs:128:1-44: Non-exhaustive patterns in function fQ09
-}
-- Rewrite the function to make it less confusing to read:
fQ09 x | x<1 = let y=2 in case y*y of z -> z


{- Question 10: Recall the quicksort algorithm. Suppose the algorithm is applied to
the input list [6,8,3,11,0,8,2,9] and the value 6 is chosen as the pivot. What
are the arguments to the immediate recursive calls of the quicksort algorithm?
  A [3,0,2] and [8,11,8,9]    B 6 and [8,3,11,0,8,2,9]    C [6,8], [3,11], [0,8] and [2,9]
  D [8,3,11] and [0,8,2,9]    E [0,2,3] and [8,8,9,11]
Answer: A
-}


{- Question 11: Which of the following expressions is NOT polymorphic?
  A []     B (&&)     C map     D (.)     E snd
Answer: B, because it requires booleans as operands.
-}


{- Question 12: Which of the following expressions, when applied to an argument of
the correct type, does NOT necessarily return the argument value unchanged?
  A (1-) . (1+)     B \x -> x     C map id
  D filter (\ -> True)     E let f xs = [x|x <- xs] in f
Answer: A, true only if the operand is zero (0).
        D is ALSO a correct - results in a 'parse error'
          and therefore can NEVER return the argument value unchanged.
( Did the constructor of this exam question forget to double-check with GHCi? )
Examples:
  A
    ((1-) $ (1+) 42)
      == -42
  B
    (\x -> x) 42
      == 42
  C
    map id [42]
      == [42]
  D
    filter (\x -> True) [42]  -- NOTE the missing 'x' in the question!
      == [42]
  E
    let f xs = [x|x <- xs] in f [42]
      == [42]
-}


{- Question 13: What is the value of foldl (-) 10 [3,2,1] ?
  A -8     B 10     C 4     D 0     E -10
Answer: C   -- See definition at:    https://wiki.haskell.org/Fold
foldl f z (x:xs) = foldl f (f z x) xs -- by definition, so with f=(-), z=10, x=3, xs=[2,1]
    foldl (-) 10 [3,2,1] = foldl (-) ((-) 10 3) [2,1]
  = foldl (-) 7 [2,1] = foldl (-) ((-) 7 2) [1]
  = foldl (-) 5 [1] = foldl (-) ((-) 5 1) []
  = foldl (-) 4 [] = 4                        -- This is the base case!
In short, foldl (-) 10 [3,2,1] = ((10 - 3) - 2) - 1 = 4,
which means that the list [3,2,1] is traversed from Left to right: 3, 2, 1.

As an extra exercise, do note that:    foldr (-) 10 [3,2,1] does not give the same answer!
foldr f z (x:xs) = f x (foldr f z xs) -- by definition, so with f=(-), z=10, x=3, xs=[2,1]
    foldr (-) 10 [3,2,1]
  = (-) 3 (foldr (-) 10 [2,1])
  = 3 - ((-) 2 (foldr (-) 10 [1]))
  = 3 - (2 - ((-) 1 (foldr (-) 10 []))    -- foldr (-) 10 [] = 10 according to the base case!
  = 3 - (2 - (1 - (10)))
  = 3 - (2 - (1 - 10))
  = 3 - (2 - (-9))
  = 3 - (11)
  = 3 - 11
  = -8
In short, foldr (-) 10 [3,2,1] = 3 - (2 - (1 - 10)) = -8,
which means that the list [3,2,1] is traversed from Right to left: 1, 2, 3.
-}


{- Question 14: Which is the most precise bound for the function 
                n^5 + 1000n^4 + 3n^3 + n^3·log n?
  A Ω(n^4)     B O(n^4)     C Θ(n^3·log n)     D O(n^5)     E Θ(n^5)
Answer: E, the function is bounded from above by O(n^5) and from below by Ω(n^5).
-}


{- Question 15: What is the closed form of the following recurrence?
      T(0) = 10
      T(n) = T(n − 1) + 5n + 6
  A T(n) = 11n + 10       B T(n) = 5n^3 + 6n + 10      C T(n) = 5n·log n + 16
  D T(n) = 5n(n+1)/2 + 6n + 10      E T(n) = 5(2^n) + 6n + 10
Answer: D, see below!

Substitution method:
  T(0) = 10
  T(1) = 10 + 5·1 + 6
  T(2) = (10 + 5·1 + 6) + 5·2 + 6
  T(3) = ((10 + 5·1 + 6) + 5·2 + 6) + 5·3 + 6
  T(4) = (((10 + 5·1 + 6) + 5·2 + 6) + 5·3 + 6) + 5·4 + 6
  ...
  T(k) = 10 + 5·(1+2+3+4+...+k) + k·6
  ...
  T(n) = 10 + 5·(1+2+3+4+...+n) + 6n = 10 + 5n·(n+1)/2 + 6n
       = (5/2)n^2 + (17/2)n + 10                                                □

Expansion method:
  T(n) = T(n−1) + 5n + 6
       = (T(n-2) + 5·(n-1) + 6) + 5n + 6
       = ((T(n-3) + 5·(n-2) + 6) + 5·(n-1) + 6) + 5n + 6
       = (((T(n-4) + 5·(n-3) + 6) + 5·(n-2) + 6) + 5·(n-1) + 6) + 5n + 6
       = T(n-4) + 5·(n-3) + 6 + 5·(n-2) + 6 + 5·(n-1) + 6 + 5n + 6
  ...
       = T(n-k) + 5·(n-k+1) + 6 + ... + 5·(n-2) + 6 + 5·(n-1) + 6 + 5n + 6
  ... Let k=n:
       = T(n-n) + 5·(n-n+1) + 6 + ... + 5·(n-2) + 6 + 5·(n-1) + 6 + 5n + 6
       = T(0) + 5·(1) + 6 + ... + 5·(n-2) + 6 + 5·(n-1) + 6 + 5n + 6
       = T(0) + 5·(1+2+3+4+...+(n-2)+(n-1)+n) + n·6
       = 10 + 5n·(1+n)/2 + 6n = (5/2)n^2 + (17/2)n + 10                         □
Same answer with both methods! Isn't that nice? (:-)
Expanding answer D:       5n(n+1)/2 + 6n + 10 = (5/2)n^2 + (17/2)n + 10         □
-}


{- Question 16: Recall that O(g(n)), Θ(g(n)) and Ω(g(n)) actually represent sets of
functions related in the appropriate way to g(n). What is the relationship between
O(g(n)), Θ(g(n)) and Ω(g(n))?
  A Ω(g(n)) ⊆ Θ(g(n)) ⊆ O(g(n))     B Ω(g(n)) ∩ O(g(n)) = Θ(g(n))
  C O(g(n)) ⊆ Θ(g(n)) ⊆ Ω(g(n))     D O(g(n)) = Ω(g(n)) ∪ Θ(g(n))
  E No relationship.
Answer: B, the definition of g(n)∈Θ(g(n)) is that g(n)∈Ω(g(n)) AND g(n)∈O(g(n)),
  or equivalently that g(n) ∈ Ω(g(n)) ∩ O(g(n)).
-}


{- Question 17: Use the Master Theorem to find a closed form for the following
recurrence:
T(n) = 2^n·T(n/2) + n^n .
The closed form is:
  A Θ(n^2n).     B Θ(n^n).     C Θ(2^n).     D Θ(n^n·log n).
  E The Master Theorem does not apply.
Answer: E. See page 1. In the Master Theorem, the coefficient in front of T(n/b)
          should be a constant independent of n, but is in this question 2^n.
-}


{- Question 18: Consider the following recurrence:
    T(0) = Θ(1)
    T(1) = Θ(1)
    T(n) = T(n − 1) + T(n − 2) + Θ(1)
  Which of the following Haskell functions’ runtime function is given by this recurrence?
Answer: A. T(n−1) is missing in E. T(n−2) is missing in B, C, and D.
-}
-- A
golf [] = 0
golf [a] = a
golf (a : b : as) = a + golf (b:as) + golf as
-- B
dog [] = 0
dog [a] = a
dog l = dog left + dog right + 1
  where
    (left, right) = split l
    split l = let n = length l `div` 2 in (take n l, drop n l)
-- C
zig [] = 1
zig (a : as) = a - zag as
zag [] = 0
zag (a : as) = a + zig as
-- D
foo [] = []
foo (a : as) = [a] : foo as
-- E
bar [] = 0
bar [a] = a
bar (a : _ : as) = a + bar as


{- Question 19: You are required to implement a function, but are not 100% sure
how to do it. You recall the design technique called dodging, which can help simplify
your task. Which of the following is NOT an example of a dodge?
  A Implement a function that returns a fixed value.
  B Implement a function that only works for some input values.
  C Implement a function that ignores boundary conditions.
  D Use an obvious but inefficient algorithm.
  E Implement all code within a single function.
Answer: E.

See the lecture slides '27-28-Design.pdf', pp 17, 18, 65-72. Page 17:
    "Dodging Solve a simpler problem: helps get working code quicker, gives insight
    about more general problem"
  Definition on page 66:
    "Often the best way to solve a problem is to solve a simpler problem first
    — reducing complexity! This is called dodging."
  Examples on page 68:
  " · solve for a specific value/set of values
    · constraining a parameter value
    · constraining the type — make it less polymorphic (or more)
    · ignore tricky boundary conditions
    · make function do simpler calculation (which may only be correct for some values)
    · use terrible algorithm, but one that works.
    · make function return a typical value, rather than do required calculation"
-}


{- Question 20: Which is NOT one of the purposes of the Function Examples step of
the 8 Step Design Process?
  A To describe the data types used in the program.
  B To understand better how the function works.
  C To provide valid inputs to the function.
  D To provide some test cases.
  E To provide expected outputs from the function.
Answer: A.

See the lecture slides '27-28-Design.pdf', pp 15-22 and pp 51-53.
  The 8 Step Design Process is on pp 21 and 25:
    1A. Data Description
    1B. Data Examples
    2. Function Description (Signature/Purpose/Header)
    3. Functional Examples
    4. Function Template
    5. Code
    6. Tests
    7. Review & Refactor
The lecture slides '27-28-Design.pdf', page 19:
  "Function Examples show examples of what happens when the function is finished"
The lecture slides '27-28-Design.pdf', page 20:
  "Function Examples gives a deeper understanding and exposes specification issues"
-}