CODEWITHSUNDEEP
haskellinteger-overflow
Jesse Sainz
Jesse Sainz

Reputation: 141

Haskell length list + factorial

I'm very new to Haskell. I've been trying to implement n_choose_r but for some reason my factorial function is returning strange values.

Main.hs

factorial 0 = 1
factorial n = n * factorial (n-1)

subsets k list = factorial n where
    n = length list

some different cases

> subsets 3 [1..4]
24 // correct value
> factorial 60
8320987112741390144276341183223364380754172606361245952449277696409600000000000000
> subsets 3 [1..60]
-8718968878589280256 // wrong value
> subsets 3 [1..100]
0 // wrong value

It seems the numbers get wonkier the longer the list. Can anyone explain?

Upvotes: 2

Views: 150

Answers (1)

Joseph Sible-Reinstate Monica
Joseph Sible-Reinstate Monica

Reputation: 48672

Your factorial function is polymorphic: it has type (Eq p, Num p) => p -> p. When you just call it like factorial 60, p gets instantiated as Integer (this choice is called "type defaulting"), which is arbitrary-precision and has no upper bound. However, length is not polymorphic in its output: it always returns an Int. Haskell won't automatically convert between numeric types for you, so when you call factorial with the result of length, it uses Int too, which does have an upper bound, which in your case appears to be 9223372036854775807 (which you can verify by doing maxBound :: Int). To work around this problem, you can either convert from Int to Integer yourself:

subsets k list = factorial (toInteger n) where
    n = length list

or use genericLength, which is the same as length except for being polymorphic in its output type:

import Data.List

subsets k list = factorial n where
    n = genericLength list

Note that if you use the latter option, you need to be careful not to do anything else that would force use of Int instead of defaulting to Integer.

Upvotes: 4

Related Questions