Personal tools

Lazy evaluation

From HaskellWiki

Revision as of 08:21, 29 November 2007 by Lemming (Talk | contribs)
Jump to: navigation, search

Lazy evaluation means Non-strict semantics and Sharing. The opposite is eager evaluation.

Non-strict semantics allows to bypass undefined values (e.g. results of infinite loops) and this way it also allows to process formally infinite data.

When it comes to machine level and efficiency issues then it is important whether equal objects share the same memory.

A Haskell program cannot observe whether
2+2 :: Int
and
4 :: Int
are different objects in the memory.

In many cases it is also not necessary to know it, but in some cases the difference between shared and separated objects yields different orders of space or time complexity.

Consider the infinite list
let x = 1:x in x
. For the non-strict semantics it would be ok to store this as a flat list
1 : 1 : 1 : 1 : ...
, with memory consumption as big as the number of consumed
1
s.

But with lazy evaluation (i.e. sharing) this becomes a list with a loop, a pointer back to the beginning. It does only consume constant space. In an imperative language (here Modula-3) the same would be achieved with the following code: 

TYPE
  List =
    REF RECORD
          next:  List;
          value: INTEGER;
        END;

VAR
  x := NEW(List, value:=1);
BEGIN
  x.next := x;
END;

Retrieved from "http://www.haskell.org/haskellwiki/Lazy_evaluation"

Category: Glossary