Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // 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(){
- static if(!is(T==BigInt)) return to!string(opCall());
- else{string r;void moo(const(char)[] x){r~=x;}
- opCall().toString(&moo,"d");return r;}
- }
- }
- 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())
- static if(!is(T==BigInt)) r~=to!string(xs.head())~",";
- else xs.head().toString((const(char)[] x){r~=x~",";},"d");
- 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({return assert(0,"Tried to get tail of empty list!"), 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(cast(T)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();
- });
- }
- import std.bigint;
- void main(){
- auto h=hamming!BigInt();
- writeln(take(20,h));
- writeln(h()[1691]);
- writeln(h()[1000000]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement