Editing Lazy evaluation (section)

=== Working with infinite data structures ===
Delayed evaluation has the advantage of being able to create calculable infinite lists without infinite loops or size matters interfering in computation. The actual values are only computed when needed. For example, one could create a function that creates an infinite list (often called a ''[[Stream (computing)|stream]]'') of [[Fibonacci number]]s. The calculation of the ''n''-th Fibonacci number would be merely the extraction of that element from the infinite list, forcing the evaluation of only the first n members of the list.<ref name="Métayer2002">{{cite conference |last1=Wells |first1=J.B. |last2=Haack |first2=C. |title=Branching Types|editor-first=Daniel |editor-last=Le Métayer |book-title=Programming languages and systems, ESOP 2002 |year=2002 |series=Lecture Notes in Computer Science |volume=2305 |doi=10.1007/3-540-45927-8_9 |publisher=Springer |isbn=978-3-540-43363-7 |pages=129–132|doi-access=free }}</ref><ref name="MachineryLanguages2002">{{cite conference |first=Jan-Willem |last=Maessen |title=Eager Haskell: resource-bounded execution yields efficient iteration |book-title=Proceedings of the 2002 ACM SIGPLAN Haskell Workshop (Haskell '02): Pittsburgh, Pennsylvania, USA; October 3, 2002 |date=2002|publisher=Association for Computing Machinery|isbn=978-1-58113-605-0|pages=38–50 See p. 40 |doi=10.1145/581690.581694}}</ref>

Take for example this trivial program in [[Haskell]]:

<syntaxhighlight lang="haskell">
numberFromInfiniteList :: Int -> Int
numberFromInfiniteList n =  infinity !! n - 1
    where infinity = [1..]

main = print $ numberFromInfiniteList 4
</syntaxhighlight>

In the function {{mono|numberFromInfiniteList}}, the value of {{mono|infinity}} is an infinite range, but until an actual value (or more specifically, a specific value at a certain index) is needed, the list is not evaluated, and even then, it is only evaluated as needed (that is, until the desired index.) Provided the programmer is careful, the program completes normally. However, certain calculations may result in the program attempting to evaluate an infinite number of elements; for example, requesting the length of the list or trying to sum the elements of the list with a [[fold (higher-order function)|fold operation]] would result in the program either failing to terminate or running [[out of memory]].

As another example, the list of all Fibonacci numbers can be written in the programming language [[Haskell]] as:<ref name="MachineryLanguages2002"/>

<syntaxhighlight lang="haskell">
 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
</syntaxhighlight>

In Haskell syntax, "<code>:</code>" prepends an element to a list, <code>tail</code> returns a list without its first element, and <code>zipWith</code> uses a specified function (in this case addition) to combine corresponding elements of two lists to produce a third.<ref name="Métayer2002"/>