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