Find the Bug
Here’s a pretty tricky bug I hunted down yesterday, with the help of oerjan on #haskell. If you weren’t there to see, it’s a lot of fun. Here’s the code:
foo n = product [24 - n .. 23] `div` product [1 .. n] bar n = length (takeWhile ((< 1000000) . foo) [1 .. n]) baz n = if bar n == n then n else bar n
And here’s the result:
cdsmith@devtools:~/haskell/projects$ ghci Strange.hs GHCi, version 6.7.20070703: http://www.haskell.org/ghc/ :? for help [1 of 1] Compiling Main ( Strange.hs, interpreted ) Ok, modules loaded: Main. *Main> bar 10 9 *Main> baz 10 10
The question: Why does
bar 10 evaluate to something different from
baz 10? By looking at the definition of
baz, you might convince yourself that
bar do the same thing. Apparently not.
Scroll down for the answer.
The problem is numeric overflow. The standard library
length function has a result type of
Int. The intermediate result in
foo is too large to fit in the data type
bar function has type
forall a. Integral a => a -> Int. When calling
bar directly, this isn’t a problem because the argument defaults to type
foo is evaluated entirely in arbitrary precision numbers. However, when
baz is evaluated, there is a comparison
bar n == n, so the result of bar must have the same type as its argument. The result is known to be
Int because the return type of
bar is not polymorphic. So the argument
n must also be of type
foo's inferred type is
Int -> Int, which causes the overflow.
All clear now?
If one wanted to take a lesson from this, it would be one of the following:
- Be careful with types.
- General purpose functions like
lengthshouldn’t use dangerous types like
Intshould be made less dangerous by throwing an exception on overflow.
Let’s take a poll: which lesson do you draw from it? Post in the comments.