fork(1) 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. // inf = 0 : map (+1) inf
  179. var inf = new Thunk(function () {
  180.   return Apply(Apply(cons)(zero))
  181.                           (Apply(Apply(map)(Apply(add)(one)))(inf));
  182. });
  183.  
  184. var twenty = new Thunk(function () { return 20; });
  185.  
  186. Evaluate(Apply(Apply(mapM_)(print))(Apply(Apply(take)(twenty))(inf)));
  187.  
Success #stdin #stdout 0.07s 10472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
https://ideone.com/KXT74d
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!