[Haskell-beginners] Re: Understanding recursion in Haskell.

[7stud]

Caitlin <The_Polymorph <at> rocketmail.com> writes:
> As a Haskell beginner, I was wondering if someoneone could explain how 
>the following programs function
> 
>maximum' :: (Ord a) => [a] -> a  
>maximum' [] = error "maximum of empty list"  
>maximum' [x] = x  
>maximum' (x:xs)   
>    | x > maxTail = x  
>    | otherwise = maxTail  
>    where maxTail = maximum' xs

I'm a beginner too.  Let's say you call:

maximum' [1, 2, 4]

First of all, a list like [1, 2, 4] is actually of the form 1:2:4:[].
So you are really calling:

maximum' 1:2:4:[]

That function call matches the pattern in this definition:

maximum' (x:xs)   
    | x > maxTail = x  
    | otherwise = maxTail  
    where maxTail = maximum' xs

Lining up the function call with the function definition:

maximum' (x:xs)
maximum'  1:2:4:[]

gives x = 1 and xs = 2:4:[].  Then the first condition("guard") in the 
function definition is examined:

| x > maxTail         = x

Because x = 1, the guard is equivalent to:

| 1 > maxTail         = 1

So is 1 greater than the value of maxTail?  What is the value of maxTail?  
maxTail is defined here:

maxTail = maximum' xs

Hmmm...that is starting to get confusing.  At this point, I draw a
diagram: 

maximum' 1:2:4:[]
 | 1 > maxTail  = 1
       [     ]--------> maximum' xs
 | otherwise maxTail

The blank([   ]) represents the value of maxTail. From above, you know 
that xs is 2:4:[], giving you:

maximum' 1:2:4:[]
 | 1 > maxTail  = 1
       [     ]--------> maximum' 2:4:[]
 | otherwise maxTail

Ok, so to figure out the value of maxTail, you have to figure out the value
of: 

maximum' 2:4:[].  

That function call matches the pattern in this definition:

maximum' (x:xs)   
    | x > maxTail = x  
    | otherwise = maxTail  
    where maxTail = maximum' xs

Lining up the function call with the function definition:

>maximum' (x:xs)
 maximum'  2:4:[]

gives x = 2 and xs = 4:[].  Then the first condition("guard") in 
the function definition is examined:

maximum' (x:xs)
    | x > maxTail = x
    | otherwise = maxTail
    where maxTail = maximum' xs

So is 2 greater than the value of maxTail?  What is the value of 
maxTail?  Uh oh, here we go again.  maxTail is defined here:

maxTail = maximum' xs

and this time xs = 4:[].  Time to update the diagram:

maximum' 1:2:4:[]
 | 1 > maxTail  = 1
       [     ]----------> maximum' 2:4:[]
 | otherwise maxTail       | 2 > maxTail   = 2                     
                                 [     ]---------> maximum' 4:[]
                           | otherwise maxTail

Now comes the fun part.  What is maximum' 4:[]? That function call 
matches one of the other definitions for maximum', this one:

maximum' [x] = x

That definition is the same as:

maximum' x:[] = x

Lining up the function call with the definition:

maximum' x:[] = x
maximum' 4:[]

Looking at the pattern in the function definition, you should be
able to see that x = 4, and therefore maximum' 4:[] = 4. 
Substituting 4 into right hand side of the current diagram:

maximum' 1:2:4:[]
 | 1 > maxTail  = 1
       [     ]----------> maximum' 2:4:[]
 | otherwise maxTail       | 2 > maxTail   = 2                     
                                 [     ]------------> 4
                           | otherwise maxTail


Ah ha!  Now we have a value for one of the blanks:  

maximum' 1:2:4:[]
 | 1 > maxTail  = 1
       [     ]----------> maximum' 2:4:[]
 | otherwise maxTail       | 2 > maxTail   = 2                     
                                 [  4  ]
                           | otherwise maxTail

Remember that a blank represents the value of maxTail above it.
Now you can answer the question: is 2 > 4?  That is false, so you 
look at the second guard condition:

| otherwise maxTail

That just returns the value of maxTail, which is 4.  That means the 
value of maximum' 2:4:[] is 4.  Updating the diagram:

maximum' 1:2:4:[]
 | 1 > maxTail  = 1
       [     ]----------> 4
 | otherwise maxTail                          
                            
Moving the 4 into the blank gives:
   
maximum' 1:2:4:[]
 | 1 > maxTail  = 1
       [  4  ]
 | otherwise maxTail         

That allows you to answer the question is 1 > 4.  That is false, so
you look at the second guard condition:

| otherwise maxTail

which just returns maxTail, or 4.  That means the value of 
maximum' 1:2:4:[] is 4. Ta da.

Try doing something similar with the other function definitions
to see if you can figure them out.