λ-račun

Naloga: Izračunajte vrednost

Do konca izračunajte naslednje izraze v λ-računu:

1. (λ f x . f (f x)) (λ z . z z)
2. (λ f g x . f (g x)) (λ z . t (t z)) t
3. ((λ x . x) (λ f g x . g)) u v w

Naloga: urejene trojice

V λ-računu definirajte funkcije za delo z urejenimi trojicami:

• triple zgradi novo trojico;
• funkcije fst, snd in trd pa vrnejo prvi, drugi oziroma tretji element dane trojice.

Primer:

# :constant U
# :constant V
# :constant W
# snd (triple U V W)
U

Rešitev

triple := ^ a b c . ^ p. p a b c
fst := ^ p . p (^x y z . x)
snd := ^ p . p (^x y z . y)
trd := ^ p . p (^x y z . z)

Naloga: dvakratnik Scott-Church števila

V Scott-Churchevi notaciji smo naravno število n predstavili z n-kratno aplikacijo funkcije na argumentu:

0 := \x f . x
1 := \x f . f 0 x
2 := \x f . f 1 (f 0 x)
3 := \x f . f 2 (f 1 (f 0 x))

V λ-računu definirajte funkcijo double, ki vrne dvakratnik danega Scott-Churchevega števila.

Rešitev

double := \n . n (\m r f x . f r (r f x)) n;