Why did the Haskell typesystem fail to catch this?

Question

The following compiles without warning or error.

factors n = [x | x<-[1..n], n `mod` x == 0]
perfects n = [x | x <- [1..n], x == sum (factors (init x))]
main = putStrLn "hello"

Even though I made a mistake in it.

perfects n = [x | x <- [1..n], x == sum (factors (init x))]  -- incorrect
perfects n = [x | x <- [1..n], x == sum (init (factors x))]  -- should have been

Where is the static type checking to rescue?

The reason I think it should have caught the mistake is:

• factor clearly expects an Integral since its argument is used with mod, while init returns a List
• not to mention that x is drawn from a List of Integers and init expects a List

Answer 1

If you look at the type ghc has deduced for it you can see

perfects :: forall a. (Eq a, Integral [a]) => [a] -> [[a]]

So if you have an instance that makes lists be in class Integral it works. And ghc doesn't know that's not what you intend.

You'll get an error if you put the intended type signature on perfects, or of you use perfects in the way you intended (change main to print (perfects 42)).

EDIT This makes your code do something (nonsensical):

module Main where
factors n = [x | x<-[1..n], n `mod` x == 0]
perfects n = [x | x <- [1..n], x == sum (factors (init x))]

instance Num [a]
instance Integral a => Integral [a]
instance Real a => Real [a]
instance Enum [a] where
    enumFromTo _ _ = []

main = print (perfects 5)

So what you wrote could be what you intended. This is why it's good to always write type signatures, so that the compiler can see what you had in mind. Or at least, you should check that the inferred type is what you intended.

Answer 2

What augustss said, but I'll add some thoughts.

The issue (not problem!) here is that Haskell makes a tradeoff: more flexibility, at the cost of concrete error reporting. Since Haskell just allows many more things, there are a lot of situations where, compared to more mainstream languages, it either can't report an error, or the error it reports is more abstract than such other languages would report.

For example, suppose you meant to type 1 + 2, but you fat fingered and typed 1 0 2. Here's how Python responds:

Python 2.7.2 (default, Oct 11 2012, 20:14:37) 
[GCC 4.2.1 Compatible Apple Clang 4.0 (tags/Apple/clang-418.0.60)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 1 0 2
  File "<stdin>", line 1
    1 0 2
      ^
SyntaxError: invalid syntax

Simple: "you typed something wrong." Now Haskell:

GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> 1 0 2

<interactive>:2:1:
    No instance for (Num (a0 -> a1 -> t0)) arising from the literal `1'
    Possible fix:
      add an instance declaration for (Num (a0 -> a1 -> t0))
    In the expression: 1
    In the expression: 1 0 2
    In an equation for `it': it = 1 0 2

<interactive>:2:3:
    No instance for (Num a0) arising from the literal `0'
    The type variable `a0' is ambiguous
    Possible fix: add a type signature that fixes these type variable(s)
    Note: there are several potential instances:
      instance Num Double -- Defined in `GHC.Float'
      instance Num Float -- Defined in `GHC.Float'
      instance Integral a => Num (GHC.Real.Ratio a)
        -- Defined in `GHC.Real'
      ...plus three others
    In the first argument of `1', namely `0'
    In the expression: 1 0 2
    In an equation for `it': it = 1 0 2

<interactive>:2:5:
    No instance for (Num a1) arising from the literal `2'
    The type variable `a1' is ambiguous
    Possible fix: add a type signature that fixes these type variable(s)
    Note: there are several potential instances:
      instance Num Double -- Defined in `GHC.Float'
      instance Num Float -- Defined in `GHC.Float'
      instance Integral a => Num (GHC.Real.Ratio a)
        -- Defined in `GHC.Real'
      ...plus three others
    In the second argument of `1', namely `2'
    In the expression: 1 0 2
    In an equation for `it': it = 1 0 2

In Python, 1 0 2 is a syntax error. In Haskell, 1 0 2 means apply the function 1 to the arguments 0 and 2. Haskell's error message isn't "you can't do that," but rather, "you haven't told me how to coerce a number to a two-argument function" (no instance for Num (a0 -> a1 -> t0)).

In your case, you managed to write something that Haskell knows how to interpret, but means something very different from what you meant. The best thing to do here, as a programmer, is to use top-level type declarations that describe your intent, and then the compiler can check against those.

---

Final note: keep in mind that you can do this in Haskell:

-- | Treat lists of numbers as numbers.  Example:
--
-- >>> [1..3] * [2..5]
-- [2,3,4,5,4,6,8,10,6,9,12,15]
--
instance Num a => Num [a] where
    xs + ys = [x + y | x <- xs, y <- ys]
    xs * ys = [x * y | x <- xs, y <- ys]
    xs - ys = [x - y | x <- xs, y <- ys]
    negate xs = map negate xs
    abs xs = map abs xs
    signum xs = map signum xs
    fromInteger x = [fromInteger x]



-- | Treat functions as numbers if they return numbers.  The functions
-- must have the same argument type.  Example:
--
-- >>> 1 0 2
-- 1
instance Num a => Num (r -> a) where
    f + g = \r -> f r + g r
    f * g = \r -> f r * g r
    f - g = \r -> f r - g r
    negate f = negate . f
    abs f = abs . f
    signum f = signum . f
    fromInteger x = const (fromInteger x)

Same thing can be done with the Integral class.