Можно ли написать факториальную функцию так же быстро, как "учебник", по-другому?

Я рассматриваю это как общий вид факторной функции в Haskell:

factorial :: (Integral a) => a -> a
factorial n = product [1..n]

Я понимаю, что это самый элегантный способ, но когда я пишу свою собственную рекурсивную функцию, это значительно медленнее:

factorial :: (Integral a) => a -> a
factorial 1 = 1
factorial n = n * factorial (n - 1)

Не первое решение должно делать почти все, что делает первый, внутри? Как это происходит быстрее? Можно ли написать что-то так же быстро, как первое решение, не используя нотацию заметок или функцию продукта?

Ответ 1

Первая версия проще для GHC оптимизировать, чем вторая. В частности, продукт использует foldl:

product = foldl (*) 1

а при применении к [1..n] (который является просто 1 `enumFromTo` n) он подвергается fusion. Короче говоря, GHC тщательно разработал правила перезаписи, предназначенные для оптимизации промежуточных структур данных из фрагментов кода, где сразу же расходуются созданные списки (в случае factorial, foldl (*) 1 - потребитель и 1 `enumFromTo` n производитель).

Обратите внимание, что вы можете делать то, что делает GHC (factorial = foldl (*) 1 . enumFromTo 1), и получить ту же производительность.

Кроме того, ваша вторая функция даже не рекурсивна. Эта часть, которую вы могли бы довольно легко исправить, передавая в аккумулятор:

factorial :: (Integral a) => a -> a
factorial n = go n 1
  where
    go 0 m = m
    go n m = go (n-1) (n*m)

Рука об руку с этим - это тот факт, что для большинства числовых типов вы хотите, чтобы арифметика была строгой. Это сводится к добавлению BangPatterns в n и m.

Ответ 1

Ответ 2