++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Recursion

Functional languages prefer recursion over iteration.

Assume the following functions are available:

> inc n = n + 1
> dec n = n - 1

1. Give a recursive definition for an add function
that adds two integers. Your definition should only
use inc and dec.

2. Give a recusive definition for a mul (multiply)
function. Your definition should only use inc, dec,
and add.


3. Give a recursive definition for an exp2 (exponentiation
base 2) function. Your function should only use mul, add,
inc, and dec.

4. Using only the previously defined functions, give a 
recursive definition for hyperExp, where

   hyperExp n = 2^(2^(2^(... 1 ...))) n times
   
Unfortunately, this will probably cause a stack overflow
each time it's called.
   
5. Implmement a function called compose. This function
takes two inputs, an unsigned integer and a function f
of type:

   f:: Int->Int
   
Basically, compose n f computes:

   f(f(f(... f(1) ...))) n times

For example, assume the following definition:

> add3 n = n + 3

then

   compose 9 add3
   28
   compose 1 add3
   4
   compose 0 add3
   1

6. Implement a recursive function called m2n which takes
two integer inputs and generates a list of
consecutive integers starting with m and ending with n:

   [m m+1 m+2 ... n]

If n < m, then this function returns [].

For example:

   m2n 3 12
   [3,4,5,6,7,8,9,10,11,12]


7. Implement a recursive function called allPass that 
expects two inputs,a function of the form:

   test: t -> Boolean
   
and a list of type [t]. This function returns True if each
member of the list passes the test, and False otherwise.

For example:

   allPass even [2, 4, 6, 8]
   True
   allPass even [2, 4, 6, 8, 9]
   False


8. Implement a recursive function called somePass that 
expects two inputs, a function of the form:

   test: t -> Boolean
   
and a list of type [t]. This function returns True if some
member of the list passes the test, and False otherwise.

For example:

   somePass even []
   False
   somePass even [1, 3, 4, 5, 7]
   True

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Iteration, Tail Recursion, State, and Dynamical Systems

We can fake iteration using tail recursion: a recursive 
call that comes at the end of the function. Many languages
optimize tail recursion so that it reuses the same stack
frame instead of growing the stack.

A discrete dynamical system (DDS) has four components:

   1. a current state from some state space: S
   
   2. an update function of type:
   
      update:: S -> Int -> S
         where
         update s n = next state of the DDS
      
   3. a halting function of type:
   
      halt:: S -> Int -> Boolean
         where
         halt s n = True when/if system reaches 
         a final state
   
The integer parameter is called the cycle number. It tells
us how many times the update function has been called.

Finally, a DDS needs a control loop that iterates update and
increments cycle until a final state is reached (which may
never happen).

> controlLoop state cycle halt update
>   | halt state cycle = state
>   | otherwise = controlLoop newState (cycle + 1) halt update
>   where
>      newState = update state cycle

The interesting thing about this definition is that the concept
of a state that changes over time doesn't make sense in a
functional language where updatable variables that might hold
state information don't exist. Our definition gets around this
by using a parameter to hold the current state of the system.

For example, a pond of amoebas is a DDS. The current
state is the size of the population. Amoebas reproduce 
by splitting in two. Assume all amoebas in a pond split 
in two at the same time. Thus, the update function is
simply the doubling function. The DDS halts after
a specified number of cycles. The following function
predicts the size after a number of splitting cycles:

> population cycles
>   = controlLoop 1 0 halt double
>   where
>     halt state cycle = cycles <= cycle
>     double size cycle = size * 2

To show how useful this idea is, we can think of a problem
such as "find a root of a function f" as a DDS. The current
state of this system is our current guess at the answer. The
update function uses Newton's approximation technique, and we
halt the system when our guess is good enough:

> solve f 
>   = controlLoop 1 0 goodEnuf improve
>   where
>      goodEnuf guess c  = abs(f(guess)) < delta
>      -- our error tolerance:
>      delta = 1.0e-5
>      improve guess c = guess - f(guess)/df(guess)
>      -- approximating the derivative of f:
>      df x = (f(x + delta) - f(x))/delta

We can use this function to solve many problems. For
example, here's the square root function:

> squareRoot x
>   = solve f
>   where
>      f y = y * y - x

9. Use the solve function to implement an n-th root
function. For example:

   root 3 64
   4.0
   root 2 64
   8.0
   root 5 32
   2.0

10. An investment is a DDS. The current state is
the current value of the investment. The update
function adds the interest earned in a cycle to 
the value. The DDS halts when the number of cycles 
reaches the term of the investment. For example,
here's the future value of an investment of $1000
earning an interest rate of 2% per cycle (month, day,
year, etc.) that matures after 12 cycles:

   futureValue 1000 0.02 12
   1268.24
   
Use the control loop to implement futureValue.

11. In theory, any recursive function can be converted
into a tail recursive function. For example, here's a
tail recursive version of the factorial function:
      
> fact n
>   = helper 1 n
>      where
>       helper k 0 = k
>       helper k m = helper (k * m) (m - 1)

Find a tail recursive version of the hyperExp function.
You may use the built-in exponential function.
   
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Algebraic Types

Assume 3 dimensional vectors are defined as follows

> data Vector = Vec Float Float Float

> showVec (Vec a b c) 
>    = "(" ++ show a ++ ", " ++ show b ++ ", " ++ show c ++ ")"

12. Implement functions for:

   12.1. Adding 2 vectors
   12.2. Subtracting 2 vectors
   12.3. Multiplying a vector times a scalar
   12.4. Computing the dot product of 2 vectors
   12.5. Computing the cross product of two vectors.
   12.6. Computing the length of a vector.
   12.7. Determining if 2 vectors are equal.
 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Lists and Streams

A stream is an infinitely long list, which is implemented as:

   (head: lambda(){I promise to compute the tail later})
   
Assume the following definitions are given:

intStream = [0, 1,, 2, 3, ... ]:

> fromN n = n: fromN(n + 1)
> intStream = fromN 0

nth stream n = item at position n of stream:

> nth [] _ = error "empty stream has no elements"
> nth (h:t) 0 = h
> nth (h:t) n = nth t (n - 1)

13. Define the infinite stream of squares using
intStream and map:

   [0, 1, 4, 9, 16, ... ]
   

14. Define the infinite stream of even numbers 
from scratch, without using intStream or map.

> evenStream = evensFromN 0

15. Define the infinite stream of odds using intStream 
and filter.