December 26th, 2011

ДР Цертуса 2011

Милая задачка на сон грядущий.

Задачка про кодирование чисел и пар лямбда-выражениями определённым красивым способом.
Ноль кодируется как тождественная функция, т.е. [x|x], остальные числа получаются из нуля последовательным применением лямбда-выражения succ:
0 = [x|x], 1 = succ [x|x], 2 = succ (succ [x|x]), ...

Кортежи кодируются лямба-выражениями, принимающими число и возвращающими соответствующий элемент кортежа.
[a] 0 = a
[a, b] 0 = a, [a, b] 1 = b
[a, b, c] 0 = a, [a, b, c] 1 = b, [a, b, c] 2 = c
...

Для формирования кортежа можно применять лямбда-выражение tuple, принимающее сперва длину n кортежа, а затем n элементов кортежа:
[a] = tuple 1 a
[a, b] = tuple 2 a b
...

Лямбда-выражение length вычисляет длину кортежа:
length [a] = 1
length [a, b] = 2
...

Лямбда-выражение append соединяет кортежи. Придумайте красивую реализацию совместимых между собой выражений succ, tuple, length и append. У меня есть одно решение, но кажется можно красивее.