This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Aug 25th, 2011  |  syntax: D  |  size: 3.15 KB  |  views: 253  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }
clone this paste RAW Paste Data