Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Aug 24th, 2011  |  syntax: D  |  size: 2.92 KB  |  views: 132  |  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(){return to!string(opCall());}
  20. }
  21.  
  22. Lazy!T lz(T)(T delegate() compute){return new Lazy!T(compute);} // lazy
  23. Lazy!T st(T)(T value){return new Lazy!T(value);}                // strict
  24.  
  25. template Type(S){alias typeof({S a;return a();}()) Type;}
  26.  
  27. struct List(T){
  28.         Lazy!T head;
  29.         Lazy!(List!T) tail;
  30.  
  31.         string toString(){
  32.                 if(empty) return "[]";
  33.                 char[] r=['['];
  34.                 for(auto xs=this;!xs.empty;xs=xs.tail()) r~=to!string(xs.head())~",";
  35.                 r[$-1]=']';
  36.                 return cast(string)r;
  37.         }
  38.         T front(){return head();}
  39.         bool empty(){return head is null;}
  40.         static List!T Empty;
  41.         static this(){Empty=List!T(null,lz({assert(0,"Tried to get tail of empty list!");return List.init;}));}
  42.         this(Lazy!T x, Lazy!(List!T) xs){
  43.                 head=x;
  44.                 tail=xs;
  45.         }
  46.         Lazy!T opIndex(int i){return drop(i-1,st(this))().head;}
  47.         Lazy!(List!T) opSlice(int a,int b){return take(b-a,drop(a-1,st(this)));}
  48. }
  49.  
  50. auto cons(T)(Lazy!T x, Lazy!(List!T) xs){return lz({return List!T(x,xs);});}
  51.  
  52. //auto list(T)(Lazy!T[] args...){return lz({return List!T(args);});} // =O?
  53. auto list(T)(Lazy!T[] args...){if(args==[]) return st(Empty!T); return cons(args[0],list(args[1..$]));}
  54. 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..$]));}
  55.  
  56. template Empty(T){alias List!T.Empty Empty;}
  57. template LList(T){alias Lazy!(List!T) LList;}
  58.  
  59. LList!S map(T,S)(Lazy!S delegate(Lazy!T) f, Lazy!(List!T) xs){
  60.         return lz({
  61.                         if(xs().empty) return Empty!S;
  62.                         return cons(f(xs.head), map(f,xs.tail))();
  63.                 });
  64. }
  65.  
  66. LList!T take(T)(int n,Lazy!(List!T) xs){
  67.         return lz({
  68.                         if(n<=0) return Empty!T;
  69.                         return cons(xs().head,lz({return take(n-1,xs().tail)();}))();
  70.                 });
  71. }
  72.  
  73. LList!T drop(T)(int n,Lazy!(List!T) xs){
  74.         return lz({
  75.                         auto r=xs();
  76.                         foreach(i;0..n) r=r.tail();
  77.                         return r;
  78.                 });
  79. }
  80.  
  81. LList!T hamming(T)(){
  82.         LList!T merge(LList!T xs, LList!T ys){
  83.                 return lz({
  84.                                 auto x=xs.head, y=ys.head;
  85.                                 if(x()<y()) return cons(x,merge(xs.tail,ys))();
  86.                                 else if(x()>y()) return cons(y,merge(xs,ys.tail))();
  87.                                 else return cons(x,merge(xs.tail,ys.tail))();
  88.                         });
  89.         }
  90.         return lz({
  91.                         LList!T r;
  92.                         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))();}));
  93.                         return r();
  94.                 });
  95. }
  96.  
  97. void main(){
  98.         auto h=hamming!int();
  99.         writeln(take(20,h));
  100.         writeln(h()[1690]);
  101.         // next would require unwieldy std.bigint
  102. }
clone this paste RAW Paste Data