Cosa fa questo combinatore: S (s k)

Question

Ora capisco la firma del tipo di s (s k):

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

.

E posso creare esempi che funzionano senza errori nello strumento Haskell WingHCI:

Esempio :

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

.

restituisce 2.

Esempio :

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

.

restituisce 4.

dove successor è definito come:

successor = (\x -> x + 1)

.

Nondimeno, non ho ancora una sensazione intuitiva per quello che genera s (s k).

Il combinatore s (s k) accetta due funzioni f e g.Cosa fa s (s k) con f e g?Mi daresti la grande immagine su quale s (s k) fa per favore?

Answer 1

Va bene, guardiamo a cosa significa S (S K).Ho intenzione di usare queste definizioni:

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)

.

Come puoi vedere, è solo ($) con tipo più specifico.