LGA-02: Functional Progamming

Note

This LGA has many parts, but each part need only be completed twice (for redundancy) when considering your group as a whole. Before you leave class, make sure to split up the work. The work should be split so that everyone has a equivalent number of questions to do.

  1. Answer these questions about referential transparency:

    1. Research the term and create your own definition for referential transparency. Make sure your definition makes sense to someone who has only ever programmed in C++ before.
    2. Provide an example C or C++ function that is not referentially transparent (and don’t just copy-paste the one from Wikipedia).
    3. What is memoization? How does referential transparency allow memoization?
    4. How does referential transparency allow you to prove functions correct?
  2. Answer these questions about eager vs. lazy evaluation:

    1. Research the term. Create your own definition of each, and prepare to explain the difference to your learning group.
    2. How does lazy evaluation allow for lists of infinite length?
    3. Under what circumstances might the result of a lazy evaluation differ from the results of a eager evaluation? Can you provide an example (any language, or even pseudocode, will do)?
  3. Haskell is a statically typed language, but it is not always necessary to write the type in the code. Answer these questions about static typing with type inference:

    1. What is type inference? Bring a really simple example that shows how type can be inferred.
    2. Why is static typing with type inference not dynamic typing? Use the definitions from lecture to explain your answer.
    3. What are some of the limitations of static typing with type inference? Provide an example that could be completed under dynamic typing, but not using static typing with type inference.
  4. Answer these questions about currying:

    1. What is currying? Create your own definition, and make sure it makes sense to someone who may have never written a computer program and only has high school level algebra (you may need to give an example, in terms of mathematics).

    2. What is partial application of a function? How does currying make partial application simple?

    3. Using any imperative language which supports treating functions as data (e.g., JavaScript, Python, PHP, etc.), write the following function as a curried function. In other words, you should be able to call \(f(a, b, c)\) as \(f(a)(b)(c)\):

      \[f(a, b, c) = 2a^3 + b^2 - 3c + 4\]
  5. Consider the following function, defined mathematically. \(f\) is a function which takes two arguments and produces one of the same type, and \(l = l_1,\ldots,l_n\) is a list of \(n\ (n > 1)\) elements of that type.

    \[\begin{split}q(f, l) = \begin{cases} f(l_1, l_2) & \mbox{if } n = 2 \\ f(l_1, q(f, l_2\ldots{}l_n)) & \mbox{otherwise} \\ \end{cases}\end{split}\]

    What function \(f\) should be used so that this function will sum a sequence of numbers? How about for product?

  6. Read Chapters 1 and 2 of LYH and prepare a tutorial for your learning group on how to use GHCi to preform simple arithmetic, load a Haskell file, and reload the current script.