What are the advantages of Lazy Evaluation?

Question

What advantages are there to Lazy Evaluation as opposed to Eager Evaluation?

What performance overhead is there? Is Lazy Evaluation going to be slower or faster? Why(or does it depend on implementation?)?

How does lazy evaluation actually work in most implementations? To me it would seem like it would be much slower and memory intensive because variables must stored operations as well as numbers. so how does that work in a language like Haskell(note, I don't actually know that language)? How is the lazyness implemented and done so that it is not tremendously slower/consume more space?

Answer 1

Lazy evaluation can be pretty useful in the creation of data structures with efficient amortized bounds.

Just to give an example, here is an immutable stack class:

class Stack<T> {     public static readonly Stack<T> Empty = new Stack<T>();     public T Head { get; private set; }     public Stack<T> Tail { get; private set; }     public bool IsEmpty { get; private set; }      private Stack(T head, Stack<T> tail)     {         this.Head = head;         this.Tail = tail;         this.IsEmpty = false;     }      private Stack()     {         this.Head = default(T);         this.Tail = null;         this.IsEmpty = true;     }      public Stack<T> AddFront(T value)     {         return new Stack<T>(value, this);     }      public Stack<T> AddRear(T value)     {         return this.IsEmpty             ? new Stack<T>(value, this)             : new Stack<T>(this.Head, this.Tail.AddRear(value));     } } 

You can add an item to the front of the stack in O(1) time, but it requires O(n) time to add an item to the rear. Since we have to re-build our entire data structure, AddRear is a monolithic operation.

Here's the same immutable stack, but now its lazily evaluated:

class LazyStack<T> {     public static readonly LazyStack<T> Empty = new LazyStack<T>();      readonly Lazy<LazyStack<T>> innerTail;     public T Head { get; private set; }     public LazyStack<T> Tail { get { return innerTail.Value; } }     public bool IsEmpty { get; private set; }      private LazyStack(T head, Lazy<LazyStack<T>> tail)     {         this.Head = head;         this.innerTail = tail;         this.IsEmpty = false;     }      private LazyStack()     {         this.Head = default(T);         this.innerTail = null;         this.IsEmpty = true;     }      public LazyStack<T> AddFront(T value)     {         return new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true));     }      public LazyStack<T> AddRear(T value)     {         return this.IsEmpty             ? new LazyStack<T>(value, new Lazy<LazyStack<T>>(() => this, true))             : new LazyStack<T>(this.Head, new Lazy<LazyStack<T>>(() => this.Tail.AddRear(value), true));     } } 

Now the AddRear function clearly runs in O(1) time now. When we access the Tail property, it will evaluate a Lazy value just enough to return the head node, then it stops, so its no longer a monolithic function.