What are the advantages of Lazy Evaluation?

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.

This refers to the evaluation of a syntax tree. If you evaluate a syntax tree lazily (i.e. when the value it represents is needed), you must carry it through the preceeding steps of your computation in its entirety. This is the overhead of lazy evaluation. However, there are two advantages. 1) you will not evaulate the tree unnecessarily if the result is never used, and 2) you can express and use an infinite syntax tree in some recursive form, because you will only ever evaluate it to the depth you need, as opposed to evaluating (eagerly) in its entirety, which would be impossible.

I don't know haskel, but as far as I know programming languages like python or ML evaluate eagerly. For example to simulate lazy evaluation in ML, you must create a dummy function that takes no parameters but returns the result. This function is then your syntax tree that you can lazily evaluate at any time by invoking it with an empty argument list.

In ruby, we use function modifiers, typically called "once", to wrap a method so that it does lazy evaluation. Such a method will only be evaluated once, the value cached, subsequent calls returning that value.

One use (or misuse) of lazy evaluation is to make order of object initialization implicit rather than explicit. Before:

def initialize
  setup_logging  # Must come before setup_database
  setup_database  # Must come before get_addresses
  setup_address_correction  # Must come before get_addresses
  get_addresses
end

def setup_logging
  @log = Log.new
end

def setup_database
  @db = Db.new(@log)
end

def setup_address_correction
  @address_correction = AddressCorrection.new
end

def get_addresses
  @log.puts ("Querying addresses")
  @addresses = @address_correction.correct(query_addresses(@db))
end

With lazy evaluation:

def initialize
  get_addresses
end

def log
  Log.new
end
once :log

def db
  Db.new(log)
end
once :db

def address_corrector
  AddressCorrection.new
end
once :address_corrector

def get_addresses
  log.puts ("Querying addresses")
  @addresses = address_corrector.correct(query_addresses(db))
end

The order of initialization of the various interdependent objects is now (1) implicit, and (2) automatic. On the downside, the flow of control can be opaque if this trick is relied upon too heavily.