Что делает этот комбинатор: s (s k) - PullRequest
Новая
       78

Что делает этот комбинатор: s (s k)

6 голосов
/ 12 марта 2012

Теперь я понимаю сигнатуру типа s (s k): 

s (s k)  :: ((t1 -> t2) -> t1) -> (t1 -> t2) -> t1

И я могу создавать примеры, которые работают без ошибок, в инструменте Haskell WinGHCi:

Пример : 

s (s k) (\g -> 2) (\x -> 3)

возвращает 2.

Пример : 

s (s k) (\g -> g 3) successor

возвращает 4.

где successor определяется следующим образом: 

successor = (\x -> x + 1)

Тем не менее, у меня все еще нет интуитивного ощущения того, что делает s (s k).

Комбинаторs (s k) принимает любые две функции f и g.Что s (s k) делает с f и g?Не могли бы вы дать общую картину о том, что s (s k) делает, пожалуйста?

1 Ответ

11 голосов
/ 12 марта 2012

Хорошо, давайте посмотрим, что означает S (S K). Я собираюсь использовать эти определения: 

S = \x y z -> x z (y z)
K = \x y   -> x

S (S K) = (\x y z -> x z (y z)) ((\x y z -> x z (y z)) (\a b -> a)) -- rename bound variables in K
        = (\x y z -> x z (y z)) (\y z -> (\a b -> a) z (y z)) -- apply S to K
        = (\x y z -> x z (y z)) (\y z -> (\b -> z) (y z)) -- apply K to z
        = (\x y z -> x z (y z)) (\y z -> z) -- apply (\_ -> z) to (y z)
        = (\x y z -> x z (y z)) (\a b -> b) -- rename bound variables
        = (\y z -> (\a b -> b) z (y z)) -- apply S to (\a b -> b)
        = (\y z -> (\b -> b) (y z)) -- apply (\a b -> b) to z
        = (\y z -> y z) -- apply id to (y z)

Как видите, это просто ($) с более конкретным типом.

...