BEGIN 16_09_22_TailRecursion_2.lhs

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

We give three examples of functions, which become increasingly
efficient as we transform them into tail-recursive form, using
the method of accumulating parameters. We omit here the CPS
(continuation-passing style) method.

EXAMPLE 1: The "length" function.

Ordinary recursion: 

> len [] = 0
> len (x:xs) = 1 + len xs

Tail recursion, using an accumulating parameter:

> lenAP xs =  help xs 0
>             where
>             help [] n = n
>             help (y:ys) n = help ys (1+n)

##########################################################
BEGIN: Discussion on STRICTNESS vs. NON-STRICTNESS

Haskell is said to be a NON-STRICT language. NON-STRICTNESS is part of what
makes Haskell a LAZY language. Basically, if you need to remember a formula,

   LAZINESS = NON-STRICTNESS + SHARING

What NON-STRICTNESS does is to allow computationally expensive values to be 
passed as arguments to functions without fear of them being computed if they
are not needed. An important example of this are infinite data structures.

What SHARING does is to physically save temporary data in memory, if it appears 
the program uses this data multiple times. It is a way of making laziness more 
efficient. But there is of course the problem of recognizing whether a data is 
indeed used multiple times, or used at all ... this is a difficult problem and 
there is in fact no way of implementing 'absolute sharing' in the sense that, 
for every data defined in the program, 'the data is physically saved IFF the
data is used multiple times'. 

END: Discussion on STRICTNESS vs. NON-STRICTNESS
##########################################################

Tail recursion, using an accumulating parameter and, for more efficiency,
a strict apply in order to override the default non-strictness of Haskell:

> lenAP1 xs = help xs 0
>             where
>             help [] n = n
>             help (y:ys) n = help ys $! (1+n)

Make sure you understand that
'help ys $! (1+n)' is equivalent to '($!) (help ys) (1+n)'

EXAMPLE 2: The "add" function (also called "sum" in Prelude.hs).

Ordinary recursion: 

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

Tail recursion, using an accumulating parameter:

> addAP xs =  help xs 0
>             where
>             help [] n = n
>             help (y:ys) n = help ys (y+n)

Tail recursion, using an accumulating parameter and, for more efficiency,
a strict apply:

> addAP1 xs = help xs 0
>             where
>             help [] n = n
>             help (y:ys) n = help ys $! (y+n)

EXAMPLE 3: The "mean" function.

Ordinary recursion: 

> mean xs = (add xs) / (len xs)

Tail recursion, using two accumulating parameters, 
one in addAP and one in lenAP:

> meanAP xs = (addAP xs) / (lenAP xs)

Tail recursion, using two accumulating parameters and two instances
of the strict apply $!, once in addAP1 and once in lenAP1:

> meanAP1 xs = (addAP1 xs) / (lenAP1 xs)

Tail recursion, using two accumulating parameters and two instances
of the strict apply $! -- just as in "meanAP1" -- but processing input 
list xs only once (not twice):

> meanAP2 xs = help xs 0 0
>              where
>              help [] m n = m / n
>              help (y:ys) m n = (help ys $! (y+m)) $! (1+n)

Tail recursion, using two accumulating parameters and two instances
of the strict apply $! -- just as in "meanAP1" and "meanAP2" -- but 
NOT processing any input list xs:

> meanAP3 m n = help m 0 0
>               where
>               help x y z 
>                 | x > n      = y / z
>                 | otherwise  = (help (x+1) $! (x+y)) $! (1+z)

CAVEAT: "meanAP3" is restricted in the kind of inputs "m" and "n"
on which it is equivalent to "mean" (as well as "meanAP", "meanAP1", 
and "meanAP2"). "meanAP3 m n" is equivalent to "mean [m..n]".

END 16_09_22_TailRecursion_2.lhs