[Haskell-beginners] Re: Understanding recursion in Haskell.
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.
More information about the Beginners
mailing list