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

list.d

By: a guest on Aug 24th, 2011  |  syntax: D  |  size: 4.85 KB  |  views: 1,287  |  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.  
  7. class Lazy(T){
  8.         T delegate() compute;
  9.         this(T delegate() compute){this.compute=compute;}
  10.         this(T value){this.value=value;}
  11.         T value;
  12.         final T opCall(){
  13.                 if(compute==null) return value;
  14.                 value=compute(), compute=null;
  15.                 return value;
  16.         }
  17.         auto opDispatch(string op,T...)(T args){return lz({return mixin("opCall()."~op)(args);});}
  18.         final string toString(){return to!string(opCall());}
  19. }
  20.  
  21. Lazy!T lz(T)(T delegate() compute){return new Lazy!T(compute);} // lazy
  22. Lazy!T st(T)(T value){return new Lazy!T(value);}                // strict
  23.  
  24. template Type(S){alias typeof({S a;return a();}()) Type;}
  25.  
  26. struct List(T){
  27.         Lazy!T head;
  28.         Lazy!(List!T) tail;
  29.  
  30.         string toString(){
  31.                 if(empty) return "[]";
  32.                 char[] r=['['];
  33.                 for(auto xs=this;!xs.empty;xs=xs.tail()) r~=to!string(xs.head())~",";
  34.                 r[$-1]=']';
  35.                 return cast(string)r;
  36.         }
  37.         T front(){return head();}
  38.         bool empty(){return head is null;}
  39.         static List!T Empty;
  40.         static this(){Empty=List!T(null,lz({assert(0,"Tried to get tail of empty list!");return List.init;}));}
  41.         this(Lazy!T x, Lazy!(List!T) xs){
  42.                 head=x;
  43.                 tail=xs;
  44.         }
  45.         Lazy!T opIndex(int i){return drop(i-1,st(this))().head;}
  46.         Lazy!(List!T) opSlice(int a,int b){return take(b-a,drop(a-1,st(this)));} //Bug? Cannot do LList!T;     
  47. }
  48.  
  49. auto cons(T)(Lazy!T x, Lazy!(List!T) xs){return lz({return List!T(x,xs);});}
  50.  
  51. //auto list(T)(Lazy!T[] args...){return lz({return List!T(args);});} // =O?
  52. auto list(T)(Lazy!T[] args...){if(args==[]) return st(Empty!T); return cons(args[0],list(args[1..$]));}
  53. 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..$]));}
  54.  
  55. template Empty(T){alias List!T.Empty Empty;}
  56. template LList(T){alias Lazy!(List!T) LList;}
  57.  
  58. LList!S map(T,S)(Lazy!S delegate(Lazy!T) f, Lazy!(List!T) xs){
  59.         return lz({
  60.                         if(xs().empty) return Empty!S;
  61.                         return cons(f(xs.head), map(f,xs.tail))();
  62.                 });
  63. }
  64.  
  65. LList!T filter(T)(Lazy!bool delegate(Lazy!T) p,Lazy!(List!T) xs){
  66.         return lz({
  67.                         if(xs().empty) return Empty!T;
  68.                         auto rest=filter(p,xs.tail);
  69.                         if(p(xs.head)()) return cons(xs.head,rest);
  70.                         return rest;
  71.                 });
  72. }
  73.  
  74. Lazy!S foldl(S,T)(Lazy!S delegate(Lazy!S,Lazy!T) f,Lazy!S nul,Lazy!(List!T) xs){
  75.         return lz({
  76.                         if(xs().empty) return nul();
  77.                         return foldl(f,f(nul,xs.head), xs.tail)();
  78.                 });
  79. }
  80.  
  81. Lazy!S foldlt(S,T)(Lazy!S delegate(Lazy!S,Lazy!T) f,Lazy!S nul,Lazy!(List!T) xs){
  82.         return lz({
  83.                         auto a=nul;
  84.                         for(auto t=xs;!t().empty;t=t().tail) a=f(a,t.head);
  85.                         return a();
  86.                 });
  87. }
  88.  
  89. Lazy!T foldr(S,T)(Lazy!T delegate(Lazy!S,Lazy!T) f,Lazy!T nul,Lazy!(List!S) xs){
  90.         return lz({
  91.                         if(xs.empty) return nul();
  92.                         return f(xs.head,foldr(f,nul,xs.tail))();
  93.                 });
  94. }
  95.  
  96. LList!T take(T)(int n,Lazy!(List!T) xs){
  97.         return lz({
  98.                         if(n<=0) return Empty!T;
  99.                         return cons(xs().head,lz({return take(n-1,xs().tail)();}))();
  100.                 });
  101. }
  102.  
  103. LList!T drop(T)(int n,Lazy!(List!T) xs){
  104.         return lz({
  105.                         auto r=xs();
  106.                         foreach(i;0..n) r=r.tail();
  107.                         return r;
  108.                 });
  109. }
  110.  
  111. LList!T zipWith(T,S,R)(Lazy!T delegate(Lazy!S,Lazy!R) f,Lazy!(List!S) xs, Lazy!(List!T) ys){
  112.         return lz({
  113.                         if(xs().empty||ys().empty) return Empty!T;
  114.                         return cons(f(xs.head,ys.head),zipWith(f,xs.tail,ys.tail))();
  115.                 });
  116. }
  117.  
  118. LList!(List!T) climbers(T)(Lazy!(List!T) xs){
  119.         return lz({
  120.                         if(xs().empty) return Empty!(List!T);
  121.                         auto x=xs().head, ys=xs().tail;
  122.                         if(ys().empty) return list(list(x))();
  123.                         auto y=ys().head;
  124.                         if(x()>y()) return cons(list(x),climbers(ys))();
  125.                         auto zs=climbers(ys);
  126.                         return cons(cons(x,zs.head),zs.tail)();
  127.                 });
  128. }
  129.  
  130. LList!T merge(T)(Lazy!(List!T) xs, Lazy!(List!T) ys){
  131.         return lz({
  132.                         if(xs().empty) return ys();
  133.                         if(ys().empty) return xs();
  134.                         if(xs().head()<=ys().head()) return cons(xs.head,merge(xs.tail,ys))();
  135.                         return cons(ys.head,merge(xs,ys.tail))();
  136.                 });
  137. }
  138.  
  139. LList!(List!T) mergepairs(T)(Lazy!(List!(List!T)) xss){
  140.         return lz({
  141.                         if(xss().empty) return Empty!(List!T);
  142.                         if(xss().tail().empty) return xss();
  143.                         return cons(merge(xss.head,xss.tail().head),mergepairs(xss.tail().tail))();
  144.                 });
  145. }
  146.  
  147. LList!T sort(T)(Lazy!(List!T) xs){
  148.         LList!T loop(Lazy!(List!(List!T)) css){
  149.                 return lz({
  150.                                 if(css().tail().empty) return css().head();    
  151.                                 return loop(mergepairs(css))();
  152.                         });
  153.         }
  154.         return lz({
  155.                         auto css=climbers(xs);
  156.                         return loop(css)();
  157.                 });
  158. }
  159.  
  160. LList!ulong fibonacci()(){
  161.         LList!ulong r;
  162.         r=cons(st(1UL),cons(st(1UL),lz({return zipWith((Lazy!ulong a,Lazy!ulong b){return lz({return a()+b();});},r,r().tail)();})));
  163.         return r;
  164. }
  165.  
  166. LList!T naturals(T)(T start){
  167.         return cons(st(start),lz({return naturals(start+1)();}));
  168. }
  169.  
  170.  
  171. import std.random;
  172. void main(){
  173.         writeln(take(93,fibonacci())());
  174.         int[] a=new int[1000];
  175.         foreach(ref x;a) x=uniform(0,cast(int)a.length);
  176.         auto m=list(a);
  177.         writeln(take(100,sort(m))());
  178. }