// written in the D programming language
// author: Timon Gehr
import std.stdio;
import std.conv;
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);});}
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)));} //Bug? Cannot do LList!T;
}
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 filter(T)(Lazy!bool delegate(Lazy!T) p,Lazy!(List!T) xs){
return lz({
if(xs().empty) return Empty!T;
auto rest=filter(p,xs.tail);
if(p(xs.head)()) return cons(xs.head,rest);
return rest;
});
}
Lazy!S foldl(S,T)(Lazy!S delegate(Lazy!S,Lazy!T) f,Lazy!S nul,Lazy!(List!T) xs){
return lz({
if(xs().empty) return nul();
return foldl(f,f(nul,xs.head), xs.tail)();
});
}
Lazy!S foldlt(S,T)(Lazy!S delegate(Lazy!S,Lazy!T) f,Lazy!S nul,Lazy!(List!T) xs){
return lz({
auto a=nul;
for(auto t=xs;!t().empty;t=t().tail) a=f(a,t.head);
return a();
});
}
Lazy!T foldr(S,T)(Lazy!T delegate(Lazy!S,Lazy!T) f,Lazy!T nul,Lazy!(List!S) xs){
return lz({
if(xs.empty) return nul();
return f(xs.head,foldr(f,nul,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 zipWith(T,S,R)(Lazy!T delegate(Lazy!S,Lazy!R) f,Lazy!(List!S) xs, Lazy!(List!T) ys){
return lz({
if(xs().empty||ys().empty) return Empty!T;
return cons(f(xs.head,ys.head),zipWith(f,xs.tail,ys.tail))();
});
}
LList!(List!T) climbers(T)(Lazy!(List!T) xs){
return lz({
if(xs().empty) return Empty!(List!T);
auto x=xs().head, ys=xs().tail;
if(ys().empty) return list(list(x))();
auto y=ys().head;
if(x()>y()) return cons(list(x),climbers(ys))();
auto zs=climbers(ys);
return cons(cons(x,zs.head),zs.tail)();
});
}
LList!T merge(T)(Lazy!(List!T) xs, Lazy!(List!T) ys){
return lz({
if(xs().empty) return ys();
if(ys().empty) return xs();
if(xs().head()<=ys().head()) return cons(xs.head,merge(xs.tail,ys))();
return cons(ys.head,merge(xs,ys.tail))();
});
}
LList!(List!T) mergepairs(T)(Lazy!(List!(List!T)) xss){
return lz({
if(xss().empty) return Empty!(List!T);
if(xss().tail().empty) return xss();
return cons(merge(xss.head,xss.tail().head),mergepairs(xss.tail().tail))();
});
}
LList!T sort(T)(Lazy!(List!T) xs){
LList!T loop(Lazy!(List!(List!T)) css){
return lz({
if(css().tail().empty) return css().head();
return loop(mergepairs(css))();
});
}
return lz({
auto css=climbers(xs);
return loop(css)();
});
}
LList!ulong fibonacci()(){
LList!ulong r;
r=cons(st(1UL),cons(st(1UL),lz({return zipWith((Lazy!ulong a,Lazy!ulong b){return lz({return a()+b();});},r,r().tail)();})));
return r;
}
LList!T naturals(T)(T start){
return cons(st(start),lz({return naturals(start+1)();}));
}
import std.random;
void main(){
writeln(take(93,fibonacci())());
int[] a=new int[1000];
foreach(ref x;a) x=uniform(0,cast(int)a.length);
auto m=list(a);
writeln(take(100,sort(m))());
}