lambda.dart

//Y-Combinator
final Y = (f) =>
  ((x) => f((y) => x(x)(y)))
  ((x) => f((y) => x(x)(y)));


//booleans
final TRUE = (x) => (y) => x;
final FALSE = (x) => (y) => y;
final cond = (b) => b;


//pairs and lists
final pair = (x) => (y) => (f) => f(x)(y);
final left = (p) => p(TRUE);
final right = (p) => p(FALSE);

final empty = pair(TRUE)(TRUE);
final cons = (x) => (l) => pair(FALSE)(pair(x)(l));
final isEmpty = left;
final first = (l) => left(right(l));
final rest = (l) => right(right(l));


//numbers
final ZERO = (p) => (x) => x;
final ONE = (p) => (x) => p(x);
final TWO = (p) => (x) => p(p(x));
final THREE = (p) => (x) => p(p(p(x)));
final FOUR = (p) => (x) => p(p(p(p(x))));
final FIVE = (p) => (x) => p(p(p(p(p(x)))));
final SIX = (p) => (x) => p(p(p(p(p(p(x))))));
final SEVEN = (p) => (x) => p(p(p(p(p(p(p(x)))))));
final EIGHT = (p) => (x) => p(p(p(p(p(p(p(p(x))))))));
final NINE = (p) => (x) => p(p(p(p(p(p(p(p(p(x)))))))));
final TEN = (p) => (x) => p(p(p(p(p(p(p(p(p(p(x))))))))));

final slide = (p) => pair(right(p))(inc(right(p)));
final inc = (n) => (p) => (x) => p(n(p)(x));
final dec = (n) => left(n(slide)(pair(ZERO)(ZERO)));
final add = (m) => (n) => n(inc)(m);
final sub = (m) => (n) => n(dec)(m);
final multiply = (m) => (n) => n(add(m))(ZERO);

final isZero = (n) => n((_) => FALSE)(TRUE);
final isLessOrEqualTo = (m) => (n) => isZero(sub(m)(n));

final mod = Y((f) => (n) => (m) =>
  cond(isLessOrEqualTo(n)(m))
    ((x) => f(n)(sub(m)(n))(x))
    (m));


//higher-order functions
final compose = (f) => (g) => (x) => f(g(x));

final fold = Y((f) => (l) => (x) => (g) =>
  cond(isEmpty(l))
    (x)
    ((y) => g(f(rest(l))(x)(g))(first(l))(y)));

final map = (k) => (f) =>
  fold(k)
    (empty)
    ((l) => (x) =>
      cons(f(x))(l));

final filter = (k) => (f) =>
  fold(k)
    (empty)
    ((l) => (x) =>
      cond(f(x))
        (cons(x)(l))
        (l));


//utility functions to covert lambda-expressions to Dart primitives
toDartInteger(lambdaInteger) => lambdaInteger((n) => n + 1)(0);
toDartBoolean(lambdaBoolean) => lambdaBoolean(true)(false);
toDartList(list){
  final res = [];
  while(! toDartBoolean(isEmpty(list))){
    res.add(toDartInteger(first(list)));
    list = rest(list);
  }
  return res;
}


//example
main(){
  final isEven = compose(isZero)(mod(TWO));

  final list = cons(EIGHT)
                (cons(SEVEN)
                  (cons(FIVE)
                    (cons(TWO)
                      (empty))));

  final res = map(
                filter(list)(isEven))
                (multiply(TEN));

  print(toDartList(res));

// The same program written in Dart
// [8,7,5,2].where((_) => _.isEven).map((_) => _ * 10).toList();
}