CODEWITHSUNDEEP
haskellfactorial
Simon Bergot
Simon Bergot

Reputation: 10582

Built-in factorial function in Haskell

I know this sounds like a stupid question, but here it is: Is there a built-in factorial in Haskell?

Google gives me tutorials about Haskell explaining how I can implement it myself, and I could not find anything on Hoogle. I don't want to rewrite it each time I need it.

I can use product [1..n] as a replacement, but is there a true Int -> Int factorial built-in function?

Upvotes: 40

Views: 42302

Answers (8)

groot
groot

Reputation: 420

fact n = if n == 0 then 1 else n * fact(n-1)
fact n = foldl(*) 1 [1..n]
fact n = product [1..n]

You can choose either

Upvotes: 2

Christian Brolin
Christian Brolin

Reputation: 111

fac = product . flip take [1..]

Upvotes: 4

K. Takusagawa
K. Takusagawa

Reputation: 81

The best implementation of factorial I know of in Hackage is Math.Combinatorics.Exact.Factorial.factorial in the exact-combinatorics package. It uses an asymptotically faster algorithm than product [1..n].

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

Upvotes: 8

alopez
alopez

Reputation: 21

You have the product function which is in the standard prelude. Combined with ranges you can get a factorial function with minimal effort. 

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

Upvotes: 2

gatoatigrado
gatoatigrado

Reputation: 16850

Try Hayoo! to search (link on the top of hackage); it came up with this, for example

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

Upvotes: 4

sanjoyd
sanjoyd

Reputation: 3340

If you're looking for a lambda expression, then you can always use the classic fix (\f x -> if x == 0 then 1 else x * (f (x - 1))).

Upvotes: 1

hammar
hammar

Reputation: 139840

Even though it is commonly used for examples, the factorial function isn't all that useful in practice. The numbers grow very quickly, and most problems that include the factorial function can (and should) be computed in more efficient ways.

A trivial example is computing binomial coefficients. While it is possible to define them as

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

it is much more efficient not to use factorials:

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

So, no, it's not included in the standard prelude. Neither is the Fibonacci sequence, the Ackermann function, or many other functions that while theoretically interesting are not used commonly enough in practice to warrant a spot in the standard libraries.

That being said, there are many math libraries available on Hackage.

Upvotes: 58

Justin Ethier
Justin Ethier

Reputation: 134157

No, but you can easily write one. If you are concerned about having to rewrite the function each time you need it, you could always write it as part of a module or a library (depending on how far you want to take this, any how many other similar functions you have). That way you only need to write it once, and can quickly pull it in to any other projects when you need it.

Upvotes: 5

Related Questions