Стиль без точек невелик

У меня есть следующий, часто цитируемый код для вычисления n-го числа Фибоначчи в Haskell:

fibonacci :: Int -> Integer
fibonacci = (map fib [0..] !!)
    where fib 0 = 0
          fib 1 = 1
          fib n = fibonacci (n-2) + fibonacci (n-1)

Используя это, я могу делать такие вызовы, как:

ghci> fibonacci 1000

и получите почти мгновенный ответ.

Однако, если я изменю приведенный выше код так, чтобы он не был в свободном стиле, т.е.

fibonacci :: Int -> Integer
fibonacci x = (map fib [0..] !!) x
    where fib 0 = 0
          fib 1 = 1
          fib n = fibonacci (n-2) + fibonacci (n-1)

он значительно медленнее. В той мере, в какой вызов, например

ghci> fibonacci 1000

зависаний.

Мое понимание заключалось в том, что эти две части кода были эквивалентны, но GHCi требует отличия. Кто-нибудь объясняет это поведение?

Ответы

Ответ 1

Чтобы заметить разницу, вам следует, вероятно, взглянуть на Core. Я предполагаю, что это сводится к сравнению (примерно)

let f = map fib [0..] in \x -> f !! x

к

\x -> let f = map fib [0..] in f !! x

Последний будет компрометировать f с нуля при каждом вызове. Первое не позволяет эффективно кэшировать один и тот же f для каждого вызова.

Бывает, что в этом конкретном случае GHC смог оптимизировать второй в первом, как только оптимизация включена.

Обратите внимание, однако, что GHC не всегда выполняет это преобразование, поскольку это не всегда оптимизация. Кэш, используемый первым, хранится в памяти навсегда. Это может привести к пустой памяти в зависимости от выполняемой функции.

Ответ 2

Я попытался найти его, но вычеркнул. Я думаю, что у меня есть это на моем ПК дома. Я читал, что функции, использующие фиксированную точку, были изначально быстрее. Существуют и другие причины использования фиксированной точки. Я столкнулся с этим, написав эту итеративную функцию Фибоначчи. Я хотел посмотреть, как будет выполняться итеративная версия, тогда я понял, что у меня нет готового способа измерения. Я неофит Хаскелла. Но вот итеративная версия для кого-то для тестирования. Я не мог определить это, если бы не использовал точку после первой последней функции. Я не мог его уменьшить. параметр [0,1] является фиксированным и не должен указываться в качестве значения параметра.

Prelude> fib = last . flip take (iterate (\ls -> ls ++ [last ls + last (init ls)]) [0,1])
Prelude> fib 25

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025]