CODEWITHSUNDEEP
haskelllambdaevaluation
Agnishom Chattopadhyay
Agnishom Chattopadhyay

Reputation: 2041

Contradictory Behaviour of Lambda Functions

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.

Upvotes: 27

Views: 1592

Answers (2)

duplode
duplode

Reputation: 34378

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

Upvotes: 8

freestyle
freestyle

Reputation: 3790

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.

Upvotes: 26

Related Questions