fork download
copy 
  1. function Thunk (value) {
  2.   this.value = value;
  3. }
  4.  
  5. function Lambda (fn) {
  6.   this.fn = fn;
  7. }
  8.  
  9. function App (fn, arg) {
  10.   this.fn = fn;
  11.   this.arg = arg;
  12. }
  13.  
  14. function Evaluate (val) {
  15.   while (val instanceof Thunk) {
  16.     val = val.value();
  17.     if (val instanceof App) {
  18.       val = (PeelLambda(Evaluate(val.fn)))(val.arg);
  19.     }
  20.   }
  21.   return val;
  22. }
  23.  
  24. function PeelLambda (lam) {
  25.   if (!(lam instanceof Lambda)) {
  26.     throw "type error: apply a non-lambda to a value"
  27.   }
  28.   return lam.fn;
  29. }
  30.  
  31. function Apply (fn) {
  32.   return function (arg) {
  33.     return new Thunk(function () {
  34.       return new App(fn, arg);
  35.     });
  36.   };
  37. }
  38.  
  39. var add = new Lambda(function (x) {
  40.   return new Lambda(function (y) {
  41.     return new Thunk(function () {
  42.       return Evaluate(x) + Evaluate(y);
  43.     });
  44.   });
  45. });
  46.  
  47. var sub = new Lambda(function (x) {
  48.   return new Lambda(function (y) {
  49.     return new Thunk(function () {
  50.       return Evaluate(x) - Evaluate(y);
  51.     });
  52.   });
  53. });
  54.  
  55. function Cons (car, cdr) {
  56.   this.car = car;
  57.   this.cdr = cdr;
  58. }
  59.  
  60. function Nil () {
  61. }
  62.  
  63. // []
  64. var nil = new Thunk(function () {
  65.   return new Nil();
  66. });
  67.  
  68. // (:)
  69. var cons = new Lambda(function (x) {
  70.   return new Lambda(function (xs) {
  71.     return new Thunk(function () {
  72.       return new Cons(x, xs);
  73.     });
  74.   });
  75. });
  76.  
  77. // map _ [] = []
  78. // map f (x:xs) = f x : map f xs
  79. var map = new Lambda(function (f) {
  80.   return new Lambda(function (list) {
  81.     return new Thunk(function () {
  82.       var xxs = Evaluate(list);
  83.       if (xxs instanceof Cons) {
  84.         var x = xxs.car;
  85.         var xs = xxs.cdr;
  86.         return Apply(Apply(cons)(Apply(f)(x)))
  87.                                 (Apply(Apply(map)(f))(xs));
  88.       } else {
  89.         return nil;
  90.       }
  91.     });
  92.   });
  93. });
  94.  
  95. // take _ [] = []
  96. // take n _ | n <= 0 = []
  97. // take n (x:xs) = x : take (n - 1) xs
  98. var take = new Lambda(function (n) {
  99.   return new Lambda(function (list) {
  100.     return new Thunk(function () {
  101.       var xxs = Evaluate(list);
  102.       if (xxs instanceof Cons) {
  103.         var nval = Evaluate(n);
  104.         if (nval <= 0) {
  105.           return nil;
  106.         } else {
  107.           var x = xxs.car;
  108.           var xs = xxs.cdr;
  109.           return Apply(Apply(cons)(x))
  110.                                   (Apply(Apply(take)(Apply(Apply(sub)(n))(one)))(xs));
  111.         }
  112.       } else {
  113.         return nil;
  114.       }
  115.     });
  116.   });
  117. });
  118.  
  119. function Unit () {
  120. }
  121.  
  122. // ()
  123. var unit = new Thunk(function () {
  124.   return new Unit();
  125. });
  126.  
  127. // print = \x -> log x; return ()
  128. var print = new Lambda(function (x) {
  129.   return new Thunk(function () {
  130.     console.log(Evaluate(x));
  131.     return Apply(return_)(unit);
  132.   });
  133. });
  134.  
  135. // return
  136. var return_ = new Lambda(function (x) {
  137.   return new Thunk(function () {
  138.     return x;
  139.   });
  140. });
  141.  
  142. // (>>)
  143. var then = new Lambda(function (fn1) {
  144.   return new Lambda(function (fn2) {
  145.     return new Thunk(function () {
  146.       Evaluate(fn1);
  147.       Evaluate(fn2);
  148.     });
  149.   });
  150. });
  151.  
  152. // mapM_ _ [] = return ()
  153. // mapM_ f (x:xs) = f x >> mapM_ f xs
  154. var mapM_ = new Lambda(function (f) {
  155.   return new Lambda(function (list) {
  156.     return new Thunk(function () {
  157.       var xxs = Evaluate(list);
  158.       if (xxs instanceof Cons) {
  159.         var x = xxs.car;
  160.         var xs = xxs.cdr;
  161.         return Apply(Apply(then)(Apply(f)(x)))
  162.                                 (Apply(Apply(mapM_)(f))(xs));
  163.       } else {
  164.         return Apply(return_)(unit);
  165.       }
  166.     });
  167.   });
  168. });
  169.  
  170. var zero = new Thunk(function () {
  171.   return 0;
  172. });
  173.  
  174. var one = new Thunk(function () {
  175.   return 1;
  176. });
  177.  
  178. var twenty = new Thunk(function () {
  179.   return 20;
  180. });
  181.  
  182. // inf = 0 : map (+1) inf
  183. var inf = new Thunk(function () {
  184.   return Apply(Apply(cons)(zero))
  185.                           (Apply(Apply(map)(Apply(add)(one)))(inf));
  186. });
  187.  
  188. // zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
  189. // zipWith _ _ _ = []
  190. var zipWith = new Lambda(function (f) {
  191.   return new Lambda(function (listx) {
  192.     return new Lambda(function (listy) {
  193.       return new Thunk(function () {
  194.         var xxs = Evaluate(listx);
  195.         if (xxs instanceof Cons) {
  196.           var yys = Evaluate(listy);
  197.           if (yys instanceof Cons) {
  198.             return Apply(Apply(cons)(Apply(Apply(f)(xxs.car))(yys.car)))
  199.                                     (Apply(Apply(Apply(zipWith)(f))(xxs.cdr))(yys.cdr));
  200.           }
  201.         } else {
  202.           return nil;
  203.         }
  204.       });
  205.     });
  206.   });
  207. });
  208.  
  209. // tail [] = error "tail: empty list"
  210. // tail (_:xs) = xs
  211. var tail = new Lambda(function (list) {
  212.   return new Thunk(function () {
  213.     var xxs = Evaluate(list);
  214.     if (xxs instanceof Cons) {
  215.       return xxs.cdr;
  216.     } else {
  217.       throw "tail: empty list";
  218.     }
  219.   });
  220. });
  221.  
  222. // fib = 0 : 1 : zipWith (+) fib (tail fib)
  223. var fib = new Thunk(function () {
  224.   return Apply(Apply(cons)(zero))
  225.                           (Apply(Apply(cons)(one))
  226.                                             (Apply(Apply(Apply(zipWith)(add))(fib))(Apply(tail)(fib))));
  227. });
  228.  
  229. Evaluate(Apply(Apply(mapM_)(print))(Apply(Apply(take)(twenty))(fib)));
  230.  
  231.  
Success #stdin #stdout 0.7s 10928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
https://ideone.com/6HJhqA
language:
Node.js (node 11.12.0)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!