Lambda Calculus for People who can't be bothered with.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All tests passed.\n"
     ]
    }
   ],
   "source": [
    "// Lambda Calculus for People Who Can't Be Bothered to Learn it\n",
    "// Steven Syrek\n",
    "\n",
    "/* operations\n",
    "\n",
    "ɑ-substitution\n",
    "(x => x)(1) === (y => y)(1)\n",
    "\n",
    "β-reduction\n",
    "(x => x)(y => y)(1) === (y => y)(1)\n",
    "(y => y)(1) === 1\n",
    "\n",
    "η-conversion\n",
    "f = x => x\n",
    "(x => f(x))(1) === f(1)\n",
    "\n",
    "*/\n",
    "\n",
    "// identity combinator\n",
    "\n",
    "ID = x => x\n",
    "\n",
    "// boolean primitives\n",
    "\n",
    "TRUE = x => y => x\n",
    "\n",
    "FALSE = x => y => y\n",
    "\n",
    "/*\n",
    "\n",
    "TRUE(\"first\")(\"second\") === \"first\"\n",
    "FALSE(\"first\")(\"second\") === \"second\"\n",
    "\n",
    "*/\n",
    "\n",
    "// boolean combinators\n",
    "\n",
    "AND = x => y => x(y)(FALSE)\n",
    "\n",
    "OR = x => y => x(TRUE)(y)\n",
    "\n",
    "NOT = x => x(FALSE)(TRUE)\n",
    "\n",
    "/*\n",
    "\n",
    "AND(TRUE)(TRUE) === TRUE\n",
    "AND(FALSE)(TRUE) === FALSE\n",
    "AND(TRUE)(FALSE) === FALSE\n",
    "AND(FALSE)(FALSE) === FALSE\n",
    "\n",
    "*/\n",
    "\n",
    "// implement XOR\n",
    "\n",
    "// branching\n",
    "\n",
    "IF_THEN_ELSE = p => x => y => p(x)(y)\n",
    "\n",
    "IF_THEN_ELSE = p => x => p(x)\n",
    "\n",
    "IF_THEN_ELSE = p => p\n",
    "\n",
    "IF_THEN_ELSE = ID\n",
    "\n",
    "// natural numbers\n",
    "\n",
    "ZERO = f => x => x\n",
    "\n",
    "ONE = f => x => f(x)\n",
    "\n",
    "TWO = f => x => f(f(x))\n",
    "\n",
    "THREE = f => x => f(f(f(x)))\n",
    "\n",
    "// enumeration\n",
    "\n",
    "SUCC = n => f => x => f(n(f)(x))\n",
    "\n",
    "PRED = n => n(p => z => z(SUCC(p(TRUE)))(p(TRUE)))(z => z(ZERO)(ZERO))(FALSE)\n",
    "\n",
    "SUCC_PAIR = p => PAIR(SECOND(p))(SUCC(SECOND(p)))\n",
    "\n",
    "PRED = n => FIRST(n(SUCC_PAIR)(PAIR(ZERO)(ZERO)))\n",
    "\n",
    "FOUR = SUCC(THREE)\n",
    "\n",
    "// basic arithmetic\n",
    "\n",
    "PLUS = n => m => m(SUCC)(n)\n",
    "\n",
    "MINUS = n => m => m(PRED)(n) // actually \"monus\"\n",
    "\n",
    "MULT = n => m => m(PLUS(n))(ZERO)\n",
    "\n",
    "EXP = n => m => m(n)\n",
    "\n",
    "FIVE = PLUS(TWO)(THREE)\n",
    "\n",
    "/* reduction steps for PLUS(ONE)(TWO)\n",
    "\n",
    "PLUS(ONE)(TWO)\n",
    "(n => m => m(SUCC)(n))(ONE)(TWO)\n",
    "(TWO)(SUCC)(ONE)\n",
    "(f => x => f(f(x)))(SUCC)(ONE)\n",
    "(x => SUCC(SUCC(x)))(ONE)\n",
    "SUCC(SUCC(ONE))\n",
    "SUCC((n => f => x => f(n(f)(x)))(ONE))\n",
    "SUCC((f => x => f(ONE(f)(x))))\n",
    "SUCC((f => x => f((f => x => f(x))(f)(x))))\n",
    "SUCC((f => x => f((x => f(x))(x))))\n",
    "SUCC((f => x => f(f(x))))\n",
    "SUCC(TWO)\n",
    "(n => f => x => f(n(f)(x)))(TWO)\n",
    "f => x => f(TWO(f)(x))\n",
    "f => x => f((f => x => f(f(x)))(f)(x))\n",
    "f => x => f((x => f(f(x)))(x))\n",
    "f => x => f(f(f(x)))\n",
    "THREE\n",
    "\n",
    "*/\n",
    "\n",
    "/* reduction steps for PRED(TWO)\n",
    "\n",
    "PRED(TWO)\n",
    "(n => FIRST(n(SUCC_PAIR)(PAIR(ZERO)(ZERO))))(TWO)\n",
    "FIRST(TWO(SUCC_PAIR)(PAIR(ZERO)(ZERO)))\n",
    "FIRST(TWO(SUCC_PAIR)((x => y => z => z(x)(y))(ZERO)(ZERO)))\n",
    "FIRST(TWO(SUCC_PAIR)((y => z => z(ZERO)(y))(ZERO)))\n",
    "FIRST(TWO(SUCC_PAIR)(z => z(ZERO)(ZERO)))\n",
    "FIRST(TWO(p => PAIR(SECOND(p))(SUCC(SECOND(p))))(z => z(ZERO)(ZERO)))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(SUCC(SECOND((z => z(ZERO)(ZERO)))))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(SUCC((p => p(x => y => y))((z => z(ZERO)(ZERO)))))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(SUCC((z => z(ZERO)(ZERO))(x => y => y)))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(SUCC((x => y => y)(ZERO)(ZERO)))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(SUCC((y => y)(ZERO)))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(SUCC(ZERO))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))((n => f => x => f(n(f)(x)))(ZERO))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(f => x => f(ZERO(f)(x)))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(f => x => f((f => x => x)(f)(x)))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(f => x => f((x => x)(x)))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(f => x => f(x))))\n",
    "FIRST(TWO(PAIR(SECOND(z => z(ZERO)(ZERO)))(ONE)))\n",
    "FIRST(TWO(PAIR((p => p(x => y => y))(z => z(ZERO)(ZERO)))(ONE)))\n",
    "FIRST(TWO(PAIR(((z => z(ZERO)(ZERO))(x => y => y)))(ONE)))\n",
    "FIRST(TWO(PAIR(((x => y => y(ZERO)(ZERO))))(ONE)))\n",
    "FIRST(TWO(PAIR(y => y(ZERO))(ONE)))\n",
    "FIRST(TWO(PAIR(ZERO)(ONE)))\n",
    "FIRST(TWO((x => y => z => z(x)(y))(ZERO)(ONE)))\n",
    "FIRST(TWO((y => z => z(ZERO)(y))(ONE)))\n",
    "FIRST(TWO(z => z(ZERO)(ONE)))\n",
    "FIRST((f => x => f(f(x)))(z => z(ZERO)(ONE)))\n",
    "FIRST(x => (z => z(ZERO)(ONE))((z => z(ZERO)(ONE))(x)))\n",
    "FIRST(x => (((z => z(ZERO)(ONE))(x))(ZERO)(ONE)))\n",
    "FIRST(x => ((x(ZERO)(ONE))(ZERO)(ONE)))\n",
    "(p => p(x => y => x))(x => ((x(ZERO)(ONE))(ZERO)(ONE)))\n",
    "((x => ((x(ZERO)(ONE))(ZERO)(ONE)))(x => y => x))\n",
    "((x => y => x)(ZERO)(ONE))(ZERO)(ONE)\n",
    "((y => ZERO)(ONE))(ZERO)(ONE)\n",
    "ZERO(ZERO)(ONE)\n",
    "(f => x => x)(ZERO)(ONE)\n",
    "(x => x)(ONE)\n",
    "ONE\n",
    "\n",
    "*/\n",
    "\n",
    "// implement SIX through TEN using any combination of the above functions\n",
    "\n",
    "// implement a function for the equation (n + 5)^3\n",
    "\n",
    "// comparison\n",
    "\n",
    "IS_ZERO = n => n(m => FALSE)(TRUE)\n",
    "\n",
    "LESS_THAN_OR_EQUAL = n => m => IS_ZERO(MINUS(n)(m))\n",
    "\n",
    "LESS_THAN = n => m => AND(LESS_THAN_OR_EQUAL(n)(m))\n",
    "                         (NOT(IS_ZERO(n(PRED)(m))))\n",
    "\n",
    "EQUALS = n => m => AND(LESS_THAN_OR_EQUAL(n)(m))\n",
    "                      (LESS_THAN_OR_EQUAL(m)(n))\n",
    "\n",
    "GREATER_THAN_OR_EQUAL = n => m => IS_ZERO(n(PRED)(m))\n",
    "\n",
    "GREATER_THAN = n => m => AND(GREATER_THAN_OR_EQUAL(n)(m))\n",
    "                            (NOT(IS_ZERO(MINUS(n)(m))))\n",
    "\n",
    "// implement MAX\n",
    "\n",
    "// implement MIN in terms of MAX\n",
    "\n",
    "// function composition\n",
    "\n",
    "COMPOSE = f => g => x => f(g(x))\n",
    "\n",
    "NOT_ZERO = COMPOSE(NOT)(IS_ZERO)\n",
    "\n",
    "// recursion\n",
    "\n",
    "FIX = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)))\n",
    "\n",
    "// advanced arithmetic\n",
    "\n",
    "MOD = FIX(r => n => m =>\n",
    "  IF_THEN_ELSE(LESS_THAN_OR_EQUAL(m)(n))\n",
    "    (x => r(MINUS(n)(m))(m)(x))\n",
    "    (n))\n",
    "\n",
    "DIV = FIX(r => n => m =>\n",
    "  IF_THEN_ELSE(LESS_THAN_OR_EQUAL(m)(n))\n",
    "    (x => SUCC(r(MINUS(n)(m))(m))(x))\n",
    "    (ZERO))\n",
    "\n",
    "// implement a function EVEN that, given a number n, returns true if n is even and false otherwise\n",
    "\n",
    "// implement ODD in terms of EVEN, using composition\n",
    "\n",
    "// factorial\n",
    "\n",
    "F = f => n => IS_ZERO(n)(ONE)(x => MULT(n)(f(PRED(n)))(x))\n",
    "\n",
    "FACT = FIX(F)\n",
    "\n",
    "FACT = FIX(r => n =>\n",
    "  IS_ZERO(n)\n",
    "    (ONE)\n",
    "    (x => MULT(n)(r(PRED(n)))(x)))\n",
    "\n",
    "/* reduction steps for FACT(TWO)\n",
    "\n",
    "FACT(TWO)\n",
    "FIX(F)(TWO)\n",
    "(Y => (x => Y(y => x(x)(y)))(x => Y(y => x(x)(y))))(F)(TWO)\n",
    "(x => F(y => x(x)(y)))(x => F(y => x(x)(y)))(TWO)\n",
    "F(y => (x => F(y => x(x)(y)))(x => F(y => x(x)(y)))(y))(TWO)\n",
    "F(FIX(F))(TWO)\n",
    "(f => n => IS_ZERO(n)(ONE)(x => MULT(n)(f(PRED(n)))(x)))(FIX(F))(TWO)\n",
    "(n => IS_ZERO(n)(ONE)(x => MULT(n)(FIX(F)(PRED(n)))(x)))(TWO)\n",
    "IS_ZERO(TWO)(ONE)(x => MULT(TWO)(FIX(F)(PRED(TWO)))(x))\n",
    "x => MULT(TWO)(FIX(F)(PRED(TWO)))(x)\n",
    "x => MULT(TWO)(FIX(F)(ONE))(x)\n",
    "x => MULT(TWO)(FACT(ONE))(x)\n",
    "x => MULT(TWO)(ONE)(x)\n",
    "MULT(TWO)(ONE)\n",
    "TWO\n",
    "\n",
    "*/\n",
    "\n",
    "FACT_EXP = (f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))(f => n => (n => n(x => x => y => y)(x => y => x))(n)(f => x => f(x))(x => (n => m => m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(n)(f((n => n(p => z => z((n => f => x => f(n(f)(x)))(p(x => y => x)))(p(x => y => x)))(z => z(f => x => x)(f => x => x))(x => y => y))(n)))(x)))\n",
    "\n",
    "/* How to implement recursive lambda functions in a strict language\n",
    "\n",
    "1. Write the function as you normally would without a fixpoint combinator:\n",
    "\n",
    "FACT = n =>\n",
    "  IS_ZERO(n)\n",
    "    (ONE)\n",
    "    (MULT(n)(FACT(PRED(n))))\n",
    "\n",
    "2. Wrap the whole thing in FIX, add a parameter to the front of the definition, and replace all recursive function calls with that parameter:\n",
    "\n",
    "FACT = FIX(r => n =>\n",
    "  IS_ZERO(n)\n",
    "    (ONE)\n",
    "    (MULT(n)(r(PRED(n)))))\n",
    "\n",
    "3. Wrap the recursive branch of your function in a dummy closure by adding a parameter to the front of that branch and applying the last function in that branch to the same parameter:\n",
    "\n",
    "FACT = FIX(r => n =>\n",
    "  IS_ZERO(n)\n",
    "    (ONE)\n",
    "    (x => MULT(n)(r(PRED(n)))(x)))\n",
    "\n",
    "*/\n",
    "\n",
    "// implement fibonacci\n",
    "\n",
    "// pairs\n",
    "\n",
    "PAIR = x => y => p => p(x)(y)\n",
    "\n",
    "FIRST = p => p(x => y => x)\n",
    "\n",
    "SECOND = p => p(x => y => y)\n",
    "\n",
    "// n-ary tuples\n",
    "\n",
    "TRIPLE = x => y => z => p => p(x)(y)(z)\n",
    "\n",
    "THIRD = p => p(x => y => z => z) // FIRST and SECOND will not work for this\n",
    "\n",
    "// implement 4-tuples and the fourth projection\n",
    "\n",
    "// lists\n",
    "\n",
    "LIST_ELEMENT = x => xs => PAIR(FALSE)(PAIR(x)(xs))\n",
    "\n",
    "EMPTY_LIST = PAIR(TRUE)(TRUE)\n",
    "\n",
    "IS_EMPTY = FIRST\n",
    "\n",
    "HEAD = xs => FIRST(SECOND(xs))\n",
    "\n",
    "TAIL = xs => SECOND(SECOND(xs))\n",
    "\n",
    "// fold/map/filter\n",
    "\n",
    "FOLD = FIX(r => f => z => xs =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (z)\n",
    "    (x => f(HEAD(xs))(r(f)(z)(TAIL(xs)))(x)))\n",
    "\n",
    "MAP = f => FOLD(x => xs => LIST_ELEMENT(f(x))(xs))(EMPTY_LIST)\n",
    "\n",
    "/* Haskell map\n",
    "\n",
    "map f xs = foldr (\\x xs -> f x : xs) [] xs\n",
    "\n",
    "map f = foldr (\\x xs -> f x : xs) []\n",
    "\n",
    "map          :: (a -> b) -> [a] -> [b]\n",
    "map _ []     =  []\n",
    "map f (x:xs) =  f x : map f xs\n",
    "\n",
    "MAP = FIX(r => f => xs =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (EMPTY_LIST)\n",
    "    (x => LIST_ELEMENT(f(HEAD(xs)))(r(f)(TAIL(xs)))(x)))\n",
    "\n",
    "map f = foldr ((:) . f) []\n",
    "\n",
    "MAP = f => FOLD(COMPOSE(LIST_ELEMENT)(f))(EMPTY_LIST)\n",
    "\n",
    "*/\n",
    "\n",
    "FILTER = p => FOLD(x => xs =>\n",
    "  IF_THEN_ELSE(p(x))\n",
    "    (LIST_ELEMENT(x)(xs))\n",
    "    (xs))\n",
    "  (EMPTY_LIST)\n",
    "\n",
    "/*\n",
    "\n",
    "toInt(FOLD(PLUS)(ZERO)(LIST))    // = 6\n",
    "toArrayInt(MAP(PLUS(ONE))(LIST)) // = [2,3,4]\n",
    "toArrayInt(FILTER(EVEN)(LIST))   // = [2]\n",
    "\n",
    "*/\n",
    "\n",
    "// return to factorial\n",
    "\n",
    "AND_EQUALS_TWO = COMPOSE(AND)(EQUALS(TWO))\n",
    "\n",
    "ALL_TWOS = FOLD(AND_EQUALS_TWO)(TRUE)\n",
    "\n",
    "FACT_CHECK = ALL_TWOS(\n",
    "  LIST_ELEMENT(\n",
    "    FACT(TWO)\n",
    "  )(LIST_ELEMENT(\n",
    "    FIX(F)(TWO)\n",
    "  )(LIST_ELEMENT(\n",
    "    (r => (x => r(y => x(x)(y)))(x => r(y => x(x)(y))))(F)(TWO)\n",
    "  )(LIST_ELEMENT(\n",
    "    (x => F(y => x(x)(y)))(x => F(y => x(x)(y)))(TWO)\n",
    "  )(LIST_ELEMENT(\n",
    "    F(y => (x => F(y => x(x)(y)))(x => F(y => x(x)(y)))(y))(TWO)\n",
    "  )(LIST_ELEMENT(\n",
    "    F(FIX(F))(TWO)\n",
    "  )(LIST_ELEMENT(\n",
    "    (f => n => IS_ZERO(n)(ONE)(x => MULT(n)(f(PRED(n)))(x)))(FIX(F))(TWO)\n",
    "  )(LIST_ELEMENT(\n",
    "    (n => IS_ZERO(n)(ONE)(x => MULT(n)(FIX(F)(PRED(n)))(x)))(TWO)\n",
    "  )(LIST_ELEMENT(\n",
    "    IS_ZERO(TWO)(ONE)(x => MULT(TWO)(FIX(F)(PRED(TWO)))(x))\n",
    "  )(LIST_ELEMENT(\n",
    "    x => MULT(TWO)(FIX(F)(PRED(TWO)))(x)\n",
    "  )(LIST_ELEMENT(\n",
    "    x => MULT(TWO)(FIX(F)(ONE))(x)\n",
    "  )(LIST_ELEMENT(\n",
    "    x => MULT(TWO)(FACT(ONE))(x)\n",
    "  )(LIST_ELEMENT(\n",
    "    x => MULT(TWO)(ONE)(x)\n",
    "  )(LIST_ELEMENT(\n",
    "    MULT(TWO)(ONE)\n",
    "  )(LIST_ELEMENT(\n",
    "    TWO\n",
    "  )(EMPTY_LIST)))))))))))))))\n",
    ")\n",
    "\n",
    "// other list functions\n",
    "\n",
    "RANGE = FIX(r => m => n =>\n",
    "  IF_THEN_ELSE(LESS_THAN_OR_EQUAL(m)(n))\n",
    "    (x => LIST_ELEMENT(m)(r(SUCC(m))(n))(x))\n",
    "    (EMPTY_LIST))\n",
    "\n",
    "INDEX = FIX(r => xs => n =>\n",
    "  IF_THEN_ELSE(IS_ZERO(n))\n",
    "    (HEAD(xs))\n",
    "    (x => r(TAIL(xs))(PRED(n))(x)))\n",
    "\n",
    "PUSH = x => xs => FOLD(LIST_ELEMENT)(LIST_ELEMENT(x)(EMPTY_LIST))(xs)\n",
    "\n",
    "APPEND = FIX(r => xs => ys =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (ys)\n",
    "    (x => LIST_ELEMENT(HEAD(xs))(r(TAIL(xs))(ys))(x)))\n",
    "\n",
    "REVERSE = xs => (FIX(r => xs => a => // implicit helper function\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (a)\n",
    "    (x => (r(TAIL(xs))(LIST_ELEMENT(HEAD(xs))(a)))(x))))\n",
    "  (xs)(EMPTY_LIST)\n",
    "\n",
    "TAKE = FIX(r => n => xs =>\n",
    "  IF_THEN_ELSE(LESS_THAN_OR_EQUAL(n)(ZERO))\n",
    "    (EMPTY_LIST)\n",
    "    (IF_THEN_ELSE(IS_EMPTY(xs)))\n",
    "      (EMPTY_LIST)\n",
    "      (x => LIST_ELEMENT(HEAD(xs))(r(MINUS(n)(ONE))(TAIL(xs)))(x)))\n",
    "\n",
    "ZIP = FIX(r => xs => ys =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (EMPTY_LIST)\n",
    "    (IF_THEN_ELSE(IS_EMPTY(ys))\n",
    "      (EMPTY_LIST)\n",
    "      (x => LIST_ELEMENT(PAIR(HEAD(xs))(HEAD(ys)))(r(TAIL(xs))(TAIL(ys)))(x))))\n",
    "\n",
    "ZIP_WITH = FIX(r => f => xs => ys =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (EMPTY_LIST)\n",
    "    (IF_THEN_ELSE(IS_EMPTY(ys))\n",
    "      (EMPTY_LIST)\n",
    "      (x => LIST_ELEMENT(f(HEAD(xs))(HEAD(ys)))(r(f)(TAIL(xs))(TAIL(ys)))(x))))\n",
    "\n",
    "/* example of zipping\n",
    "\n",
    "LIST = LIST_ELEMENT(ONE)(LIST_ELEMENT(TWO)(LIST_ELEMENT(THREE)(EMPTY_LIST)))\n",
    "\n",
    "toArray(ZIP(LIST)(LIST)).map(x => printPair(toPairInt(x))) // = [(1,1),(2,2),(3,3)]\n",
    "toArrayInt(ZIP_WITH(PLUS)(LIST)(LIST))                     // = [2,4,6]\n",
    "\n",
    "*/\n",
    "\n",
    "INSERT = FIX(r => n => xs =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (LIST_ELEMENT(n)(EMPTY_LIST))\n",
    "    (IF_THEN_ELSE(GREATER_THAN(n)(HEAD(xs)))\n",
    "      (x => LIST_ELEMENT(HEAD(xs))(r(n)(TAIL(xs)))(x))\n",
    "      (LIST_ELEMENT(n)(xs))))\n",
    "\n",
    "SORT = FOLD(INSERT)(EMPTY_LIST)\n",
    "\n",
    "/*\n",
    "\n",
    "toArrayInt(SORT(REVERSE(LIST))) // = [1,2,3]\n",
    "\n",
    "*/\n",
    "\n",
    "/* implementation of TAKE from Haskell to JavaScript lambdas\n",
    "\n",
    "take                   :: Int -> [a] -> [a]\n",
    "take n _      | n <= 0 =  []\n",
    "take _ []              =  []\n",
    "take n (x:xs)          =  x : take (n-1) xs\n",
    "\n",
    "TAKE = n => xs =>\n",
    "  IF_THEN_ELSE(LESS_THAN_OR_EQUAL(n)(ZERO))(EMPTY_LIST)\n",
    "  (IF_THEN_ELSE(IS_EMPTY(xs)))(EMPTY_LIST)\n",
    "  (LIST_ELEMENT(HEAD(xs))(TAKE(MINUS(n)(ONE))(TAIL(xs))))\n",
    "\n",
    "TAKE = FIX(r => n => xs =>\n",
    "  IF_THEN_ELSE(LESS_THAN_OR_EQUAL(n)(ZERO))\n",
    "    (EMPTY_LIST)\n",
    "    (IF_THEN_ELSE(IS_EMPTY(xs)))\n",
    "      (EMPTY_LIST)\n",
    "      (x => LIST_ELEMENT(HEAD(xs))(r(MINUS(n)(ONE))(TAIL(xs)))(x)))\n",
    "\n",
    "*/\n",
    "\n",
    "// implement DROP\n",
    "\n",
    "/*\n",
    "\n",
    "drop                   :: Int -> [a] -> [a]\n",
    "drop n xs     | n <= 0 =  xs\n",
    "drop _ []              =  []\n",
    "drop n (_:xs)          =  drop (n-1) xs\n",
    "\n",
    "*/\n",
    "\n",
    "// implement LENGTH (HINT: use an implicit helper function)\n",
    "\n",
    "// streams\n",
    "\n",
    "ZEROS = FIX(r => LIST_ELEMENT(ZERO)(r))\n",
    "\n",
    "REPEAT = x => FIX(r => LIST_ELEMENT(x)(r))\n",
    "\n",
    "/* example of streams\n",
    "\n",
    "toArrayInt(TAKE(TEN)(ZEROS))          // = [0,0,0,0,0,0,0,0,0,0]\n",
    "toArrayInt(TAKE(TEN)(REPEAT(NINE)))   // = [9,9,9,9,9,9,9,9,9]\n",
    "toInt(LENGTH(TAKE(TEN)(REPEAT(TEN)))) // error!\n",
    "\n",
    "*/\n",
    "\n",
    "// universal properties of fold\n",
    "\n",
    "SUM = FIX(r => xs =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (ZERO)\n",
    "    (x => PLUS(HEAD(xs))(r(TAIL(xs)))(x)))\n",
    "\n",
    "SUM_FOLD = FOLD(PLUS)(ZERO)\n",
    "\n",
    "PRODUCT_FOLD = FOLD(MULT)(ONE) // here there be monoids!\n",
    "\n",
    "/*\n",
    "\n",
    "LIST = RANGE(ONE)(TEN)\n",
    "toInt(SUM_FOLD(LIST)) === toInt(SUM(LIST))\n",
    "\n",
    "*/\n",
    "\n",
    "LENGTH_FOLD = FOLD(x => n => PLUS(ONE)(n))(ZERO)\n",
    "\n",
    "REVERSE_FOLD = FOLD(x => xs => APPEND(xs)(LIST_ELEMENT(x)(EMPTY_LIST)))(EMPTY_LIST)\n",
    "\n",
    "FOLDL = f => z => xs => FOLD(x => g => (y => g(f(y)(x))))(ID)(xs)(z)\n",
    "\n",
    "REVERSE_FOLDL = FOLDL(xs => x => LIST_ELEMENT(x)(xs))(EMPTY_LIST) // more efficient\n",
    "\n",
    "// implement AND_FOLD and OR_FOLD\n",
    "\n",
    "// binary numbers using lists\n",
    "\n",
    "B_ZERO = LIST_ELEMENT(ZERO)\n",
    "\n",
    "B_ONE = LIST_ELEMENT(ONE)\n",
    "\n",
    "BINARY_ZERO = B_ZERO(EMPTY_LIST)\n",
    "\n",
    "BINARY_ONE = B_ONE(EMPTY_LIST)\n",
    "\n",
    "BINARY_TWO = B_ONE(B_ZERO)(EMPTY_LIST)\n",
    "\n",
    "BINARY_THREE = B_ONE(B_ONE)(EMPTY_LIST)\n",
    "\n",
    "// trees\n",
    "\n",
    "EMPTY_TREE = EMPTY_LIST\n",
    "\n",
    "NODE = v => l => r => LIST_ELEMENT(v)(LIST_ELEMENT(l)(LIST_ELEMENT(r)(EMPTY_TREE)))\n",
    "\n",
    "VALUE = t => HEAD(t)\n",
    "\n",
    "LEFT = t => HEAD(TAIL(t))\n",
    "\n",
    "RIGHT = t => HEAD(TAIL(TAIL(t)))\n",
    "\n",
    "/*\n",
    "\n",
    "TREE = NODE(TWO)(NODE(ONE)(EMPTY_TREE)(EMPTY_TREE))(NODE(THREE)(EMPTY_TREE)(EMPTY_TREE))\n",
    "\n",
    "toInt(VALUE(TREE))         // = 2\n",
    "\n",
    "toInt(VALUE(LEFT(TREE)))   // = 1\n",
    "\n",
    "toInt(VALUE(RIGHT(TREE)))  // = 3\n",
    "\n",
    "printTree(toTreeInt(TREE)) // = [2, [1, [], []], [3, [], []]]\n",
    "\n",
    "*/\n",
    "\n",
    "// functional structures (list implementations)\n",
    "\n",
    "// monoid\n",
    "\n",
    "MEMPTY = EMPTY_LIST\n",
    "\n",
    "MAPPEND = APPEND\n",
    "\n",
    "// functor\n",
    "\n",
    "FMAP = MAP\n",
    "\n",
    "// applicative\n",
    "\n",
    "PURE = x => LIST_ELEMENT(x)(EMPTY_LIST)\n",
    "\n",
    "AP = FIX(r => fs => xs =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (EMPTY_LIST)\n",
    "    (IF_THEN_ELSE(IS_EMPTY(fs))(EMPTY_LIST)\n",
    "      (x => MAPPEND(MAP(HEAD(fs))(xs))(r(TAIL(fs))(xs))(x))))\n",
    "\n",
    "AP_ZIP_LIST = fs => xs =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (EMPTY_LIST)\n",
    "    (IF_THEN_ELSE(IS_EMPTY(fs))(EMPTY_LIST)\n",
    "      (ZIP_WITH(ID)(fs)(xs)))\n",
    "\n",
    "/*\n",
    "\n",
    "LIST = RANGE(ONE)(TEN)\n",
    "\n",
    "FUNC_LIST = MAP(PLUS)(LIST)\n",
    "\n",
    "AP_LIST = AP(FUNC_LIST)(LIST)\n",
    "\n",
    "ZIP_LIST = AP_ZIP_LIST(FUNC_LIST)(REVERSE(LIST))\n",
    "\n",
    "toArrayInt(AP_LIST) // = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n",
    "\n",
    "toArrayInt(ZIP_LIST) // = [11, 11, 11, 11, 11, 11, 11, 11, 11, 11]\n",
    "\n",
    "*/\n",
    "\n",
    "// monad\n",
    "\n",
    "RETURN = PURE\n",
    "\n",
    "BIND = FIX(r => xs => f =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))\n",
    "    (EMPTY_LIST)\n",
    "    (x => MAPPEND(f(HEAD(xs)))(r(TAIL(xs))(f))(x)))\n",
    "\n",
    "/*\n",
    "\n",
    "BIND_PLUS = x => RETURN(PLUS(x)(ONE))\n",
    "\n",
    "BIND_SQUARE = x => RETURN(EXP(x)(TWO))\n",
    "\n",
    "BIND_CUBE = x => RETURN(EXP(x)(THREE))\n",
    "\n",
    "BIND_LIST = BIND(BIND(LIST)(BIND_SQUARE))(BIND_CUBE)\n",
    "\n",
    "BIND_ADDS = BIND(BIND(BIND(BIND(BIND(LIST)(BIND_PLUS))(BIND_PLUS))(BIND_PLUS))(BIND_PLUS))(BIND_PLUS)\n",
    "\n",
    "*/\n",
    "\n",
    "// implement any function of your choice\n",
    "\n",
    "// utility functions\n",
    "\n",
    "toBool = b => IF_THEN_ELSE(b)(true)(false)\n",
    "\n",
    "fromBool = b => b ? TRUE : FALSE\n",
    "\n",
    "toInt = n => n(x => x + 1)(0)\n",
    "\n",
    "fromInt = n => n == 0 ? f => x => x : f => x => f(fromInt(n - 1)(f)(x))\n",
    "\n",
    "toArray = xs => [].concat(toBool(IS_EMPTY(xs)) ? [] : [HEAD(xs)].concat(toArray(TAIL(xs))))\n",
    "\n",
    "fromArray = xs => xs.length === 0 ? EMPTY_LIST : LIST_ELEMENT(xs[0])(fromArray(xs.slice(1)))\n",
    "\n",
    "toArrayInt = xs => [].concat(toBool(IS_EMPTY(xs)) ? [] : [toInt(HEAD(xs))].concat(toArrayInt(TAIL(xs))))\n",
    "\n",
    "fromArrayInt = xs => xs.length === 0 ? EMPTY_LIST : LIST_ELEMENT(fromInt(xs[0]))(fromArrayInt(xs.slice(1)))\n",
    "\n",
    "toPair = p => {\n",
    "  return {fst: FIRST(p), snd: SECOND(p)}\n",
    "}\n",
    "\n",
    "toPairInt = p => {\n",
    "  return {fst: (toInt(FIRST(p))), snd: (toInt(SECOND(p)))}\n",
    "}\n",
    "\n",
    "printPair = p => `(${p.fst},${p.snd})`\n",
    "\n",
    "toString = str => toArrayInt(str).map(n => String.fromCharCode(n)).join(\"\")\n",
    "\n",
    "fromString = str => str.length === 0 ? EMPTY_LIST : LIST_ELEMENT(fromInt(str.charCodeAt(str[0])))(fromString(str.substr(1)))\n",
    "\n",
    "toTreeInt = t => toBool(IS_EMPTY(t)) ? [] : [toInt(VALUE(t)), toTreeInt(LEFT(t)), toTreeInt(RIGHT(t))]\n",
    "\n",
    "printTree = t => t.length === 0 ? \"[]\" : `[${t[0]}, ${printTree(t[1])}, ${printTree(t[2])}]`\n",
    "\n",
    "toLambda = x => {\n",
    "  if (Number.isInteger(x)) return fromInt(x)\n",
    "  if (typeof x === \"boolean\") return fromBool(x)\n",
    "  if (typeof x === 'string') return fromString(x)\n",
    "  if (Array.isArray(x)) return fromArray(x.map(y => toLambda(y)))\n",
    "  return x\n",
    "}\n",
    "\n",
    "// tests\n",
    "\n",
    "p = PAIR(ONE)(TWO)\n",
    "l = RANGE(ONE)(THREE)\n",
    "t = NODE(TWO)(NODE(ONE)(EMPTY_TREE)(EMPTY_TREE))(NODE(THREE)(EMPTY_TREE)(EMPTY_TREE))\n",
    "\n",
    "tests = {\n",
    "  id: ID(1) === 1,\n",
    "  true: TRUE(1)(0) === 1,\n",
    "  false: FALSE(1)(0) === 0,\n",
    "  and: toBool(AND(FALSE)(TRUE)) === false,\n",
    "  or: toBool(OR(FALSE)(TRUE)) === true,\n",
    "  not: toBool(NOT(TRUE)) === false,\n",
    "  ifThenElse: toBool(IF_THEN_ELSE(IS_ZERO(ZERO))(TRUE)(FALSE)) === true,\n",
    "  zero: toInt(ZERO) === 0,\n",
    "  one: toInt(ONE) === 1,\n",
    "  two: toInt(TWO) === 2,\n",
    "  three: toInt(THREE) === 3,\n",
    "  four: toInt(FOUR) === 4,\n",
    "  five: toInt(FIVE) === 5,\n",
    "  succ: toInt(SUCC(ONE)) === 2,\n",
    "  pred: toInt(PRED(ONE)) === 0,\n",
    "  plus: toInt(PLUS(TWO)(TWO)) === 4,\n",
    "  minus: toInt(MINUS(TWO)(ONE)) === 1,\n",
    "  mult: toInt(MULT(TWO)(THREE)) === 6,\n",
    "  exp: toInt(EXP(TWO)(THREE)) === 8,\n",
    "  isZero: toBool(IS_ZERO(ZERO)) === true,\n",
    "  lessThanOrEqual: toBool(LESS_THAN_OR_EQUAL(ZERO)(ZERO)) === true,\n",
    "  lessThan: toBool(LESS_THAN(ZERO)(ONE)) === true,\n",
    "  equals: toBool(EQUALS(ONE)(ONE)) === true,\n",
    "  greaterThanOrEqual: toBool(GREATER_THAN_OR_EQUAL(ONE)(ZERO)) === true,\n",
    "  greaterThan: toBool(GREATER_THAN(ONE)(ZERO)) === true,\n",
    "  compose: COMPOSE(ID)(ID)(1) === ID(ID(1)),\n",
    "  mod: toInt(MOD(FOUR)(TWO)) === 0,\n",
    "  div: toInt(DIV(FOUR)(TWO)) === 2,\n",
    "  pair: toPairInt(p).fst === 1 && toPairInt(p).snd === 2,\n",
    "  first: toInt(FIRST(p)) === 1,\n",
    "  second: toInt(SECOND(p)) === 2,\n",
    "  emptyList: toBool(AND(FIRST(EMPTY_LIST))(SECOND(EMPTY_LIST))) === true,\n",
    "  isEmpty: toBool(AND(IS_EMPTY(EMPTY_LIST))(NOT(IS_EMPTY(l)))) === true,\n",
    "  head: toInt(HEAD(l)) === 1,\n",
    "  tail: toArrayInt(TAIL(l)).every((e,i) => e === [2,3][i]),\n",
    "  fold: toInt(FOLD(PLUS)(ZERO)(l)) === 6,\n",
    "  map: toArrayInt(MAP(PLUS(ONE))(l)).every((e,i) => e === [2,3,4][i]),\n",
    "  filter: toArrayInt(FILTER(GREATER_THAN(THREE))(l)).every((e,i) => e === [1,2][i]),\n",
    "  range: toArrayInt(l).every((e,i) => e === [1,2,3][i]),\n",
    "  index: toInt(INDEX(l)(ZERO)) === 1,\n",
    "  push: toArrayInt(PUSH(FOUR)(l)).every((e,i) => e === [1,2,3,4][i]),\n",
    "  append: toArrayInt(APPEND(l)(l)).every((e,i) => e === [1,2,3,1,2,3][i]),\n",
    "  reverse: toArrayInt(REVERSE(l)).every((e,i) => e === [3,2,1][i]),\n",
    "  take: toArrayInt(TAKE(TWO)(l)).every((e,i) => e === [1,2][i]),\n",
    "  zip: toArray(ZIP(l)(l)).map(x => toPairInt(x)).every((e,i) => e.fst === i+1 && e.snd === i+1),\n",
    "  zipWith: toArrayInt(ZIP_WITH(PLUS)(l)(REVERSE(l))).every((e,i) => e === [4,4,4][i]),\n",
    "  insert: toArrayInt(INSERT(ZERO)(l)).every((e,i) => e === [0,1,2,3][i]),\n",
    "  sort: toArrayInt(SORT(REVERSE(l))).every((e,i) => e === toArrayInt(l)[i]),\n",
    "  zeros: toArrayInt(TAKE(THREE)(ZEROS)).every((e,i) => e === [0,0,0][i]),\n",
    "  repeat: toArrayInt(TAKE(THREE)(REPEAT(ONE))).every((e,i) => e === [1,1,1][i]),\n",
    "  sum: toInt(SUM(l)) === 6,\n",
    "  sumFold: toInt(SUM_FOLD(l)) === 6,\n",
    "  productFold: toInt(PRODUCT_FOLD(l)) === 6,\n",
    "  lengthFold: toInt(LENGTH_FOLD(l)) === 3,\n",
    "  reverseFold: toArrayInt(REVERSE_FOLD(l)).every((e,i) => e === [3,2,1][i]),\n",
    "  foldl: toInt(FOLDL(PLUS)(ZERO)(l)) === 6,\n",
    "  reverseFoldl: toArrayInt(REVERSE_FOLDL(l)).every((e,i) => e === [3,2,1][i]),\n",
    "  tree: printTree(toTreeInt(t)) === \"[2, [1, [], []], [3, [], []]]\",\n",
    "  value: toInt(VALUE(t)) === 2,\n",
    "  left: toInt(VALUE(LEFT(t))) === 1,\n",
    "  right: toInt(VALUE(RIGHT(t))) === 3,\n",
    "  pure: toArrayInt(PURE(ONE))[0] === 1,\n",
    "  ap: toArrayInt(AP(MAP(PLUS)(l))(l)).every((e,i) => e === [2,3,4,3,4,5,4,5,6][i]),\n",
    "  apZipList: toArrayInt(AP_ZIP_LIST(MAP(PLUS)(l))(REVERSE(l))).every((e,i) => e === [4,4,4][i]),\n",
    "  bind: toArrayInt(BIND(l)(RETURN(x => RETURN(PLUS(x)(ONE))))).every((e,i) => e === [2,3,4][i]),\n",
    "  fact: toInt(FACT(TWO)) === 2,\n",
    "  factCheck: toBool(FACT_CHECK),\n",
    "  factExp: toInt(FACT_EXP(TWO)) === 2,\n",
    "}\n",
    "\n",
    "allTests = () => Object.values(tests).reduce((x, y) => x && y)\n",
    "\n",
    "failedTests = () => Object.getOwnPropertyNames(tests).filter((e,i) => !Object.values(tests)[i])\n",
    "\n",
    "console.log(allTests() ? \"All tests passed.\" : `Failed tests: ${failedTests().join(\", \")}`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(x => x)(1) == (y => y)(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: ONE]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ONE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(ONE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toBool(AND(TRUE)(FALSE))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AND(FALSE)(FALSE) === FALSE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "720"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(FACT(MULT(THREE)(TWO)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(FACT_EXP(FIVE))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implement XOR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: XOR]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR = x => y => OR(AND(x)(NOT(y)))(AND(NOT(x))(y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[Function: FALSE] [Function: FALSE] [Function: TRUE] [Function: TRUE]\n"
     ]
    }
   ],
   "source": [
    "console.log(XOR(TRUE)(TRUE), XOR(FALSE)(FALSE), XOR(TRUE)(FALSE), XOR(FALSE)(TRUE))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: XOR1]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR1 = x => y => AND(OR(x)(y))(NOT(AND(x)(y)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FALSE]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR1(TRUE)(TRUE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: XOR1]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR1 = x => y => NOT(AND(x)(y)) // this doesnt work"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: TRUE]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR1(FALSE)(FALSE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "false == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "false === 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[] == false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[] == {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3125"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(EXP(FIVE)(FIVE))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: XOR3]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR3 = x => y => x(NOT(y))(y) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FALSE]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR3(TRUE)(TRUE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: TRUE]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR3(FALSE)(TRUE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: TRUE]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR3(TRUE)(FALSE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FALSE]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR3(FALSE)(FALSE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implement MAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: MAX]"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MAX = x => y => IF_THEN_ELSE(GREATER_THAN_OR_EQUAL(x)(y))(x)(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: THREE]"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MAX(TWO)(THREE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implement MIN in terms of MAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: MIN]"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MIN = x => y => IF_THEN_ELSE(EQUALS(MAX(x)(y))(x))(y)(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: THREE]"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MIN(THREE)(FIVE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: TRUE]"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NOT_ZERO(THREE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FALSE]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NOT_ZERO(ZERO)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implement EVEN check"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: IS_EVEN]"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_EVEN = x => IF_THEN_ELSE(EQUALS(MOD(x)(TWO))(ZERO))(TRUE)(FALSE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: IS_EVEN]"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_EVEN = x => EQUALS(MOD(x)(TWO))(ZERO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: TRUE]"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_EVEN(TWO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FALSE]"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_EVEN(THREE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implement ODD using EVEN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: IS_ODD]"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_ODD = x => IF_THEN_ELSE(IS_EVEN(x))(FALSE)(TRUE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: IS_ODD]"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_ODD = x => NOT(IS_EVEN(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [],
   "source": [
    "// IS_ODD = x => COMPOSE(NOT)(IS_EVEN)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: TRUE]"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_ODD(THREE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FALSE]"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_ODD(TWO)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Y Combinator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: YCOMB]"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "YCOMB = g => (x => g(x)(x))(x => g(x)(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Z Combinator - for call by value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: ZCOMB]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ZCOMB = f => (y => f(z => y(y)(z)))(y => f(z => y(y)(z)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FACT1 = ZCOMB( r => n => \n",
    "             IS_ZERO(n)\n",
    "             (ONE)\n",
    "             (x => MULT(n)(r(PRED(n)))(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(FACT1(FIVE))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: ONE]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_ZERO(ZERO)(ONE)(TWO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: TWO]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IS_ZERO(ONE)(ONE)(TWO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FACT2]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FACT2 = n => IS_ZERO(n)(ONE)(MULT(n)(FACT2(PRED(n))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "ename": "RangeError",
     "evalue": "Maximum call stack size exceeded",
     "output_type": "error",
     "traceback": [
      "evalmachine.<anonymous>:281",
      "FIRST = p => p(x => y => x)",
      "                    ^",
      "",
      "RangeError: Maximum call stack size exceeded",
      "    at y (evalmachine.<anonymous>:281:21)",
      "    at p (evalmachine.<anonymous>:279:27)",
      "    at FIRST (evalmachine.<anonymous>:281:14)",
      "    at PRED (evalmachine.<anonymous>:83:13)",
      "    at FACT2 (evalmachine.<anonymous>:1:44)",
      "    at FACT2 (evalmachine.<anonymous>:1:38)",
      "    at FACT2 (evalmachine.<anonymous>:1:38)",
      "    at FACT2 (evalmachine.<anonymous>:1:38)",
      "    at FACT2 (evalmachine.<anonymous>:1:38)",
      "    at FACT2 (evalmachine.<anonymous>:1:38)"
     ]
    }
   ],
   "source": [
    "FACT2(ONE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(PRED(TWO))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FACT3]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FACT3 = r => n => IF_THEN_ELSE(LESS_THAN_OR_EQUAL(n)(ZERO))(ONE)(x => MULT(n)(r(PRED(n)))(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FACT3 = ZCOMB(FACT3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(FACT3(FIVE))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fibonacci Series using Z Combinator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FIB]"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FIB = r => n => IS_ZERO(n)  (ZERO)(\n",
    "                            (IF_THEN_ELSE(EQUALS(n)(ONE))(ONE))\n",
    "                            (x => (PLUS(r(PRED(n)))(r(PRED(PRED(n)))))(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FIB = ZCOMB(FIB)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "SEVEN = PLUS(FIVE)(TWO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(FIB(SEVEN))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FIB]"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FIB = r => n => IS_ZERO(n)(ZERO)\n",
    "                (EQUALS(n)(ONE)(ONE)\n",
    "                (x => PLUS(r(PRED(n)))(r(PRED(PRED(n))))(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FIB = ZCOMB(FIB)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(FIB(ZERO))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(FIB(TWO))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(PLUS(ONE)(TWO))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(SUM(ONE)(THREE))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(FIB(PLUS(FOUR)(THREE)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FIB]"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FIB = r => n => IS_ZERO(n)(ZERO)\n",
    "                (EQUALS(n)(ONE)(ONE)\n",
    "                (x => PLUS(r(MINUS(n)(ONE)))(r(MINUS(n)(TWO)))(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FIB = ZCOMB(FIB)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(FIB(SEVEN))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: QUADRUPLE]"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "QUADRUPLE = a => b => c => d => p => p(a)(b)(c)(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: FOURTH]"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FOURTH = p => p(a => b => c => d => d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: ONE]"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FOURTH(QUADRUPLE(FOUR)(THREE)(TWO)(ONE))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list = LIST_ELEMENT(ONE)(LIST_ELEMENT(TWO)(LIST_ELEMENT(THREE)(EMPTY_LIST)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "this is the same as  \n",
    "``1:(2:(3:[]))``"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 2, 3 ]"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toArrayInt(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list_sum = SUM(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(list_sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "double = MAP(x => MULT(x)(TWO))(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 2, 4, 6 ]"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toArrayInt(double)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum = FOLD(PLUS)(ZERO)(double)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "even = FILTER(IS_EVEN)(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 2 ]"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toArrayInt(even)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 127,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list = fromArrayInt([2, 3, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list2 = fromArrayInt([2, 2, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toBool(ALL_TWOS(list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toBool(ALL_TWOS(list2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toBool(FACT_CHECK)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 135,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list = RANGE(ONE)(PLUS(FIVE)(FIVE))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]"
      ]
     },
     "execution_count": 136,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toArrayInt(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 137,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toInt(INDEX(list)(ONE))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ]"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toArrayInt(REVERSE(list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1satyajit'"
      ]
     },
     "execution_count": 139,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 + \"satyajit\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'satyajit1'"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"satyajit\" + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'s,atyajit'"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "['s','a'] + \"tyajit\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1,2'"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1,2].toString()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list = fromArrayInt([4,3,2,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 2, 3, 4 ]"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toArrayInt(SORT(list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ZEROS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 0, 0, 0, 0, 0 ]"
      ]
     },
     "execution_count": 152,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toArrayInt(TAKE(FIVE)(ZEROS))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "ename": "RangeError",
     "evalue": "Maximum call stack size exceeded",
     "output_type": "error",
     "traceback": [
      "evalmachine.<anonymous>:495",
      "ZEROS = FIX(r => LIST_ELEMENT(ZERO)(r))",
      "            ^",
      "",
      "RangeError: Maximum call stack size exceeded",
      "    at r (evalmachine.<anonymous>:495:13)",
      "    at FIX.x (evalmachine.<anonymous>:199:40)",
      "    at y (evalmachine.<anonymous>:199:47)",
      "    at FIRST (evalmachine.<anonymous>:281:14)",
      "    at toArrayInt (evalmachine.<anonymous>:658:37)",
      "    at toArrayInt (evalmachine.<anonymous>:658:83)",
      "    at toArrayInt (evalmachine.<anonymous>:658:83)",
      "    at toArrayInt (evalmachine.<anonymous>:658:83)",
      "    at toArrayInt (evalmachine.<anonymous>:658:83)",
      "    at toArrayInt (evalmachine.<anonymous>:658:83)"
     ]
    }
   ],
   "source": [
    "toArrayInt(ZEROS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ '🐔', '🥚' ]"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "['🥚', '🐔'].sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ '🐈', '🐔', '🐕', '👨', '👩', '🥚' ]"
      ]
     },
     "execution_count": 157,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "['🥚', '🐔', '🐈', '🐕', '👨', '👩'].sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ '🐈', '🐕' ]"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "['🐕', '🐈'].sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ '👨', '👩' ]"
      ]
     },
     "execution_count": 161,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "['👩', '👨'].sort()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FizzBuzz with Lambdas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Numbers\n",
    "ZERO = f => x => x;\n",
    "ONE = f => x => f(x);\n",
    "TWO = f => x => f(f(x));\n",
    "THREE = f => x => f(f(f(x)));\n",
    "FOUR = f => x => f(f(f(f(x))));\n",
    "FIVE = f => x => f(f(f(f(f(x)))));\n",
    "SIX = f => x => f(f(f(f(f(f(x))))));\n",
    "SEVEN = f => x => f(f(f(f(f(f(f(x)))))));\n",
    "EIGHT = f => x => f(f(f(f(f(f(f(f(x))))))));\n",
    "NINE = f => x => f(f(f(f(f(f(f(f(f(x)))))))));\n",
    "TEN = f => x => f(f(f(f(f(f(f(f(f(f(x))))))))));\n",
    "\n",
    "// Booleans\n",
    "TRUE = x => y => x;\n",
    "FALSE = x => y => y;\n",
    "\n",
    "// Branching\n",
    "IF_THEN_ELSE = p => x => y => p(x)(y);\n",
    "\n",
    "// Arithmetic\n",
    "SUCC = n => f => x => f(n(f)(x));\n",
    "PRED = n => n(p => z => z(SUCC(p(TRUE)))(p(TRUE)))(z => z(ZERO)(ZERO))(FALSE);\n",
    "PLUS = n => m => m(SUCC)(n);\n",
    "MINUS = n => m => m(PRED)(n);\n",
    "MULT = n => m => m(PLUS(n))(ZERO);\n",
    "\n",
    "// Comparison\n",
    "IS_ZERO = n => n(m => FALSE)(TRUE);\n",
    "LESS_THAN_OR_EQUAL = n => m => IS_ZERO(MINUS(n)(m));\n",
    "\n",
    "// Recursion\n",
    "FIX = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)));\n",
    "\n",
    "// Modulus\n",
    "MOD = FIX(r => n => m =>\n",
    "  IF_THEN_ELSE(LESS_THAN_OR_EQUAL(m)(n))(x => r(MINUS(n)(m))(m)(x))(n)\n",
    ");\n",
    "\n",
    "// More numbers\n",
    "FIFTEEN = PLUS(TEN)(FIVE);\n",
    "TWENTY = PLUS(TEN)(TEN);\n",
    "HUNDRED = MULT(TEN)(TEN);\n",
    "\n",
    "// Letters encoded as numbers (JS char codes)\n",
    "F = MULT(TEN)(SEVEN);\n",
    "I = PLUS(HUNDRED)(FIVE);\n",
    "Z = PLUS(HUNDRED)(PLUS(TWENTY)(TWO));\n",
    "B = PLUS(MULT(TEN)(SIX))(SIX);\n",
    "U = PLUS(HUNDRED)(PLUS(TEN)(SEVEN));\n",
    "\n",
    "// Tuples\n",
    "PAIR = x => y => p => p(x)(y);\n",
    "FIRST = p => p(x => y => x);\n",
    "SECOND = p => p(x => y => y);\n",
    "\n",
    "// Linked lists\n",
    "LIST_ELEMENT = x => xs => PAIR(FALSE)(PAIR(x)(xs));\n",
    "EMPTY_LIST = PAIR(TRUE)(TRUE);\n",
    "IS_EMPTY = FIRST;\n",
    "HEAD = xs => FIRST(SECOND(xs));\n",
    "TAIL = xs => SECOND(SECOND(xs));\n",
    "\n",
    "// List comprehension\n",
    "RANGE = FIX(r => m => n =>\n",
    "  IF_THEN_ELSE(LESS_THAN_OR_EQUAL(m)(n))(x =>\n",
    "    LIST_ELEMENT(m)(r(SUCC(m))(n))(x)\n",
    "  )(EMPTY_LIST)\n",
    ");\n",
    "\n",
    "// Lists of letters\n",
    "FIZZ = LIST_ELEMENT(F)(\n",
    "  LIST_ELEMENT(I)(LIST_ELEMENT(Z)(LIST_ELEMENT(Z)(EMPTY_LIST)))\n",
    ");\n",
    "\n",
    "BUZZ = LIST_ELEMENT(B)(\n",
    "  LIST_ELEMENT(U)(LIST_ELEMENT(Z)(LIST_ELEMENT(Z)(EMPTY_LIST)))\n",
    ");\n",
    "\n",
    "FIZZBUZZ = LIST_ELEMENT(F)(\n",
    "  LIST_ELEMENT(I)(LIST_ELEMENT(Z)(LIST_ELEMENT(Z)(BUZZ)))\n",
    ");\n",
    "\n",
    "// Reduce\n",
    "FOLD = FIX(r => f => z => xs =>\n",
    "  IF_THEN_ELSE(IS_EMPTY(xs))(z)(x => f(HEAD(xs))(r(f)(z)(TAIL(xs)))(x))\n",
    ");\n",
    "\n",
    "// Functor map\n",
    "MAP = f => FOLD(x => xs => LIST_ELEMENT(f(x))(xs))(EMPTY_LIST);\n",
    "\n",
    "// FizzBuzz\n",
    "FIZZBUZZFUNC = MAP(n =>\n",
    "  IF_THEN_ELSE(IS_ZERO(MOD(n)(FIFTEEN)))(FIZZBUZZ)(\n",
    "    IF_THEN_ELSE(IS_ZERO(MOD(n)(THREE)))(FIZZ)(\n",
    "      IF_THEN_ELSE(IS_ZERO(MOD(n)(FIVE)))(BUZZ)(n)\n",
    "    )\n",
    "  )\n",
    ");\n",
    "\n",
    "// Utilities\n",
    "toBool = b => IF_THEN_ELSE(b)(true)(false);\n",
    "\n",
    "toInt = n => n(x => x + 1)(0);\n",
    "\n",
    "toArray = xs =>\n",
    "  [].concat(toBool(IS_EMPTY(xs)) ? [] : [HEAD(xs)].concat(toArray(TAIL(xs))));\n",
    "\n",
    "toArrayInt = xs =>\n",
    "  [].concat(\n",
    "    toBool(IS_EMPTY(xs)) ? [] : [toInt(HEAD(xs))].concat(toArrayInt(TAIL(xs)))\n",
    "  );\n",
    "\n",
    "toString = str =>\n",
    "  toArrayInt(str)\n",
    "    .map(n => String.fromCharCode(n))\n",
    "    .join(\"\");\n",
    "\n",
    "toFizzBuzz = fb =>\n",
    "  toArray(fb).map(x => (toString(x) === \"\" ? toInt(x) : toString(x)));\n",
    "\n",
    "// Test\n",
    "testFizzBuzz = () =>\n",
    "  toFizzBuzz(FIZZBUZZFUNC(RANGE(ONE)(FIFTEEN))).every(\n",
    "    (e, i) =>\n",
    "      e ===\n",
    "      [\n",
    "        1,\n",
    "        2,\n",
    "        \"Fizz\",\n",
    "        4,\n",
    "        \"Buzz\",\n",
    "        \"Fizz\",\n",
    "        7,\n",
    "        8,\n",
    "        \"Fizz\",\n",
    "        \"Buzz\",\n",
    "        11,\n",
    "        \"Fizz\",\n",
    "        13,\n",
    "        14,\n",
    "        \"FizzBuzz\"\n",
    "      ][i]\n",
    "  );\n",
    "\n",
    "// FIZZBUZZFUNC expanded into lambdas\n",
    "FIZZBUZZFUNC_EXP = (f =>\n",
    "  (f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))(r => f => z => xs =>\n",
    "    (p => x => y => p(x)(y))((p => p(x => y => x))(xs))(z)(x =>\n",
    "      f((xs => (p => p(x => y => x))((p => p(x => y => y))(xs)))(xs))(\n",
    "        r(f)(z)((xs => (p => p(x => y => y))((p => p(x => y => y))(xs)))(xs))\n",
    "      )(x)\n",
    "    )\n",
    "  )(x => xs =>\n",
    "    (x => xs =>\n",
    "      (x => y => p => p(x)(y))(x => y => y)((x => y => p => p(x)(y))(x)(xs)))(\n",
    "      f(x)\n",
    "    )(xs)\n",
    "  )((x => y => p => p(x)(y))(x => y => x)(x => y => x)))(n =>\n",
    "  (p => x => y => p(x)(y))(\n",
    "    (n => n(m => x => y => y)(x => y => x))(\n",
    "      (f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))(r => n => m =>\n",
    "        (p => x => y => p(x)(y))(\n",
    "          (n => m =>\n",
    "            (n => n(m => x => y => y)(x => y => x))(\n",
    "              (n => m =>\n",
    "                m(n =>\n",
    "                  n(p => z =>\n",
    "                    z((n => f => x => f(n(f)(x)))(p(x => y => x)))(\n",
    "                      p(x => y => x)\n",
    "                    )\n",
    "                  )(z => z(f => x => x)(f => x => x))(x => y => y)\n",
    "                )(n))(n)(m)\n",
    "            ))(m)(n)\n",
    "        )(x =>\n",
    "          r(\n",
    "            (n => m =>\n",
    "              m(n =>\n",
    "                n(p => z =>\n",
    "                  z((n => f => x => f(n(f)(x)))(p(x => y => x)))(p(x => y => x))\n",
    "                )(z => z(f => x => x)(f => x => x))(x => y => y)\n",
    "              )(n))(n)(m)\n",
    "          )(m)(x)\n",
    "        )(n)\n",
    "      )(n)(\n",
    "        (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "          f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "        )(f => x => f(f(f(f(f(x))))))\n",
    "      )\n",
    "    )\n",
    "  )(\n",
    "    (x => xs =>\n",
    "      (x => y => p => p(x)(y))(x => y => y)((x => y => p => p(x)(y))(x)(xs)))(\n",
    "      (n => m =>\n",
    "        m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(\n",
    "        f => x => f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "      )(f => x => f(f(f(f(f(f(f(x))))))))\n",
    "    )(\n",
    "      (x => xs =>\n",
    "        (x => y => p => p(x)(y))(x => y => y)((x => y => p => p(x)(y))(x)(xs)))(\n",
    "        (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "          (n => m =>\n",
    "            m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(\n",
    "            f => x => f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "          )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "        )(f => x => f(f(f(f(f(x))))))\n",
    "      )(\n",
    "        (x => xs =>\n",
    "          (x => y => p => p(x)(y))(x => y => y)(\n",
    "            (x => y => p => p(x)(y))(x)(xs)\n",
    "          ))(\n",
    "          (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "            (n => m =>\n",
    "              m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(\n",
    "              f => x => f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "            )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "          )(\n",
    "            (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "              (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "                f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "              )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "            )(f => x => f(f(x)))\n",
    "          )\n",
    "        )(\n",
    "          (x => xs =>\n",
    "            (x => y => p => p(x)(y))(x => y => y)(\n",
    "              (x => y => p => p(x)(y))(x)(xs)\n",
    "            ))(\n",
    "            (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "              (n => m =>\n",
    "                m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(\n",
    "                f => x => f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "              )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "            )(\n",
    "              (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "                  f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "              )(f => x => f(f(x)))\n",
    "            )\n",
    "          )(\n",
    "            (x => xs =>\n",
    "              (x => y => p => p(x)(y))(x => y => y)(\n",
    "                (x => y => p => p(x)(y))(x)(xs)\n",
    "              ))(\n",
    "              (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                (n => m =>\n",
    "                  m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x =>\n",
    "                    x\n",
    "                  ))(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))(f => x =>\n",
    "                  f(f(f(f(f(f(x))))))\n",
    "                )\n",
    "              )(f => x => f(f(f(f(f(f(x)))))))\n",
    "            )(\n",
    "              (x => xs =>\n",
    "                (x => y => p => p(x)(y))(x => y => y)(\n",
    "                  (x => y => p => p(x)(y))(x)(xs)\n",
    "                ))(U)(\n",
    "                (x => xs =>\n",
    "                  (x => y => p => p(x)(y))(x => y => y)(\n",
    "                    (x => y => p => p(x)(y))(x)(xs)\n",
    "                  ))(\n",
    "                  (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                    (n => m =>\n",
    "                      m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(\n",
    "                        f => x => x\n",
    "                      ))(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))(f => x =>\n",
    "                      f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                    )\n",
    "                  )(\n",
    "                    (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                      (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "                        f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                      )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "                    )(f => x => f(f(x)))\n",
    "                  )\n",
    "                )(\n",
    "                  (x => xs =>\n",
    "                    (x => y => p => p(x)(y))(x => y => y)(\n",
    "                      (x => y => p => p(x)(y))(x)(xs)\n",
    "                    ))(\n",
    "                    (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                      (n => m =>\n",
    "                        m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(\n",
    "                          f => x => x\n",
    "                        ))(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))(f => x =>\n",
    "                        f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                      )\n",
    "                    )(\n",
    "                      (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                        (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "                          f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                        )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "                      )(f => x => f(f(x)))\n",
    "                    )\n",
    "                  )((x => y => p => p(x)(y))(x => y => x)(x => y => x))\n",
    "                )\n",
    "              )\n",
    "            )\n",
    "          )\n",
    "        )\n",
    "      )\n",
    "    )\n",
    "  )(\n",
    "    (p => x => y => p(x)(y))(\n",
    "      (n => n(m => x => y => y)(x => y => x))(\n",
    "        (f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))(r => n => m =>\n",
    "          (p => x => y => p(x)(y))(\n",
    "            (n => m =>\n",
    "              (n => n(m => x => y => y)(x => y => x))(\n",
    "                (n => m =>\n",
    "                  m(n =>\n",
    "                    n(p => z =>\n",
    "                      z((n => f => x => f(n(f)(x)))(p(x => y => x)))(\n",
    "                        p(x => y => x)\n",
    "                      )\n",
    "                    )(z => z(f => x => x)(f => x => x))(x => y => y)\n",
    "                  )(n))(n)(m)\n",
    "              ))(m)(n)\n",
    "          )(x =>\n",
    "            r(\n",
    "              (n => m =>\n",
    "                m(n =>\n",
    "                  n(p => z =>\n",
    "                    z((n => f => x => f(n(f)(x)))(p(x => y => x)))(\n",
    "                      p(x => y => x)\n",
    "                    )\n",
    "                  )(z => z(f => x => x)(f => x => x))(x => y => y)\n",
    "                )(n))(n)(m)\n",
    "            )(m)(x)\n",
    "          )(n)\n",
    "        )(n)(f => x => f(f(f(x))))\n",
    "      )\n",
    "    )(\n",
    "      (x => xs =>\n",
    "        (x => y => p => p(x)(y))(x => y => y)((x => y => p => p(x)(y))(x)(xs)))(\n",
    "        (n => m =>\n",
    "          m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(\n",
    "          f => x => f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "        )(f => x => f(f(f(f(f(f(f(x))))))))\n",
    "      )(\n",
    "        (x => xs =>\n",
    "          (x => y => p => p(x)(y))(x => y => y)(\n",
    "            (x => y => p => p(x)(y))(x)(xs)\n",
    "          ))(\n",
    "          (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "            (n => m =>\n",
    "              m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(\n",
    "              f => x => f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "            )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "          )(f => x => f(f(f(f(f(x))))))\n",
    "        )(\n",
    "          (x => xs =>\n",
    "            (x => y => p => p(x)(y))(x => y => y)(\n",
    "              (x => y => p => p(x)(y))(x)(xs)\n",
    "            ))(\n",
    "            (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "              (n => m =>\n",
    "                m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(\n",
    "                f => x => f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "              )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "            )(\n",
    "              (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "                  f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "              )(f => x => f(f(x)))\n",
    "            )\n",
    "          )(\n",
    "            (x => xs =>\n",
    "              (x => y => p => p(x)(y))(x => y => y)(\n",
    "                (x => y => p => p(x)(y))(x)(xs)\n",
    "              ))(\n",
    "              (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                (n => m =>\n",
    "                  m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x =>\n",
    "                    x\n",
    "                  ))(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))(f => x =>\n",
    "                  f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                )\n",
    "              )(\n",
    "                (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                  (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "                    f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                  )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "                )(f => x => f(f(x)))\n",
    "              )\n",
    "            )((x => y => p => p(x)(y))(x => y => x)(x => y => x))\n",
    "          )\n",
    "        )\n",
    "      )\n",
    "    )(\n",
    "      (p => x => y => p(x)(y))(\n",
    "        (n => n(m => x => y => y)(x => y => x))(\n",
    "          (f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y))))(r => n => m =>\n",
    "            (p => x => y => p(x)(y))(\n",
    "              (n => m =>\n",
    "                (n => n(m => x => y => y)(x => y => x))(\n",
    "                  (n => m =>\n",
    "                    m(n =>\n",
    "                      n(p => z =>\n",
    "                        z((n => f => x => f(n(f)(x)))(p(x => y => x)))(\n",
    "                          p(x => y => x)\n",
    "                        )\n",
    "                      )(z => z(f => x => x)(f => x => x))(x => y => y)\n",
    "                    )(n))(n)(m)\n",
    "                ))(m)(n)\n",
    "            )(x =>\n",
    "              r(\n",
    "                (n => m =>\n",
    "                  m(n =>\n",
    "                    n(p => z =>\n",
    "                      z((n => f => x => f(n(f)(x)))(p(x => y => x)))(\n",
    "                        p(x => y => x)\n",
    "                      )\n",
    "                    )(z => z(f => x => x)(f => x => x))(x => y => y)\n",
    "                  )(n))(n)(m)\n",
    "              )(m)(x)\n",
    "            )(n)\n",
    "          )(n)(f => x => f(f(f(f(f(x))))))\n",
    "        )\n",
    "      )(\n",
    "        (x => xs =>\n",
    "          (x => y => p => p(x)(y))(x => y => y)(\n",
    "            (x => y => p => p(x)(y))(x)(xs)\n",
    "          ))(\n",
    "          (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "            (n => m =>\n",
    "              m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(\n",
    "              f => x => f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "            )(f => x => f(f(f(f(f(f(x)))))))\n",
    "          )(f => x => f(f(f(f(f(f(x)))))))\n",
    "        )(\n",
    "          (x => xs =>\n",
    "            (x => y => p => p(x)(y))(x => y => y)(\n",
    "              (x => y => p => p(x)(y))(x)(xs)\n",
    "            ))(\n",
    "            (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "              (n => m =>\n",
    "                m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x => x))(\n",
    "                f => x => f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "              )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "            )(\n",
    "              (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "                f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "              )(f => x => f(f(f(f(f(f(f(x))))))))\n",
    "            )\n",
    "          )(\n",
    "            (x => xs =>\n",
    "              (x => y => p => p(x)(y))(x => y => y)(\n",
    "                (x => y => p => p(x)(y))(x)(xs)\n",
    "              ))(\n",
    "              (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                (n => m =>\n",
    "                  m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x =>\n",
    "                    x\n",
    "                  ))(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))(f => x =>\n",
    "                  f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                )\n",
    "              )(\n",
    "                (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                  (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "                    f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                  )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "                )(f => x => f(f(x)))\n",
    "              )\n",
    "            )(\n",
    "              (x => xs =>\n",
    "                (x => y => p => p(x)(y))(x => y => y)(\n",
    "                  (x => y => p => p(x)(y))(x)(xs)\n",
    "                ))(\n",
    "                (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                  (n => m =>\n",
    "                    m((n => m => m(n => f => x => f(n(f)(x)))(n))(n))(f => x =>\n",
    "                      x\n",
    "                    ))(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))(f => x =>\n",
    "                    f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                  )\n",
    "                )(\n",
    "                  (n => m => m(n => f => x => f(n(f)(x)))(n))(\n",
    "                    (n => m => m(n => f => x => f(n(f)(x)))(n))(f => x =>\n",
    "                      f(f(f(f(f(f(f(f(f(f(x))))))))))\n",
    "                    )(f => x => f(f(f(f(f(f(f(f(f(f(x)))))))))))\n",
    "                  )(f => x => f(f(x)))\n",
    "                )\n",
    "              )((x => y => p => p(x)(y))(x => y => x)(x => y => x))\n",
    "            )\n",
    "          )\n",
    "        )\n",
    "      )(n)\n",
    "    )\n",
    "  )\n",
    ");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1,\n",
       "  2,\n",
       "  'Fizz',\n",
       "  4,\n",
       "  'Buzz',\n",
       "  'Fizz',\n",
       "  7,\n",
       "  8,\n",
       "  'Fizz',\n",
       "  'Buzz',\n",
       "  11,\n",
       "  'Fizz',\n",
       "  13,\n",
       "  14,\n",
       "  'FizzBuzz' ]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "toFizzBuzz(FIZZBUZZFUNC(RANGE(ONE)(FIFTEEN)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "TRUE.inspect = () => 'True'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FALSE.inspect = () => 'False'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NOT(TRUE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR = x => y => x (NOT(y))(y)\n",
    "XOR(TRUE)(TRUE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: OR2]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "OR2 = x => y => x(x)(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "OR2(TRUE)(FALSE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: AND2]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AND2 = x => y => x(y)(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AND2(FALSE)(TRUE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Omega Functor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: OMEGA]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "OMEGA = f => f(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: OR3]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "OR3 = x => y => OMEGA(x)(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "OR3(FALSE)(FALSE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function: XNOR]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XNOR = x => y => x(y)(NOT(y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XNOR(FALSE)(FALSE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XNOR(TRUE)(FALSE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "TWO(NOT)(TRUE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ONE(ID)(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Javascript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "8.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}