Kata

Algebraic Data Types (not to be confused with Abstract Data Types, ADT) are composed types (normally recursively) and for those who have defined a serie of operations.

For example in Haskell, natural numbers can be defined in this way:

data Nat = Zero | Succ Nat

So:

0 = Zero
1 = Succ Zero
2 = Succ (Succ Zero)
3 = Succ (Succ (Succ Zero))
...

The objective of this kata is to define an algebra for the Nat data type.

In JavaScript we are going to use the next definition for natural numbers:

function zero(){}

function succ(nat) {
  return function() {
    return nat;
  };
}

zero and succ() are constructor functions of the Nat data type. A nat number could be the zero function (although you will never really call this function) or a function obtained by calling the function succ() with the previous natural number. This definition corresponds roughly to the definition of Church numbers

So:

zero nat number corresponds to zero function one nat number is obtained by calling succ(zero) two nat number is obtained by calling succ(succ(zero)) ... and so on

Or more precisely:

var one = succ(zero);
var two = succ(one) = succ(succ(zero));
...

The algebra are composed by the next operations:

natToInt(nat) -> int // obtains the integer value of the nat number. For example natToInt(succ(succ(zero)) returns 2
intToNat(int) -> nat // converts an integer to a natural value. For example intToNat(2) does the same that succ(succ(zero))
toString(nat) -> string // returns a string representation of the natural value (see examples below)
add(nat1, nat2) -> nat // given two natual numbers, returns the natural sum of them
mul(nat1, nat2) -> nat // multiplies two naturals
compareTo(nat1, nat2) -> int // returns a number less than zero when nat1 < nat2; greater than zero when nat1 > nat2; and 0 when nat1 === nat2

Some examples:

natToInt(zero); // 0
natToInt(succ(zero)); // 1
natToInt(succ(succ(zero))); // 2 

intToNat(0) === zero; // true
intToNat(1); // is the same than succ(zero)
intToNat(2); // is the same than succ(succ(zero))
natToInt(intToNat(10)); // 10

toString(zero); // "zero"
toString(succ(zero)); // "succ(zero)"
toString(succ(succ(zero))); // "succ(succ(zero))"

add(zero, zero) === zero; // true
add(succ(zero), zero); // is the same that succ(zero)
add(succ(zero), succ(zero)); // is the same that succ(succ(zero))
add(succ(zero), succ(succ(zero))); // is the same that succ(succ(succ(zero)))
natToInt(add(zero, succ(zero))); // 1
natToInt(add(intToNat(10), intToNat(15))); // 25

mul(zero, zero) === zero; // true
mul(suc(zero), zero) === zero; // true
natToInt(mul(intToNat(10), intToNat(15))); // 150

compareTo(zero, zero); // 0
compareTo(zero, succ(zero)) < 0; // true
compareTo(succ(zero), zero) > 0; // true
compareTo(succ(zero), succ(zero)); // 0
compareTo(intToNat(10), intToNat(15)) < 0; // true

Additional notes:

1.- Function implementations must be pure (no mutable state and no side effects). So iterative implementations are not allowed. Do not use while or for keywords in your solution.

2.- A simple but inefficient implementation of add() operation could be:

function add(nat1, nat2) {
  return intToNat(natToInt(nat1) + natToInt(nat2));
}

The tests prove that the implementation of the add() function is efficient.

3.- In the same way, mul() can be implemented like this:

function mul(nat1, nat2) {
  return intToNat(natToInt(nat1) * natToInt(nat2)); // bad: * operator is forbidden
}

Do not use arithmetic operators (+, - , *, /, %, ...) in implementing the functions add() and mul().