Jak napisać rekurencyjne wyrażenie lambda w Haskell?

Question

Jak napisać rekurencyjne wyrażenie lambda w Haskell?

Nie jestem pewien, czy jest to dobra praktyka programowania, ale chciałbym wiedzieć, czy można zdefiniować funkcję rekurencyjną używając wyrażenia lambda.

Jest to sztuczny przykład, który wymyśliłem: więc można zdefiniować funkcję czynnikową w Haskell rekurencyjnie w następujący sposób

factorial :: Integer -> Integer 
factorial 1 = 1
factorial (n + 1) = (n + 1) * factorial n

Chcę mieć funkcję f taką, że f n = (factorial n) + 1. Zamiast używać nazwy dla factorial n (tj. definiując ją przed ręką), chcę zdefiniować f Gdzie factorial n jest podane wyrażenie lambda w ramach definicji f. Czy mogę użyć rekurencyjnej definicji lambda w f zamiast nazwy factorial?

30

haskell recursion lambda

Author: hammar, 2011-08-21

Source

4 answers

Tak, używając funkcji punktu stałego fix:

fact :: Int -> Int
fact = fix (\f n -> if n == 0 then 1 else n * (f (n-1)))

Zasadniczo, nie ma nazwy, ponieważ jest wyrażeniem lambda, więc bierzesz funkcję jako argument. Fix stosuje funkcję do siebie "nieskończenie" wiele razy:

fix f = f (fix f)

I jest zdefiniowana w Data.Function.

29

Author: Owen,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-06-02 16:30:59

Dlaczego używamy lambda zamiast let in?

Prelude> (let fib n = if n == 1 then 1 else n * fib(n-1) in fib ) 4
24

1

Author: Anon Imous,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-06-21 23:12:53

Owen jest na miejscu z funkcją fix

Prelude> fix f = f (fix f)
Prelude> fix (\f n -> if n == 0 then 1 else n * f (n - 1)) 6
720

Bezimienna funkcja Lambda samoczynnie się kończy, nawet jeśli fix nie jest. Funkcja fix Owena bije funkcję fix zazwyczaj używaną w Haskell, która jest

fix :: (a -> a) -> a
fix f = let {x = f x} in x

Oba umożliwiają anonimowe rekurencyjne funkcje lambda

0

Author: fp_mora,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-02-15 02:31:40

score 31 · Accepted Answer

Kanonicznym sposobem wykonywania rekursji z czystymi wyrażeniami lambda jest użycie kombinatora fixpoint , który jest funkcją o właściwości

fixpoint f x = f (fixpoint f) x

Jeśli założymy, że taki kombinator istnieje, możemy zapisać funkcję rekurencyjną jako

factorial = fixpoint (\ff n -> if n == 1 then 1 else n * ff(n-1))

Jedynym problemem jest to, że fixpoint Sam jest wciąż rekurencyjny. W czystym rachunku lambda istnieją sposoby tworzenia kombinatorów fixpoint, które składają się tylko z lambda, na przykład klasycznego " Y kombinator": {]}

fixpoint f = (\x -> f (x x)) (\x -> f (x x))

Ale nadal mamy problemy, ponieważ definicja ta nie jest dobrze wpisana według Haskella -- i można udowodnić, że nie ma sposobu , aby napisać dobrze wpisany kombinator fixpoint używając tylko lambda i aplikacji funkcyjnych. Można to zrobić za pomocą pomocniczego typu danych do wywołania rekurencji typu:

data Paradox a = Self (Paradox a -> a)
fixpoint f = let half (Self twin) = f (twin (Self twin))
             in half (Self half)

(zauważ, że jeśli zastrzyki i projekcje z typu danych singleton zostaną usunięte, jest to dokładnie kombinator Y!)