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

В Haskell это простое (наивное) определение фиксированной точки

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

Но вот как это реализовано в Haskell (более эффективно)

fix f = let x = f x in x

Мой вопрос: почему второй более эффективен, чем первый?


haskell fixpoint-combinators
person Vijaya Rani    schedule 21.05.2016    source источник
comment
на каком основании вы утверждаете, что один эффективнее другого - можете ли вы предоставить какие-то доказательства   -  person epsilonhalbe    schedule 21.05.2016
comment
Ну, во-первых, кажется, что он работает быстрее. А также см. здесь h2.jaguarpaw.co.uk/posts/polymorphic- комбинатор рекурсии   -  person Vijaya Rani    schedule 21.05.2016

Ответы (3)


arrow_upward
22
arrow_downward

Медленный 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 приводит к тому, что для x выделяется отложенный преобразователь, а указатель на этот преобразователь передается в f. При первой оценке fix' f оценивается преобразователь, и все ссылки на него (в частности, ту, которую мы передаем на f) перенаправляются на результирующее значение. Просто так получается, что x получает значение, которое также содержит ссылку на x.

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

person András Kovács    schedule 21.05.2016
comment
Я думаю, что сегодня я немного не в состоянии разобрать английский, но если вы говорите, что вызывает f ровно один раз, вы не говорите об оценке f в какой-то момент, верно? потому что, очевидно, вам придется вызывать facf пару раз, независимо от того, какая магия задействована (перемещение trace в facf покажет это) - person Random Dev; 21.05.2016
comment
facf не является рекурсивным, мы вызываем его один раз, а fix' возвращает объект функции. Когда мы вызываем этот функциональный объект с числовым аргументом, он рекурсивно вызывает себя, возможно, несколько раз (что можно снова отследить, как вы говорите). - person András Kovács; 21.05.2016
comment
Спасибо за объяснение. У меня более общий вопрос. Можно ли «оптимизировать» все рекурсивные функции с помощью этого подхода let привязки? Если да, то почему внутри GHC не используется этот метод для оптимизации рекурсий? Я бы предположил, что наивный способ написания рекурсивных функций легче читать и понимать. - person Vijaya Rani; 21.05.2016
comment
Простые рекурсивные определения @VijayaRani уже настолько быстры и оптимизируемы, насколько это возможно. Это просто медленное определение fix, которое приводит к накладным расходам по сравнению с простыми рекурсивными определениями. - person András Kovács; 21.05.2016
comment
Это что-то, что на самом деле гарантируется спецификацией языка, или это зависит от частных внутренних деталей реализации одной конкретной версии одной конкретной реализации? - person Jörg W Mittag; 22.05.2016

arrow_upward
10
arrow_downward

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

fix (1 :)

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

person dfeuer    schedule 21.05.2016

arrow_upward
5
arrow_downward

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

fix f = f (fix f)

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

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

Но

fix f = let x = f x in x

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

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

person Petr    schedule 21.05.2016
comment
Я не думаю, что есть какое-либо встраивание. - person András Kovács; 21.05.2016
comment
@ AndrásKovács Верно. Оба варианта fix компилируются по-разному, один через привязку let rec, другой через rec. (-ddump-simpl). - person Zeta; 21.05.2016