Я знаю, это звучит как глупый вопрос, но вот он: есть ли встроенный факториал в Haskell?
Google дает мне учебники о Haskell, объясняющие, как я могу реализовать его сам, и я не мог найти ничего в Hoogle. Я не хочу переписывать его каждый раз, когда мне это нужно.
Я могу использовать product [1..n] в качестве замены, но существует ли истинная факториальная встроенная функция Int -> Int?
Несмотря на то, что он обычно используется для примеров, факториальная функция не так полезна на практике. Числа растут очень быстро, и большинство проблем, которые включают факториальную функцию, могут (и должны) вычисляться более эффективно.
Тривиальный пример - вычисление биномиальных коэффициентов. Хотя их можно определить как
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.
Нет, но вы можете легко написать один. Если вас беспокоит необходимость переписывать функцию каждый раз, когда она вам нужна, вы всегда можете записать ее как часть модуля или библиотеки (в зависимости от того, насколько вы хотите это сделать, сколько у вас других подобных функций). Таким образом, вам нужно только написать его один раз и быстро потянуть его в любые другие проекты, когда вам это нужно.
Попробуй Хэйо! искать (ссылка на вершину хака); он придумал это, например
Лучшая реализация факториала, который я знаю в Hackage, Math.Combinatorics.Exact.Factorial.factorial в пакете exact-combinatorics. Он использует асимптотически более быстрый алгоритм, чем product [1..n].
fac = product . flip take [1..]
У вас есть функция 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
Если вы ищете выражение лямбда, вы всегда можете использовать классический fix (\f x -> if x == 0 then 1 else x * (f (x - 1))).