6

Look at this output from ghci:

Prelude> :t Data.Map.lookup
Data.Map.lookup :: Ord k => k -> Data.Map.Map k a -> Maybe a
Prelude> :t flip Data.Map.lookup
flip Data.Map.lookup :: Ord a => Data.Map.Map a a1 -> a -> Maybe a1
Prelude> let look = flip Data.Map.lookup
Loading package array-0.3.0.2 ... linking ... done.
Loading package containers-0.4.0.0 ... linking ... done.
Prelude> :t look
look :: Data.Map.Map () a -> () -> Maybe a

Why look's inferred type differs from type of flip Data.Map.lookup?

To give you some context. Initially I had small program and was trying to figure out why it produces compiler error:

import qualified Data.Map as M

type A = String
type B = String
data C = C1 | C2 | C3
     deriving (Eq, Ord)
type D = String

z :: A -> M.Map A B -> M.Map B C -> M.Map C D -> Maybe D
z a aToB bToC cToD = look aToB a >>= look bToC >>= look cToD
  where look = flip M.lookup

Ghci's reaction:

Prelude> :load main.hs
[1 of 1] Compiling Main             ( main.hs, interpreted )
Failed, modules loaded: none.

main.hs:10:52:
    Couldn't match expected type `C' with actual type `[Char]'
    Expected type: C -> Maybe D
      Actual type: A -> Maybe a0
    In the return type of a call of `look'
    In the second argument of `(>>=)', namely `look cToD'

I've found that this variation compiles well (type definitions are the same):

x :: A -> M.Map A B -> M.Map B C -> Maybe C
x a aToB bToC = look aToB a >>= look bToC
  where look = flip M.lookup

y :: A -> M.Map A B -> M.Map B C -> M.Map C D -> Maybe D
y a aToB bToC cToD = (x a aToB bToC) >>= look cToD
  where look = flip M.lookup

And after some experimentation it's turned up that if I put type of look explicitly - first version compiles well too:

z :: A -> M.Map A B -> M.Map B C -> M.Map C D -> Maybe D
z a aToB bToC cToD = look aToB a >>= look bToC >>= look cToD
  where look :: (Ord a) => M.Map a b -> a -> Maybe b
        look = flip M.lookup

Which leads me to my first question.

Tom Crockett
  • 30,818
  • 8
  • 72
  • 90
Ivan Danilov
  • 14,287
  • 6
  • 48
  • 66

1 Answers1

7

By default, top-level bindings are non-polymorphic unless an explicit type specifier is given; this is known as the 'monomorphism restriction'. Since no type specifier was given, GHC had to choose a way to instantiate k at the time you defined the function. It happened to choose k = ().

The idea behind this is that polymorphism can hurt performance by introducing a lot of vtable calls in the final compiled code; by forcing these to be resolved at compile time unless otherwise explicitly stated, this overhead can be avoided. This decision is rather controversial. GHC supports an extension to disable the monomorphism restriction entirely, by passing -XNoMonomorphismRestriction.

bdonlan
  • 224,562
  • 31
  • 268
  • 324
  • 6
    Note that normal defaulting won't set things to `()` all over the place; there's an extended defaulting mode used in GHCi that does that. – C. A. McCann Jul 31 '11 at 03:02
  • 2
    Or by adding comment `{-# LANGUAGE NoMonomorphismRestriction #-}` to the source file (just for completeness). – Ivan Danilov Jul 31 '11 at 03:36
  • 2
    I've been hanging around SO too long... I read the title of the question and before I even clicked the link thought "gotta be monomorphism." – sclv Jul 31 '11 at 04:43
  • 2
    Incidentally, while there is a legitimate debate over it for compiled source files, you practically never actually want the monomorphism restriction in GHCi. Everyone should add `:set -XNoMonomorphismRestriction` to their `~/.ghci` file. – Chris Smith Jul 31 '11 at 06:13
  • 3
    "The idea behind this is that polymorphism can hurt performance by introducing a lot of vtable calls in the final compiled code" Those aren't the problem - or at least not the biggest problem. The primary reason why the monomorphism restriction was introduced was that without it certain expressions will be evaluated multiple times when you wouldn't expect them to be. – sepp2k Jul 31 '11 at 12:27