I stumbled across some lovely posts by Kyle Kingsbury, making fun of technical interviews by taking deliberately obtuse approaches to them. One of the simplest, Reversing the technical interview, uses Church encoding of lists to solve a very simple problem.
That post uses Clojure to implement things, which is likely to be unfamiliar. Here, I've translated the code into Javascript and Python, to make the ideas clearer.
The problem is to implement a linked list and reverse it.
First, we define a cons cell as the basis of our linked list.
function cons(h, t) {
return (p) => p ? h : t ;
};
def cons(h, t):
return lambda p: h if p else t
This is the Church encoding. Rather than representing the cons cell as data, we represent it as a function: a closure that contains the two parts of the cons cell and which can return either on request.
We get those parts by calling the closure with a Boolean, True for the head of the list, False for the tail.
> var x = cons(1, cons(2, null));
undefined
> x(true)
1
> x(false)(true)
2
> x
[Function]
>>> x = cons(1, cons(2, None))
>>> x(True)
1
>>> x(False)(True)
2
>>> x
<function cons.<locals>.<lambda> at 0x7f166fbd40e0>
Pulling out the nth element of the list is a recursive call based on n. If n = 0, return the head of the list; otherwise, return the (n - 1)th element of the tail of the list. (If n is greater than the length of the list, do nothing.) And small mercies: we're not using the Peano representation of numbers.
function nth(l, n) {
if (l) {
if (n == 0) {
return l(true);
} else {
return nth(l(false), n - 1);
};
};
};
def nth(l, n):
if l:
if n == 0:
return l(True)
else:
return nth(l(False), n - 1)
The pretty-printer can be done iteratively, otherwise I'd need helper functions to get the brackets right. There's some fiddling around to suppress line breaks in the output.
function prn_list(l) {
process.stdout.write("(");
while (l) {
process.stdout.write(l(true).toString());
if (l(false)) {
process.stdout.write(" ");
};
l = l(false);
};
process.stdout.write(")\n");
};
def prn_list(l):
print('(', end='')
while l:
print(l(True), end='')
if l(False):
print(' ', end='')
l = l(False)
print(')')
And finally, reversing a list. It's a standard approach, if you think of the lists as being like stacks. Pop the head off the given list, push it onto the accumulator. As stacks are LIFO, this reverses the order for us. Note that I've swapped the order of the arguments in the recursive call, putting the accumulator r after the remaining list l. This allows me to use arguments with default values, rather than local variables in the loop.
function reverse_list(l, r = null) {
if (l) {
return reverse_list(l(false), cons(l(true), r));
} else {
return r;
};
};
def reverse_list(l, r=None):
if l:
return reverse_list(l(False), cons(l(True), r))
else:
return r
Finally, putting it all together:
> prn_list(reverse_list(cons(1, cons(2, cons(3, null)))));
(3 2 1)
>>> prn_list(reverse_list(cons(1, cons(2, cons(3, None)))))
(3 2 1)
Of course, all this confusion could have been avoided if we'd finished off the abstraction. We built a function, cons, that made lists, instead of always writing out the lambda expression for them. We could easily implement functions head and tail for decomposing lists.
function head(l) { return l(true); };
function tail(l) { return l(false); };
def head(l): return l(True)
def tail(l): return l(False)
or, more tersely in Javascript
var head = (l) => l(true)
var tail = (l) => l(false)
Using these makes reverse look very familiar.
function rev_ht(l, r = null) {
if (l) {
return rev_ht(tail(l), cons(head(l), r));
} else {
return r;
};
};
def rev_ht(l, r=None):
if l:
return rev_ht(tail(l), cons(head(l), r))
else:
return r