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

[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
Аппликативный функтор характеризуется наличием

Comments

[kodt_rsdn]

Вместо обфускатора можно написать транслятор в унлямбду или с унлямбды. Там как раз SKI используется.

[thedeemon]

да, транслятор в унлямбду - очень нужная в хозяйстве вещь! :)

[sorhed]

Как нет применения? Можно было бы отлично писать зомбей на прошлом ICFPC. :)

[sassa_nf]

также,

inc = S mul

а посему, h = inc inc

как же так?!

[thedeemon]

>inc = S mul

С чего бы?

[sassa_nf]

Удивительно, но факт! ты подставь?

inc = S (S (K S) K)
mul = S (K S) K
Я тоже как-то не мог понять, и в виде mul a b f x = a (b f) x этого не видно.

Зато раз x можно "сократить", то выходит mul a b x = a (b x) (даже больше: mul = (.)), а inc n f x = f ((n f) x) = mul f (n f) x

Полиморфизм!

[thedeemon]

А вообще да, действительно.

Prelude> let h = inc inc
Prelude> (h . h . h $ one) (+1) 0
42

Хотя типы ghci выводит разные для inc и s mul.