eliseuvideira

Functional Programming Boolean

June 24th, 2020 — javascript, functional programming8 min read

The other day I was solving some katas at codewars when I confronted a really good one.

This is the kata if you are interested. https://www.codewars.com/kata/5ac739ed3fdf73d3f0000048

The whole premise of this kata is to arrive at boolean operators (Not, And, Or and Xor) using only functions as the primitives.

The kata gives you the structure of the functions, you just need to fill the return statements.

js
const True = x => y => x;
const False = x => y => y;
const Not = x => null;
const And = x => y => null;
const Or = x => y => null;
const Xor = x => y => null;

The thing that makes this exercise interesting is that you are not allowed to make use of any built-in language operators, you need to deduce them from scratch, in this case from the functions True and False.

By the function definitions we see that both True and False are using currying and recieve two parameters.

True just returns the first parameters and ignores the second, False does the contrary, it ignores the first one and returns the second as recieved. The parameters are supposed to be either True or False.

We need to make use of this knowledge to obtain the boolean operators.

Not

To obtain Not we need to be able to transform True into False and False into True by using the function definition.

js
const Not = x => null;

In this snippet, x is either True or False, we need to reverse it's value, in a way that works both ways.

Let's suppose x is True, to reverse it's value we just need to return False.

js
const Not1 = x => False;

Now if x is False, we just need to return True.

js
const Not2 = x => True;

To combine both conditions into one, we need to move our current definitions to depend on the values of x, which can be True and False

js
// x -> True
const Not1 = x => x(False)(null);
console.log(Not1(True) === False); // true
// x -> False
const Not2 = x => x(null)(True);
console.log(Not2(False) === True); // true

Now we can safely combine both definitions into one:

js
// const Not1 = x => x(False)(null);
// const Not2 = x => x(null)(True);
const Not = x => x(False)(True);
console.log(Not(True) === False); // true
console.log(Not(False) === True); // true

By looking at the output we can see that we correctly transformed True into False.

And

Now let's take a look at the And operator, the idea behind this operator, as you are already aware of, is to return True only in the case that both parameters are True.

The definition provided so far is this, we need to fix the return value.

js
const And = x => y => null;

Suppose for a moment that x is always True.

If x is always True, to make the And function work as intended, we need to return True when y is True, and False otherwise. The simplest way to express this is the following:

js
const And1 = x => y => y;
console.log(And1(True)(True) === True); // true
console.log(And1(True)(False) === False); // true

Now let's imagine that x is always False.

js
const And2 = x => y => False;
console.log(And2(False)(True) === False); // true
console.log(And2(False)(False) === False); // true

To combine both definitions we need to make And2 depend on the value of y.

js
const And2 = x => y => False(y)(False);

Since the value of x in this case is always False, we can replace for this definition:

js
const And2 = x => y => x(y)(False);

Let's now revisit the And1 definition, and make it depend on True, we are making this step to later replace True with x.

js
const And1 = x => y => True(y)(null);

Now replace True with x.

js
const And1 = x => y => x(y)(null);

Combining both definition at this point is easier, keep in mind that we can put anything to replace null value.

So we arrive at:

js
// const And1 = x => y => x(y)(null);
// const And2 = x => y => x(y)(False);
const And = x => y => x(y)(False);
console.log(And(True)(True) === True); // true
console.log(And(True)(False) === False); // true
console.log(And(False)(True) === False); // true
console.log(And(False)(False) === False); // true

Observing the logs we can verify that we arrived at the correct definition of And.

Or

Next in the line is the Or operator. We need to return True if any of the parameters are True, and return False only if both are False.

js
const Or = x => y => null;

If we make the same assumption we did previously, that x is always True, we just need to return True, whatever the value of y.

js
const Or1 = x => y => True;
console.log(Or1(True)(True) === True); // true
console.log(Or1(True)(False) === True); // true

Now for the reverse situation, in which x is always False, we need to check if y is True to return True, and False otherwise.

js
const Or2 = x => y => y;
console.log(Or2(False)(True) === True); // true
console.log(Or2(False)(False) === False); // true

To combine both definitions, we need to make the second (Or2) depend on False, to replace later with the value of x.

js
const Or2 = x => y => False(null)(y);
console.log(Or2(False)(True) === True); // true
console.log(Or2(False)(False) === False); // true

Since we know that x is always False for this case, we can replace for this definition:

js
const Or2 = x => y => x(null)(y);

Let's do the same with Or1, but using True instead of False:

js
// const Or1 = x => y => True;
const Or1 = x => y => True(True)(y);

Then replace True with x.

js
const Or1 = x => y => x(True)(y);

Combining both definitions we reach the following.

js
// const Or1 = x => y => x(True)(y);
// const Or2 = x => y => x(null)(y);
const Or = x => y => x(x)(y);
console.log(Or(True)(True) === True); // true
console.log(Or(True)(False) === True); // true
console.log(Or(False)(True) === True); // true
console.log(Or(False)(False) === False); // true

Looking to the console we can verify that the definition we reached is a correct one.

Xor

Xor is the exclusive Or, it should return True only if the values of x and y are different.

js
const Xor = x => y => null;

Let's continue with our method of setting x as True, in this case, if y is True we should return False, and in the case that its False, we should return True.

If that sounded familiar, its because is the same as the Not operator we did earlier. So we can reuse Not here.

js
const Xor1 = x => y => Not(y);
console.log(Xor1(True)(True) === False); // true
console.log(Xor1(True)(False) === True); // true

Now for x being False.

When y is True, return True, when False, False. We can just replace this with the value of y then.

js
const Xor2 = x => y => y;
console.log(Xor2(False)(True) === True); // true
console.log(Xor2(False)(False) === False); // true

To conciliate our answers we could change the first one to depend on True

js
const Xor1 = x => y => True(Not(y))(null);

Now replace True with x.

js
const Xor1 = x => y => x(Not(y))(null);

Let's make Xor1 depend on False.

js
const Xor2 = x => y => False(null)(y);

Then replace False with x.

js
const Xor2 = x => y => x(null)(y);

Now we can combine both definitions.

js
// const Xor1 = x => y => x(Not(y))(null);
// const Xor2 = x => y => x(null)(y);
const Xor = x => y => x(Not(y))(y);
console.log(Xor(True)(True) === False); // true
console.log(Xor(True)(False) === True); // true
console.log(Xor(False)(True) === True); // true
console.log(Xor(False)(False) === False); // true

Looking to the console values, we verify that the Xor operator works expected.

Conclusion

That's it, now we have fully functional boolean operators using only functions as primitives, its interesting that I never really tought that deep on how the boolean operators work behind the scenes, I always took them for granted.

The full code is as follows:

Boolean.js

js
export const True = x => y => x;
export const False = x => y => y;
export const Not = x => x(False)(True);
export const And = x => y => x(y)(False);
export const Or = x => y => x(x)(y);
export const Xor = x => y => x(Not(y))(y);

And the test cases:

Boolean.test.js

js
import { True, False, Not, And, Or, Xor } from './Boolean';
describe('Not', () => {
  it('works', () => {
    expect.assertions(2);
    expect(Not(True)).toBe(False);
    expect(Not(False)).toBe(True);
  });
});
describe('And', () => {
  it('works', () => {
    expect.assertions(4);
    expect(And(True)(True)).toBe(True);
    expect(And(True)(False)).toBe(False);
    expect(And(False)(True)).toBe(False);
    expect(And(False)(False)).toBe(False);
  });
});
describe('Or', () => {
  it('works', () => {
    expect.assertions(4);
    expect(Or(True)(True)).toBe(True);
    expect(Or(True)(False)).toBe(True);
    expect(Or(False)(True)).toBe(True);
    expect(Or(False)(False)).toBe(False);
  });
});
describe('Xor', () => {
  it('works', () => {
    expect.assertions(4);
    expect(Xor(True)(True)).toBe(False);
    expect(Xor(True)(False)).toBe(True);
    expect(Xor(False)(True)).toBe(True);
    expect(Xor(False)(False)).toBe(False);
  });
});