Rekurencja w rachunku lambda
Z Wikipedii
Rachunek lambda z pozoru nie ma żadnego mechanizmu, który umożliwiałby rekurencję - nie można odwoływać się w definicji do samej funkcji. A jednak - rekurencję można osiągnąć poprzez operator paradoksalny Y.
Paradoks polega na tym że dla każdego F zachodzi Y F = F (Y F). Tak więc np. funkcja negacji nie jest możliwa do zaimplementowania w postaci ogólnej gdyż: (Y nie) = nie (Y nie)
Funkcja rekurencyjna musi pobrać siebie samą jako wartość.
Działa to w następujący sposób:
- (Y f) n
- f (Y f) n
- λ f . λ n . ciało_f, gdzie ciało_f może się odwoływać do siebie samej
Np. :
- silnia = Y (λ f . λ n . if_then_else (is_zero n) 1 (mult n (f (pred n))))
