Почему эта версия "fix" более эффективна в Haskell?

Ответ 1

Медленный fix вызывает f на каждом этапе рекурсии, а быстрый вызывает f ровно один раз. Его можно визуализировать с помощью трассировки:

import Debug.Trace

fix  f = f (fix f)
fix' f = let x = f x in x

facf :: (Int -> Int) -> Int -> Int
facf f 0 = 1
facf f n = n * f (n - 1)

tracedFacf x = trace "called" facf x

fac  = fix tracedFacf
fac' = fix' tracedFacf

Теперь попробуйте запустить:

> fac 3
called
called
called
called
6
> fac' 3
called
6

Более подробно let x = f x in x приводит к тому, что ленивый thunk выделяется для x, а указатель на этот thunk передается на f. При первой оценке fix' f, thunk оценивается и все ссылки на него (здесь конкретно: тот, который мы передаем на f) перенаправляются на результирующее значение. Просто случается, что x получает значение, которое также содержит ссылку на x.

Я признаю, что это может быть скорее изгиб ума. Это то, к чему нужно привыкнуть при работе с лени.

Ответ 2

Я не думаю, что это всегда (или обязательно когда-либо) помогает, когда вы вызываете fix с помощью функции, которая принимает два аргумента для создания функции, принимающей один аргумент. Вам нужно будет запустить некоторые тесты, чтобы их увидеть. Но вы также можете вызвать его с помощью функции, принимающей один аргумент!

fix (1 :)

- круговой связанный список. Используя наивное определение fix, он вместо этого будет бесконечным списком, а новые произведения будут построены лениво, когда структура будет принудительно.

Ответ 3

Я считаю, что это уже было задано, но я не смог найти ответ. Причина в том, что первая версия

fix f = f (fix f)

- рекурсивная функция, поэтому она не может быть встроена, а затем оптимизирована. Из руководства GHC:

Например, для саморекурсивной функции прерыватель цикла может быть только самой функцией, поэтому прагма INLINE всегда игнорируется.

Но

fix f = let x = f x in x

не является рекурсивным, рекурсия перемещается в привязку let, поэтому возможно встроить ее.

Обновление: Я провел несколько тестов, и, хотя предыдущая версия не является встроенной, в то время как последняя делает это, она, похоже, не имеет решающего значения для производительности. Таким образом, другие объяснения (один объект в куче против создания каждой итерации) кажутся более точными.