Difference between revisions of "Haskell/Lazy evaluation"
(formatting, c/e) 

(7 intermediate revisions by 5 users not shown)  
Line 1:  Line 1:  
+  This question came up in #haskell, and it seemed instructive to take the discussion and sum it up into a simple tutorial on lazy evaluation. 

+  For more information, see the [[Performance/LazinessLaziness]] 

+  and [[Performance/StrictnessStrictness]] pages. 

+  
+  The following code was given: 

+  
<haskell> 
<haskell> 

magic :: Int > Int > [Int] 
magic :: Int > Int > [Int] 

Line 5:  Line 11:  
getIt :: [Int] > Int > Int 
getIt :: [Int] > Int > Int 

−  getIt [] _ = 
+  getIt [] _ = undefined 
getIt (x:xs) 1 = x 
getIt (x:xs) 1 = x 

getIt (x:xs) n = getIt xs (n1) 
getIt (x:xs) n = getIt xs (n1) 

</haskell> 
</haskell> 

−  We want to evaluate the following: 

+  Analyzing this code a little, we can see that <code>(magic 1 1)</code> is just the Fibonacci numbers, namely <code>[1,1,2,3,5,...]</code>, i.e. an infinite list. Now, the person asking wanted to evaluate the following: 

+  <haskell> 

getIt (magic 1 1) 3 
getIt (magic 1 1) 3 

+  </haskell> 

⚫  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). 

+  In this context, of course, <code>getIt (magic 1 1) x</code> is simply <code>(magic 1 1) !! (x  1)</code>. Again, the important thing in this context is that although the full evaluation of <code>(magic 1 1)</code> never terminates, the evaluation of this expression in fact does. But if a parameter to a function can never be fully evaluated, how can the full function call ever be evaluated? The answer is: Lazy Evaluation. In this tutorial, we're going to step through this code, and attempt to give an idea of how Haskell will attempt to evaluate the above expression. 

⚫  The first thing to do is to figure out which pattern in <code>getIt</code> this expression matches. The first pattern only matches if <code>getIt</code> 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 <code>(magic 1 1)</code>. 

+  <haskell> 

getIt (1 : (magic 1 (1+1)) 3 
getIt (1 : (magic 1 (1+1)) 3 

−  
+  </haskell> 

−  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 
+  Now it's clear that <code>getIt</code> 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 <code>getIt</code>. So we look at the second pattern in <code>getIt</code>. Now the nonempty list is fine, but the 3 doesn't match with the 1, so we move on to the third pattern. Finally we have a nonempty list <code>(x:xs)</code> and any integer <code>n</code>, so we will match this pattern. The first 1 gets bound to <code>x</code>, the <code>(magic 1 (1+1))</code> gets bound to <code>xs</code>, and the 3 gets bound to <code>n</code>. Doing the substitution on the righthand side yields 
−  +  <haskell> 

getIt (magic 1 (1+1)) (31) 
getIt (magic 1 (1+1)) (31) 

−  
+  </haskell> 

−  Time to find a pattern in getIt to match with again. Looking at the first pattern 
+  Time to find a pattern in <code>getIt</code> 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. 
−  +  <haskell> 

getIt (1 : (magic (1+1) (1+(1+1)))) (31) 
getIt (1 : (magic (1+1) (1+(1+1)))) (31) 

−  
+  </haskell> 

−  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). 
+  Now it again becomes clear that we're not talking about an empty list. On to the second pattern in <code>getIt</code> 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). 
−  +  <haskell> 

getIt (1 : (magic (1+1) (1+(1+1)))) 2 
getIt (1 : (magic (1+1) (1+(1+1)))) 2 

−  
+  </haskell> 

−  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 
+  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, <code>(magic (1+1) (1+(1+1)))</code> to <code>xs</code>, and 2 to <code>n</code>, yielding 
−  +  <haskell> 

getIt (magic (1+1) (1+(1+1))) (21) 
getIt (magic (1+1) (1+(1+1))) (21) 

−  
+  </haskell> 

−  Again, we need to know whether or not the list is nonempty, forcing the magic call to be expanded. 
+  Again, we need to know whether or not the list is nonempty, forcing the magic call to be expanded. To see if this call matches the first pattern in magic, we must evaluate the first argument, (1+1), giving 
−  +  <haskell> 

−  getIt 
+  getIt (magic 2 (1+2)) (21) 
−  +  </haskell> 

+  Both <code>(1+1)</code> were in fact the same expression (bound to <code>m</code> in <code>magic n m = n : magic m (n+m)</code>), and so the second <code>(1+1)</code> is now 2 as well. The first argument to <code>magic</code> is not 0, so the second pattern in <code>magic</code> definition is used, yielding 

+  <haskell> 

+  getIt (2 : magic (1+2) (2+(1+2))) (21) 

+  </haskell> 

It's again a nonempty list, so we evaluate the second parameter to find out if it's a 1. 
It's again a nonempty list, so we evaluate the second parameter to find out if it's a 1. 

+  <haskell> 

⚫  
+  </haskell> 

⚫  
+  <haskell> 

⚫  
+  </haskell> 

⚫  
−  
⚫  
−  This yields 

+  [[Category:Tutorials]] 

−  
−  (1+1) 

−  
−  Which further evaluates to 2 

−  
⚫ 
Latest revision as of 10:14, 23 August 2014
This question came up in #haskell, and it seemed instructive to take the discussion and sum it up into a simple tutorial on lazy evaluation. For more information, see the Laziness and Strictness pages.
The following code was given:
magic :: Int > Int > [Int]
magic 0 _ = []
magic m n = m : (magic n (m+n))
getIt :: [Int] > Int > Int
getIt [] _ = undefined
getIt (x:xs) 1 = x
getIt (x:xs) n = getIt xs (n1)
Analyzing this code a little, we can see that (magic 1 1)
is just the Fibonacci numbers, namely [1,1,2,3,5,...]
, i.e. an infinite list. Now, the person asking wanted to evaluate the following:
getIt (magic 1 1) 3
In this context, of course, getIt (magic 1 1) x
is simply (magic 1 1) !! (x  1)
. Again, the important thing in this context is that although the full evaluation of (magic 1 1)
never terminates, the evaluation of this expression in fact does. But if a parameter to a function can never be fully evaluated, how can the full function call ever be evaluated? The answer is: Lazy Evaluation. In this tutorial, we're going to step through this code, and attempt to give an idea of how Haskell will attempt to evaluate the above expression.
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 on to the third pattern. Finally we have a nonempty list (x:xs)
and any integer n
, 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. To see if this call matches the first pattern in magic, we must evaluate the first argument, (1+1), giving
getIt (magic 2 (1+2)) (21)
Both (1+1)
were in fact the same expression (bound to m
in magic n m = n : magic m (n+m)
), and so the second (1+1)
is now 2 as well. The first argument to magic
is not 0, so the second pattern in magic
definition is used, yielding
getIt (2 : magic (1+2) (2+(1+2))) (21)
It's again a nonempty list, so we evaluate the second parameter to find out if it's a 1.
getIt (2 : (magic (1+2) (2+(1+2))) 1
It is, so 2 gets bound to x
, and (magic (1+2) (2+(1+2)))
to xs
. This yields:
2