7stud bbxx789_05ss at yahoo.com
Wed Mar 18 03:54:22 EDT 2009

```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.

```