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.