BEGIN 16_09_22_TailRecursion_1.lhs

###########################################################
CS 320 
22 September 2016
FROM GENERAL RECURSION TO TAIL RECURSION (PART 1)
##########################################################

Tail-recursive definitions are generally preferred over other forms
of recursive definitions, because they can be implemented more
efficiently (obviating the need of saving so-called "activation
records", also called "stack frames", on the runtime stack). This
is a general rule, but there are exceptions -- see, for example,
Example 3 below (the "split" function).

There are methods for transforming arbitrary recursive definitions
into tail-recursive form. We give a glimpse of some techniques, by examples.

EXAMPLE 1: The "sum" function.

The "sum" function is already in Prelude.hs. Here it is again as "mySum":

> mySum [] = 0
> mySum (x : xs) = x + mySum xs

We transform "mySum" into tail-recursive form by using a technique known
as "accumulating-parameter style" (APS):

> mySumA lst = mySumAP lst 0 
>     where 
>     mySumAP [] n = n
>     mySumAP (x : xs) n = mySumAP xs (n + x)

Another technique for transforming "mySum" into tail-recursive form is
known "continuation-passing style" (CPS), of which there are many 
variations. Here is one way of writing "mySum" in CPS:

> mySumB lst = mySumCPS lst (\ x -> x)
>     where
>     mySumCPS [] k = k 0
>     mySumCPS (x : xs) k = mySumCPS xs (\ n -> k (x + n))

> mySumC lst = foldr (+) 0 lst

BEGIN DISCUSSION

On a first reading you can skip this discussion -- it is demanding!!

Let's compare these three approaches carefully.  The first program, given
an input list of n integers, will call itself recursively n times.  On the
way down, it does not do any additions, but only remembers the left
argument of the + , and also remembers that an addition must be performed
after the sum of the tail has been calculated. This is called a deferred
operation. It then calls itself recursively on the tail of the input list.
The program continues to call itself recursively on successive tails,
remembering all the deferred operations and the left-hand-sides of + on the
runtime stack, until it gets to the empty list, at which point it returns
0.  Thereafter, on the way back up out of the recursion, at each level it
performs the deferred addition and returns the result to its caller.  Thus
on input [x_1,x_2,...,x_p], the elements are added in the order

   (x_1 + (x_2 + (... + (x_{p-1} + (x_p + 0))...))),

from right to left.

In the second version, i.e. "mySumA", we define an auxiliary function
"mySumAP" that takes an extra argument n, an accumulated result. The 
initial value of the accumulated result that is passed to the auxiliary 
function "mySumAP" on the first call is the basis element 0. Thus the 
elements are added in the opposite order:

   (((...((0 + x_1) + x_2) + ...) + x_{p-1}) + x_p),

from left to right.  Luckily in this case, addition is associative, so the
order of additions doesn't matter, and we will get the same result. We
would not be so fortunate if we tried to do the same thing with a
nonassociative operation such as exponentiation or (:).

The third version, i.e. "mySumB", is a mixture of both: carry out
the operations from right to left, but with no deferred operations. This is
done using "continuations". Since we have first-class functions, we can
create a function that packages up any such deferred operations, then
passes it down in the recursive call for somebody else to perform. In this
example, the auxiliary function "mySumCPS" takes a continuation function as
an extra argument, which consists of all the deferred operations 
accumulated so far. Before the next recursive call, the deferred addition
is composed with the previously accumulated ones in the correct order, and
this new continuation function is passed down in the next recursive call.
At the bottom of the recursion, all the deferred operations that were
accumulated on the way down are performed all at once by applying the
continuation to the basis element 0.

The initial call to "mySumCPS" passes the identity function (\ x -> x),
which is the identity element for the operation of function composition.
On the way down, the operation of adding the new element x is composed with
the passed-in continuation k consisting of all deferred additions
accumulated so far, giving a new continuation (\ n -> k (x + n)).  Note
that this is equivalent to "k . (\ n -> x + n)", i.e., the composition of k
and (\ n -> x + n), with (\ n -> x + n) applied first and k applied second.

Thus at the bottom of the recursion on input [x_1,x_2,...,x_p], we have a
function that is equivalent to the composition of p+1 functions:

(\ x -> x) . (\ n -> x_1 + n) . (\ n -> x_2 + n) . ... . (\ n -> x_p + n)

Function composition is a binary operation that is associative, i.e.,
(f . g) . h = f . (g . h) and the parentheses are superfluous. We omit 
all superfluous parentheses for clarity. Applying the preceding function 
to 0 gives: 

   (x_1 + (x_2 + (... + (x_{p-1} + (x_p + 0))...))),

which is the same sum calculated in the same order as in the first version.

END DISCUSSION

EXAMPLE 2: The 3*x + 1 Problem

The 3*x+1 problem refers to the following iteration.  Given a positive
integer x:

   if x is even, divide it by 2 
   if x is odd, multiply it by 3 and add 1. 
   repeat forever. 

This process eventually ends up in the cycle 1 -> 4 -> 2 -> 1 for all x 
that anyone has every tried, but no one has yet been able to prove that
this occurs for all x. 

Here are three programs that perform this iteration, returning the sequence
of integers produced along the way until 1 is encountered.  These three
programs correspond to the three versions of "sum" above: ordinary
recursion, tail recursion using APS, and tail recursion using CPS.

Ordinary (or direct-parameter passing) recursion:

> foo x 
>     | x == 1      = [1] 
>     | even x      = x : foo (x `div` 2) 
>     | odd x       = x : foo (3 * x + 1)

Tail-recursion, using accumulating-parameter style:

> fooA (x,a) 
>     | x == 1       = a ++ [1]
>     | even x       = fooA (x `div` 2, a ++ [x])
>     | odd x        = fooA (3 * x + 1, a ++ [x])

"fooA" is activated by evaluating "fooA (x,[])".

Tail-recursion, using continuation-passing style:

> fooB (x,k) 
>     | x == 1        = k [1]
>     | even x        = fooB (x `div` 2, \ a -> k (x : a))
>     | odd x         = fooB (3 * x + 1, \ a -> k (x : a))  

"fooB" is activated by evaluating "fooB (x,\ x -> x)".
 
BEGIN DISCUSSION

Note that foo and fooB can use (:), a constant-time operation, whereas the
tail-recursive version fooA uses the linear-time (++).  This is because of 
the associativity issues discussed above.  We could fix this by producing 
the list in the opposite order and then reversing it at the end, but this 
is not the point.

END DISCUSSION

EXAMPLE 3: The "split" function, which splits an input list into two
equal sublists.

The definition of "split" which we recommend in order to avoid having
to compute the length of the input list is the following. "split" uses
two help functions, "evens" and "odds", neither of which is
tail-recursive:

  evens [] = []
  evens [x] = [x]
  evens (x:_:xs) = x : evens xs

  odds [] = []
  odds [x] = []
  odds (_:x:xs) = x : odds xs

  split xs = (evens xs, odds xs)

We can re-write this definition in order to make "evens" and "odds"
local rather than global:

> split xs = (evens xs, odds xs)
>      where
>      evens []       = []
>      evens [x]      = [x]
>      evens (x:_:xs) = x : evens xs ;
>      odds []        = []
>      odds [x]       = []
>      odds (_:x:xs)  = x : odds xs

Following the (simpler) APS and CPS transformations for
functions "mySum" (in Example 1) and "foo" (in Example 2),
we can try to transform "split" to put it in tail-recursive
form.

First, in accumulating-parameter style, we obtain:

> splitAPS lst = splitAPS' lst ([],[])
>     where
>     splitAPS' [] (evenLoc,oddLoc)        = (evenLoc,oddLoc)
>     splitAPS' [x] (evenLoc,oddLoc)       = (x:evenLoc, oddLoc)
>     splitAPS' (x:x':xs) (evenLoc,oddLoc) = 
>                splitAPS' xs (x:evenLoc, x':oddLoc)

Second, in continuation-passing style, we obtain:

> splitCPS lst = splitCPS' lst (\ (lst1,lst2) -> (lst1,lst2))
>     where
>     splitCPS' [] k        = k ([],[])
>     splitCPS' [x] k       = k ([x],[])
>     splitCPS' (x:x':xs) k = 
>                splitCPS' xs (\ (lst1,lst2) -> k (x:lst1,x':lst2)) 

EXERCISE 1: Evaluate each of the following expressions and explain
the differences in the outputs:

  head (fst (split [10..25]))
  head (fst (splitAPS [10..25]))
  head (fst (splitCPS [10..25]))

EXERCISE 2: Evaluate each of the following expressions and explain
the differences in their behaviors:

  head (fst (split [10..]))
  head (fst (splitAPS [10..]))
  head (fst (splitCPS [10..]))

END 16_09_22_TailRecursion_1.lhs