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

[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, получим программу выше.
Представляете, какие открываются горизонты? Я тоже нет. Разве что обфускатор можно написать. :)

Comments

[akuklev.livejournal.com]

Это нифига не случайное совпадение, а собствено базовая мотивация интерфейса аппликативных функторов.

[thedeemon.livejournal.com]

Оно ж не для каждого ап.функтора справедливо. Одно дело засунуть в функтор и применить какую-то свою функцию, другое - как здесь - реализовать функцию на самом интерфейсе ап.функтора.

[akuklev.livejournal.com]

> Оно ж не для каждого ап.функтора справедливо.
Аппликативный функтор это функтор, "переносящий" лямбда-исчисление из одной категории в другую, так его определили. Метод "переноса" заключается в том, что мы можем переписать лямбда-выражения через S и K комбинаторы и заменить их на <*> и pure. В исходной работе по аппликатианым функторам (“Applicative programming with effects”, Conor McBride, Ross Paterson)
для <*> и pure используются обозначения \mathbb{S} и \mathbb{K}, и написано прямым текстом: «This class generalises S and K from threading an environment to threading an effect in general».

У аппликативных функторов возможен и _другой_ интерфейс, связь которого с комбинаторной логикой менее очевидна; в той же работе объясняется, что аппликативный функтор это strong lax monoidal functor, т.е. вместо S и K его можно снабжать тензорным произведением и тензорной силой, эффект будет тот же. Можно кстати сделать интерфейс через одноточечный базис комбинаторной логики навроде X; но неудобно.

[thedeemon.livejournal.com]

спасибо, помедитирую над этим

[aruslan.livejournal.com]

спасибо за референс