import std.stdio;

void main()
{
    auto empty = new EmptyList!(int);
    
    auto list = Cons(3, Cons(2, Cons(1, empty))); // list = [3,2,1]
    foreach (value; list) writef(value, ","); // Prints 3,2,1,
    writefln();

    // not allowed: (undefined identifier ones)
    // auto ones = Cons(1, ones);
    List!(int) ones; ones = Cons(1, ones);
    
    int count = 0;
    foreach (value; ones)
    {
        count++;
        if (count > 10) break;
        writef(value, ",");
    }
    writefln();
    
    // Output is garbage
    auto naturals = NumsFrom(1);
}

// Doesn't work because of lack of complete Lexical Closures
List!(T) NumsFrom(T)(T n)
{
    return Cons(n, NumsFrom(n+1));
}

List!(T) Cons(T)(T head, List!(T) delegate()[] tail...)
in
{
    assert(tail.length == 1);
}
body
{
    return new ConsList!(T)(head, tail[0]);
}

abstract class List(T)
{
    abstract bool isEmpty();
    abstract T Head();
    abstract List!(T) Tail();
    
    final int opApply(int delegate(inout T) dg)
    {
        int result = 0;
        List!(T) current = this;
        
        while(!current.isEmpty)
        {
            T value = current.Head;
            result = dg(value);
            if (result) break;
            
            current = current.Tail;
        }
        
        return result;
    }
}

struct Memoizer(T)
{
    private bool _hasValue = false;
    private T _value = void;
    private T delegate() _valueGen;

    alias Memoizer!(T) TThis;
    static TThis opCall(T delegate() generator)
    {
        TThis val;
        val._valueGen = generator;
        return val;
    }
    
    T value()
    {
        if (_hasValue) return _value;
        _value = _valueGen();
        _hasValue = true;
        return _value;
    }
}

private class ConsList(T) : List!(T)
{
    T head = void;
    Memoizer!(List!(T)) tail = void;
  
    this(T  head, List!(T) delegate() tail)
    {
        this.head = head;
        this.tail = Memoizer!(List!(T))(tail);
    }
    
    bool isEmpty() { return false; }
    
    T Head()
    {
        return head;
    }
    
    List!(T) Tail()
    {
        return tail.value;
    }
}

private class EmptyList(T) : List!(T)
{
    bool isEmpty() { return true; }
    T Head () { assert(false); }
    List!(T) Tail() { assert (false); }
}