Difference between revisions of "Haskell/Lazy evaluation"
(No difference)

Revision as of 14:17, 18 January 2007
magic :: Int > Int > [Int] magic 0 _ = [] magic m n = m : (magic n (m+n))
getIt :: [Int] > Int > Int getIt [] _ = 0 getIt (x:xs) 1 = x getIt (x:xs) n = getIt xs (n1)
getIt (magic 1 1) 3
The first thing to do is to figure out which pattern in getIt this expression matches. The first pattern only matches if getIt is passed an empty list, and any Int. The 'any Int' part is fine, so we need to know if it's passed an empty list. Answering that question forces one step in the evaluation of (magic 1 1).
getIt (1 : (magic 1 (1+1)) 3
Now it's clear that getIt has not been passed an empty list, since the element has, at least, a head of 1. Thus, this expression will not match the first pattern in getIt. So we look at the second pattern in getIt. Now the nonempty list is fine, but the 3 doesn't match with the 1, so we move to the third pattern. Finally, we have a nonempty list, and any integer, so we will match this pattern. The first 1 gets bound to x, the (magic 1 (1+1)) gets bound to xs, and the 3 gets bound to n. Doing the substitution on the righthand side yields
getIt (magic 1 (1+1)) (31)
Time to find a pattern in getIt to match with again. Looking at the first pattern, it's clear that it doesn't matter what the second argument is, so the question again becomes whether or not the first argument is an empty list or not. This forces another step in the evaluation of magic.
getIt (1 : (magic (1+1) (1+(1+1)))) (31)
Now it again becomes clear that we're not talking about an empty list. On to the second pattern in getIt then. Here, the nonempty list is good, and we need to know if the second argument is a 1. This forces an evaluation of (31).
getIt (1 : (magic (1+1) (1+(1+1)))) 2
Definitely not a 1. On to the third pattern. A nonempty list is good, and any Int is fine, so 1 gets bound to x, (magic (1+1) (1+(1+1))) to xs, and 2 to n, yielding
getIt (magic (1+1) (1+(1+1))) (21)
Again, we need to know whether or not the list is nonempty, forcing the magic call to be expanded.
getIt ((1+1) : (magic (1+(1+1)) (1+(1+(1+1))))) (21)
It's again a nonempty list, so we evaluate the second parameter to find out if it's a 1.
getIt ((1+1) : (magic (1+(1+1)) (1+(1+(1+1))))) 1
It is, so (1+1) gets bound to x, and (magic (1+(1+1)) (1+(1+(1+1)))) to xs.
This yields
(1+1)
Which further evaluates to 2
2