Untitled

// written in the D programming language
// author: Timon Gehr

import std.stdio;
import std.conv;
import core.memory;

class Lazy(T){
        T delegate() compute;
        this(T delegate() compute){this.compute=compute;}
        this(T value){this.value=value;}
        T value;
        final T opCall(){
                if(compute==null) return value;
                value=compute(), compute=null;
                return value;
        }
        auto opDispatch(string op,T...)(T args){return lz({return mixin("opCall()."~op)(args);});}
        override final string toString(){return to!string(opCall());}
}

Lazy!T lz(T)(T delegate() compute){return new Lazy!T(compute);} // lazy
Lazy!T st(T)(T value){return new Lazy!T(value);}                // strict

template Type(S){alias typeof({S a;return a();}()) Type;}

struct List(T){
        Lazy!T head;
        Lazy!(List!T) tail;

        string toString(){
                if(empty) return "[]";
                char[] r=['['];
                for(auto xs=this;!xs.empty;xs=xs.tail()) r~=to!string(xs.head())~",";
                r[$-1]=']';
                return cast(string)r;
        }
        T front(){return head();}
        bool empty(){return head is null;}
        static List!T Empty;
        static this(){Empty=List!T(null,lz({assert(0,"Tried to get tail of empty list!");return List.init;}));}
        this(Lazy!T x, Lazy!(List!T) xs){
                head=x;
                tail=xs;
        }
        Lazy!T opIndex(int i){return drop(i-1,st(this))().head;}
        Lazy!(List!T) opSlice(int a,int b){return take(b-a,drop(a-1,st(this)));}
}

auto cons(T)(Lazy!T x, Lazy!(List!T) xs){return lz({return List!T(x,xs);});}

//auto list(T)(Lazy!T[] args...){return lz({return List!T(args);});} // =O?
auto list(T)(Lazy!T[] args...){if(args==[]) return st(Empty!T); return cons(args[0],list(args[1..$]));}
auto list(T)(T[] args...) if(!is(T U==Lazy!U)){if(args==[]) return st(Empty!T); return cons(st(args[0]),list(args[1..$]));}

template Empty(T){alias List!T.Empty Empty;}
template LList(T){alias Lazy!(List!T) LList;}

LList!S map(T,S)(Lazy!S delegate(Lazy!T) f, Lazy!(List!T) xs){
        return lz({
                        if(xs().empty) return Empty!S;
                        return cons(f(xs.head), map(f,xs.tail))();
                });
}

LList!T take(T)(int n,Lazy!(List!T) xs){
        return lz({
                        if(n<=0) return Empty!T;
                        return cons(xs().head,lz({return take(n-1,xs().tail)();}))();
                });
}

LList!T drop(T)(int n,Lazy!(List!T) xs){
        return lz({
                        auto r=xs();
                        foreach(i;0..n) r=r.tail();
                        return r;
                });
}

LList!T hamming(T)(){
        LList!T merge(LList!T xs, LList!T ys){
                return lz({
                                auto x=xs.head, y=ys.head;
                                if(x()<y()) return cons(x,merge(xs.tail,ys))();
                                else if(x()>y()) return cons(y,merge(xs,ys.tail))();
                                else return cons(x,merge(xs.tail,ys.tail))();
                        });
        }
        return lz({
                        LList!T r;
                        r=cons(st(1),lz({return merge(merge(map((Lazy!T a){return lz({return 2*a();});},r),map((Lazy!T a){return lz({return 3*a();});},r)),map((Lazy!T a){return lz({return 5*a();});},r))();}));
                        return r();
                });
}

void main(){
        auto h=hamming!int();
        writeln(take(20,h));
        writeln(h()[1690]);
        // next would require unwieldy std.bigint
}