27

Using the following definitions:

lenDigits n = length (show n)
factorial n = product [1..n]

I evaluate the following

Prelude> ((lenDigits . factorial) 199) <= 199
False
Prelude> (\i -> ((lenDigits . factorial) i) <= i) 199
True

What is the reason for such behaviour? As I see it, the first expression is just the same as the second expression with the lambdas reduced.

3
  • 5
    You might also like comparing these two, which gets to the essence of the question, and avoids all the vagaries of having typeclasses lying around to confuse things: (id True, id 'a') is fine but (\f -> (f True, f 'a')) id is an error. Dec 8, 2016 at 19:48
  • @DanielWagner Why does this happen? Isn't id polymorphic? Dec 9, 2016 at 4:34
  • 3
    Yes indeed, id is polymorphic; and \f -> ... can be polymorphic; but inside the ..., f itself is not polymorphic! \f -> (f True, f 'a') is already a type error without ever mentioning id. This restriction is put in place to make type inference easier and to preserve the desirable property that any term that can be given a type at all has a most general type. Dec 9, 2016 at 5:01

2 Answers 2

26

Because in the first expression the first 199 has type Integer and the second has Int. But in the second expression both have type Int and factorial 199 can't be represented by the type Int.

5
  • 1
    Does this relate to monomorphism restriction?
    – mnoronha
    Dec 8, 2016 at 16:52
  • 14
    I don't think so. In the first example, the first 199 is free to default to Integer, but the second one is forced to be treated as Int because it is being compared to the return value of lenDigits. In the second, i is forced to be Int for the same reason, which in turn forces 199 to be an Int as well.
    – chepner
    Dec 8, 2016 at 16:55
  • Is there any reason the return type of length isn't polymorphic?
    – mnoronha
    Dec 8, 2016 at 17:03
  • 1
    @mnoronha Yes, for example perfomence. But you can use genericLength :: Num i => [a] -> i
    – freestyle
    Dec 8, 2016 at 17:07
  • 5
    @mnoronha See also: Why isn't `length` generic by default? at SE.SE.
    – duplode
    Dec 8, 2016 at 17:09
8

Here goes a step-by-step take on this question.

Let's begin with:

((lenDigits . factorial) 199) <= 199

According to the Haskell Report...

An integer literal represents the application of the function fromInteger to the appropriate value of type Integer.

That means our first expression is actually:

((lenDigits . factorial) (fromInteger (199 :: Integer)) 
    <= (fromInteger (199 :: Integer))

By itself, fromInteger (199 :: Integer) has the polymorphic type Num a => a. We now have to see whether this type is specialised in the context of the whole expression. Note that, until we find a reason for it not being so, we should assume that the polymorphic types of the two occurrences of fromInteger (199 :: Integer) are independent (Num a => a and Num b => b, if you will).

lenDigits is Show a => a -> Int, and so the...

(lenDigits . factorial) (fromInteger (199 :: Integer))

... to the left of the <= must be an Int. Given that (<=) is Ord a => a -> a -> Bool, the fromInteger (199 :: Integer) to the right of the <= also has to be an Int. The whole expression then becomes:

((lenDigits . factorial) (fromInteger (199 :: Integer)) <= (199 :: Int)

While the second 199 was specialised to Int, the first one is still polymorphic. In the absence of other type annotations, defaulting makes it specialise to Integer when we use the expression in GHCi. Therefore, we ultimately get:

((lenDigits . factorial) (199 :: Integer)) <= (199 :: Int)

Now, on to the second expression:

(\i -> ((lenDigits . factorial) i) <= i) 199

By the same reasoning used above, (lenDigits . factorial) i (to the left of <=) is an Int, and so i (to the right of <=) is also an Int. That being so, we have...

GHCi> :t \i -> (lenDigits . factorial) i <= i
\i -> (lenDigits . factorial) i <= i :: Int -> Bool

... and therefore applying it to 199 (which is actually fromInteger (199 :: Integer)) specialises it to int, giving:

((lenDigits . factorial) (199 :: Int)) <= (199 :: Int)

The first 199 is now Int rather than Integer. factorial (199 :: Int) overflows the fixed size Int type, leading to a bogus result. One way of avoiding that would be introducing an explicit fromInteger in order to get something equivalent to the first scenario:

GHCi> :t \i -> (lenDigits . factorial) i <= fromInteger i
\i -> (lenDigits . factorial) i <= fromInteger i :: Integer -> Bool
GHCi> (\i -> (lenDigits . factorial) i <= fromInteger i) 199
False

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.