Explain monomorphism restriction to me please?

Question

I started doing 99 haskell problems and I was on problem 7 and my unittests were blowing up.

Apparently, it's due to this: http://www.haskell.org/haskellwiki/Monomorphism_restriction

I just wanted to make sure I understood this correctly because I'm kinda confused.

situation 1: func a is defined with no type def or with a non-strict type def and then used once, the compiler has no issues infering the type at compile time.

situation 2: the same func a is used many times in the program, the compiler can't be 100% sure what the type is unless it recomputes the function for the given arguments.

To avoid the computation loss, ghc complains to the programmer that it needs a strict type def on a to work correctly.

I think in my situation, assertEqual has the type def of

 assertEqual :: (Eq a, Show a) => String -> a -> a -> Assertion

I was getting an error when test3 was defined that I interpreted as saying that it had 2 possible types for the return of testcase3 (Show and Eq) and didn't know how to continue.

Does that sound correct or am I completely off?

problem7.hs:

-- # Problem 7
-- Flatten a nested list structure.

import Test.HUnit

-- Solution

data NestedList a = Elem a | List [NestedList a]

flatten :: NestedList a -> [a]
flatten (Elem x) = [x]
flatten (List x) = concatMap flatten x

-- Tests

testcase1 = flatten (Elem 5)
assertion1 = [5]

testcase2 = flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]])
assertion2 = [1,2,3,4,5]

-- This explodes
-- testcase3 = flatten (List [])

-- so does this:
-- testcase3' = flatten (List []) :: Eq a => [a]

-- this does not
testcase3'' = flatten (List []) :: Num a => [a]

-- type def based off `:t assertEqual`
assertEmptyList :: (Eq a, Show a) => String -> [a] -> Assertion
assertEmptyList str xs = assertEqual str xs []

test1 = TestCase $ assertEqual "" testcase1 assertion1
test2 = TestCase $ assertEqual "" testcase2 assertion2
test3 = TestCase $ assertEmptyList "" testcase3''

tests = TestList [test1, test2, test3]

-- Main
main = runTestTT tests

1st situation: testcase3 = flatten (List [])

GHCi, version 7.4.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( problem7.hs, interpreted )

problem7.hs:29:20:
    Ambiguous type variable `a0' in the constraints:
      (Eq a0)
        arising from a use of `assertEmptyList' at problem7.hs:29:20-34
      (Show a0)
        arising from a use of `assertEmptyList' at problem7.hs:29:20-34
    Probable fix: add a type signature that fixes these type variable(s)
    In the second argument of `($)', namely
      `assertEmptyList "" testcase3'
    In the expression: TestCase $ assertEmptyList "" testcase3
    In an equation for `test3':
        test3 = TestCase $ assertEmptyList "" testcase3
Failed, modules loaded: none.
Prelude> 

2nd situation: testcase3 = flatten (List []) :: Eq a => [a]

GHCi, version 7.4.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( problem7.hs, interpreted )

problem7.hs:22:13:
    Ambiguous type variable `a0' in the constraints:
      (Eq a0)
        arising from an expression type signature at problem7.hs:22:13-44
      (Show a0)
        arising from a use of `assertEmptyList' at problem7.hs:29:20-34
    Possible cause: the monomorphism restriction applied to the following:
      testcase3 :: [a0] (bound at problem7.hs:22:1)
    Probable fix: give these definition(s) an explicit type signature
                  or use -XNoMonomorphismRestriction
    In the expression: flatten (List []) :: Eq a => [a]
    In an equation for `testcase3':
        testcase3 = flatten (List []) :: Eq a => [a]
Failed, modules loaded: none.

Answer 1

It's not so much the monomorphism restriction, it's the resolution of ambiguous type variables by defaulting that causes the compilation failure.

-- This explodes
-- testcase3 = flatten (List [])

-- so does this:
-- testcase3' = flatten (List []) :: Eq a => [a]

-- this does not
testcase3'' = flatten (List []) :: Num a => [a]

flatten :: NestedList a -> [a]
flatten (Elem x) = [x]
flatten (List x) = concatMap flatten x

flatten imposes no constraints on the type variable a, so there's no problem with the definition of testcase3 as such, it would be polymorphic.

But when you use it in test3,

test3 = TestCase $ assertEmptyList "" testcase3 -- ''

you inherit the constraints of

assertEmptyList :: (Eq a, Show a) => String -> [a] -> Assertion

Now the compiler has to find out at which type testcase3 should be used there. There is not enough context to determine the type, so the compiler tries to resolve the type variable by defaulting. According to the defaulting rules, a context (Eq a, Show a) cannot be resolved by defaulting, since only contexts involving at least one numeric class are eligible for defaulting. So compilation fails due to an ambiguous type variable.

testcase3' and testcase3'' however fall under the monomorphism restriction due to the expression type signature which imposes constraints on the right hand side of the definition that are inherited by the left.

testcase3' fails to compile due to that, regardless of whether it is used in an assertion.

testcase3'' gets defaulted to [Integer] since the expression type signature imposes a numeric constraint. Thus when the type is monomorphised for testcase'', the constrained type variable is defaulted to Integer. Then there is no question of the type at which it is used in test3.

If you had given type signatures to the bindings instead of to the right hand side,

testcase3' :: Eq a => [a]
testcase3' = flatten (List [])

testcase3'' :: Num a => [a]
testcase3'' = flatten (List [])

both values would have compiled on their own to polymorphic values, but still only testcase3'' would be usable in test3, since only that introduces the required numeric constraint to allow defaulting.