Встроенная функция факториала в Haskell

Question

Я знаю, это звучит как глупый вопрос, но вот он: есть ли в Haskell встроенный факториал?

Google дает мне учебные пособия по Haskell, объясняющие, как я могу реализовать это сам, и я не смог найти ничего в Hoogle. Я не хочу переписывать его каждый раз, когда мне это нужно.

Я могу использовать product [1..n] в качестве замены, но есть ли истинная Int -> Int факторная встроенная функция?

Answer 1

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

Тривиальным примером является вычисление биномиальных коэффициентов. Пока их можно определить как

choose n k = factorial n `div` (factorial k * factorial (n-k))

гораздо эффективнее не использовать факториалы:

choose n 0 = 1
choose 0 k = 0
choose n k = choose (n-1) (k-1) * n `div` k 

Так что нет, это не входит в стандартную прелюдию. Ни последовательность Фибоначчи, ни функция Аккермана, ни многие другие функции, которые теоретически интересны, не используются на практике достаточно часто, чтобы гарантировать место в стандартных библиотеках.

Как говорится, в Hackage есть много математических библиотек .

Answer 2

Лучшая реализация факториала, которую я знаю в Hackage, - это Math.Combinatorics.Exact.Factorial.factorial в пакете exact-combinatorics.Он использует асимптотически более быстрый алгоритм, чем product [1..n].

http://hackage.haskell.org/package/exact-combinatorics

Answer 3

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

Answer 4

Попробуйте Hayoo! искать (ссылка наверху взлома); это пришло с этим, например

http://hackage.haskell.org/packages/archive/statistics/latest/doc/html/Statistics-Math.html#v:factorial

Answer 5

fac = product . flip take [1..]

Answer 6

У вас есть функция product, которая входит в стандартную прелюдию.В сочетании с диапазонами вы можете получить факториальную функцию с минимальными усилиями.

factorial n = product [n, n-1 .. 1]
nCr n r = n' `div` r'
    where
    -- unroll just what you need and nothing more
    n' = product [n, n-1 .. n-r+1]
    r' = factorial r

Answer 7

Если вы ищете лямбда-выражение, то вы всегда можете использовать классический fix (\f x -> if x == 0 then 1 else x * (f (x - 1))).