Один аппликативный функтор как вычислительный базис

[thedeemon]

Сперва пример. Вот такая программа на хаскеле вычисляет и выводит ответ на жизнь, вселенную и вообще:

import Control.Applicative
main = print $ answer succ 0 where
one = pure <*> (pure :: a -> b -> a)
inc = (<*>) ((<*>) <$> pure)
mul = (<*>) <$> pure
h = mul <*> inc
answer = h . h . h $ one

Аппликативный функтор характеризуется наличием двух функций с определенными свойствами:

class Functor f => Applicative f where
pure :: a -> f a -- Lift a value.
(<*>) :: f (a -> b) -> f a -> f b -- Sequential application.

Фишка в том, что для ((->) a) эти две функции - комбинаторы K и S!

instance Applicative ((->) a) where
pure = const -- \x . \y . x
(<*>) f g x = f x (g x)

А мы знаем, что через S и K можно выразить любую лямбда-функцию, а значит и любую вычислимую функцию. Возьмем, например, функцию
h(x) = x * (x + 1)
Она интересна тем, что использует только умножение и инкремент, и будучи трижды применена к единице, дает 42. Для арифметики на лямбдах задействуем числа Черча. Число n там представляется функцией, которая берет другую функцию и ее аргумент, и применяет ту функцию n раз. Так, единица применяет данную функцию f один раз:
one f x = f x
Чтобы увеличить n на 1, нужно применить f на один раз больше, чем это делает n:
inc n f x = f (n f x)
Умножение a на b делается применением b a раз:
mul a b f x = a (b f) x
(x тут можно "сократить" и не писать)
Тогда h будет выглядеть как
h x = mul x (inc x)

Теперь возьмем комбинаторный базис:
S x y z = (x z) (y z)
K x y = x
Пользуясь простым алгоритмом конверсии, наши арифметические функции можно выразить через S и K:
one = S K K
inc = S (S (K S) K)
mul = S (K S) K
h = S mul inc

Теперь осталось лишь вспомнить, что K = pure, S = <*>, а
pure x <*> y = x <$> y
Подставив их вместо S и K, получим программу выше.
Представляете, какие открываются горизонты? Я тоже нет. Разве что обфускатор можно написать. :)