Как использовать Y-Combinator; почему эта бесконечная рекурсия возвращает 9?

Question

Y - комбинатор

Я пытался узнать о Y - комбинаторы (объяснение на том, что было бы прекрасно, а) и наткнулся на пример из этой wiki. Подробное объяснение по этому вопросу было бы высоко оценено либо в Haskell, либо в Python. Pleaaase!

Код

fix :: (a -> a) -> a 
fix f = f (fix f) 

Проблема

Функция называется fix возвращает 9 когда fix применяется к (\x -> 9), и я понятия не имею, почему; когда я следую за стеком, я представляю f(f ... (fix f) ...).

>> fix (\x -> 9) 
>> 9 

Answer 1

Прежде всего: функция fix у вас есть фиксированная точка комбинатор реализован с прямой рекурсией. Комбинатор Y - это конкретный комбинатор с фиксированной запятой, который не нуждается в синтаксической рекурсии, поэтому он выполняет то же самое, что и fix, но по-другому.

Если вам интересно, вы можете посмотреть здесь how to implement the Y combinator in Haskell. Это немного сложно со статическими типами - для работы требуется рекурсивный тип.

Что касается вашего второго вопроса, код работает благодаря лени. Если вы примените (\ x -> 9) к что-нибудь, эта вещь никогда не будет оценена. Попробуйте это:

λ> (\ x -> 9) (error "fail") 
9 

Это включает рекурсивный вызов в определении fix. Посмотрите, что происходит, когда вы замените внешний-наиболее f с (\ x -> 9) в определении fix:

(\ x -> 9) (fix f) 

Следуя точно той же логике, что и версия с error, рекурсивный вызов никогда не получает оценку и вы просто получите a 9.