Advertisement
Guest User

Untitled

a guest
Aug 25th, 2011
333
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
D 3.15 KB | None | 0 0
  1. // written in the D programming language
  2. // author: Timon Gehr
  3.  
  4. import std.stdio;
  5. import std.conv;
  6. import core.memory;
  7.  
  8. class Lazy(T){
  9.     T delegate() compute;
  10.     this(T delegate() compute){this.compute=compute;}
  11.     this(T value){this.value=value;}
  12.     T value;
  13.     final T opCall(){
  14.         if(compute==null) return value;
  15.         value=compute(), compute=null;
  16.         return value;
  17.     }
  18.     auto opDispatch(string op,T...)(T args){return lz({return mixin("opCall()."~op)(args);});}
  19.     override final string toString(){
  20.         static if(!is(T==BigInt)) return to!string(opCall());
  21.         else{string r;void moo(const(char)[] x){r~=x;}
  22.             opCall().toString(&moo,"d");return r;}
  23.     }
  24. }
  25.  
  26. Lazy!T lz(T)(T delegate() compute){return new Lazy!T(compute);} // lazy
  27. Lazy!T st(T)(T value){return new Lazy!T(value);}                // strict
  28.  
  29. template Type(S){alias typeof({S a;return a();}()) Type;}
  30.  
  31. struct List(T){
  32.     Lazy!T head;
  33.     Lazy!(List!T) tail;
  34.  
  35.     string toString(){
  36.         if(empty) return "[]";
  37.         char[] r=['['];
  38.         for(auto xs=this;!xs.empty;xs=xs.tail())
  39.             static if(!is(T==BigInt)) r~=to!string(xs.head())~",";
  40.             else xs.head().toString((const(char)[] x){r~=x~",";},"d");
  41.         r[$-1]=']';
  42.         return cast(string)r;
  43.     }
  44.     T front(){return head();}
  45.     bool empty(){return head is null;}
  46.     static List!T Empty;
  47.     static this(){Empty=List!T(null,lz({return assert(0,"Tried to get tail of empty list!"), List.init;}));}
  48.     this(Lazy!T x, Lazy!(List!T) xs){
  49.         head=x;
  50.         tail=xs;
  51.     }
  52.     Lazy!T opIndex(int i){return drop(i-1,st(this))().head;}
  53.     Lazy!(List!T) opSlice(int a,int b){return take(b-a,drop(a-1,st(this)));}
  54. }
  55.  
  56. auto cons(T)(Lazy!T x, Lazy!(List!T) xs){return lz({return List!T(x,xs);});}
  57.  
  58. //auto list(T)(Lazy!T[] args...){return lz({return List!T(args);});} // =O?
  59. auto list(T)(Lazy!T[] args...){if(args==[]) return st(Empty!T); return cons(args[0],list(args[1..$]));}
  60. 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..$]));}
  61.  
  62. template Empty(T){alias List!T.Empty Empty;}
  63. template LList(T){alias Lazy!(List!T) LList;}
  64.  
  65. LList!S map(T,S)(Lazy!S delegate(Lazy!T) f, Lazy!(List!T) xs){
  66.     return lz({
  67.             if(xs().empty) return Empty!S;
  68.             return cons(f(xs.head), map(f,xs.tail))();
  69.         });
  70. }
  71.  
  72. LList!T take(T)(int n,Lazy!(List!T) xs){
  73.     return lz({
  74.             if(n<=0) return Empty!T;
  75.             return cons(xs().head,lz({return take(n-1,xs().tail)();}))();
  76.         });
  77. }
  78.  
  79. LList!T drop(T)(int n,Lazy!(List!T) xs){
  80.     return lz({
  81.             auto r=xs();
  82.             foreach(i;0..n) r=r.tail();
  83.             return r;
  84.         });
  85. }
  86.  
  87. LList!T hamming(T)(){
  88.     LList!T merge(LList!T xs, LList!T ys){
  89.         return lz({
  90.                 auto x=xs.head, y=ys.head;
  91.                 if(x()<y()) return cons(x,merge(xs.tail,ys))();
  92.                 else if(x()>y()) return cons(y,merge(xs,ys.tail))();
  93.                 else return cons(x,merge(xs.tail,ys.tail))();
  94.             });
  95.     }
  96.     return lz({
  97.             LList!T r;
  98.             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))();}));
  99.             return r();
  100.         });
  101. }
  102. import std.bigint;
  103. void main(){
  104.     auto h=hamming!BigInt();
  105.     writeln(take(20,h));
  106.     writeln(h()[1691]);
  107.     writeln(h()[1000000]);
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement