Lazy evaluationLazy evaluationldots Lazy evaluationldots Lazy evaluationldots Lazy evaluation --- Exampleldots Lazy evaluation --- Exampleldots Infinite data structuresInfinite data structuresldots Infinite data structuresldots Acknowledgements520—Spring 2005—19CSc 520Principles of ProgrammingLanguages19: Haskell — Lazy EvaluationChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2004 Christian Collberg[1]520—Spring 2005—19Lazy evaluationHaskell evaluates expressions using a technique calledlazy evaluation:No expression is evaluated until its value is needed.No shared expression is evaluated more than once; ifthe expression is ever evaluated then the result isshared between all those places in which it is used.The first of these ideas is illustrated by the followingfunction:ignoreArgument x = "Didn’t evaluate x"[2]520—Spring 2005—19Lazy evaluation...Since the result of the function ignoreArgument doesn’tdepend on the value of its argumentx, that argument willnot be evaluated:? ignoreArgument (1/0)I didn’t need to evaluate x(1 reduction, 31 cells)?We can force strict evaluation when that is necessary:? strict ignoreArgument (1/0){primDivInt 1 0}(4 reductions, 29 cells)?[3]520—Spring 2005—19Lazy evaluation...The second basic idea behind lazy evaluation is that noshared expression should be evaluated more than once.For example, the following two expressions can be used tocalculate3 ∗ 3 ∗ 3 ∗ 3:> /usr/local/hugs98/bin/hugs +s> square*square where square = 3*381(28 reductions, 39 cells)> (3*3)*(3*3)81(34 reductions, 45 cells)Notice that the first expression requires fewer reductionthan the second.[4]520—Spring 2005—19Lazy evaluation...The sequences of reductions:square * square where square = 3 * 3-- calculate the value of square by-- reducing 3*3==>9 and replace each-- occurrence of square with this result==> 9 * 9==> 81(3 * 3) * (3 * 3) -- evaluate first (3*3)==> 9 * (3 * 3) -- evaluate second (3*3)==> 9 * 9==> 81Lazy evaluation means that only the minimum amount ofcalculation is used to determine the result of an expression.[5]520—Spring 2005—19Lazy evaluation — Example...Consider the task of finding the smallest element of a list ofintegers.? minimum [100,99..1]1(809 reductions, 1322 cells)?[100,99..1]denotes the list of integers from 1 to 100arranged in decreasing order.Instead, we could first sort and then take the head of theresult:? :load List? sort [100,99..1][1, 2, 3, 4, 5, 6, 7, 8, ..., 99, 100](10712 reductions, 21519 cells)?[6]520—Spring 2005—19Lazy evaluation — Example...However, thanks to lazy-evaluation, calculating just the firstelement of the sorted list actually requires less work in thisparticular case than the first solution usingminimum:? head (sort [100,99..1])1(713 reductions, 1227 cells)?[7]520—Spring 2005—19Infinite data structuresLazy evaluation makes it possible for functions inHaskell to manipulate ‘infinite’ data structures.The advantage of lazy evaluation is that it allows us toconstruct infinite objects piece by piece as necessaryConsider the following function which can be used toproduce infinite lists of integer values:countFrom n = n : countFrom (n+1)? countFrom 1[1, 2, 3, 4, 5, 6, 7, 8,ˆC{Interrupted!}](53 reductions, 160 cells)?[8]520—Spring 2005—19Infinite data structures...For practical applications, we are usually only interestedin using a finite portion of an infinite data structure.We can find the sum of the integers 1 to 10:? sum (take 10 (countFrom 1))55(62 reductions, 119 cells)?take n xs evaluates to a list containing the first nelements of the list xs.[9]520—Spring 2005—19Infinite data structures...Infinite data structures enables us to describe an objectwithout being tied to one particular application of thatobject.The following definition for infinite list of powers of two[1, 2, 4, 8, ...]:powersOfTwo = 1 : map double powersOfTwowhere double n = 2*nxs!!n evaluates to the nth element of the list xs.We can define a function to find the nth power of 2 forany given integern:twoToThe n = powersOfTwo !! n[10]520—Spring 2005—19AcknowledgementsThese slides were derived directly from the Gofermanual.Functional programming environment, Version2.20c Copyright Mark P. Jones 1991.A copy of the Gofer manual can be found
View Full Document
Unlocking...