Type check error in Haskell monad chaining

Question

I'm new to Haskell and I'm just following the example on RWH. I'm having problems with the following programs on Chapter 14:

import qualified Data.Map as M

type PersonName = String
type PhoneNumber = String
type BillingAddress = String
data MobileCarrier = Honest_Bobs_Phone_Network
                   | Morrisas_Marvelous_Mobiles
                   | Petes_Plutocratic_Phones
                     deriving (Eq, Ord)

findCarrierBillingAddress :: PersonName
                          -> M.Map PersonName PhoneNumber
                          -> M.Map PhoneNumber MobileCarrier
                          -> M.Map MobileCarrier BillingAddress
                          -> Maybe BillingAddress
-- This will work
findCarrierBillingAddress person phoneMap carrierMap addressMap = do
  phone <- M.lookup person phoneMap
  carrier <- M.lookup phone carrierMap
  address <- M.lookup carrier addressMap
  return address

-- This will NOT work:
findCarrierBillingAddress person phoneMap carrierMap addressMap =
    return person >>=
    lookup phoneMap >>=
    lookup carrierMap >>=
    lookup addressMap
  where lookup = flip M.lookup

It seems that when writing findCarrierBillingAddres in the monad chaining format using >>=, it just does not type check:

/home/bruce/Programming/haskell/real/ch14/hello.hs:21:9:
    Couldn't match type `[Char]' with `MobileCarrier'
    Expected type: MobileCarrier -> Maybe BillingAddress
      Actual type: PersonName -> Maybe BillingAddress
    In the return type of a call of `lookup'
    In the second argument of `(>>=)', namely `lookup addressMap'
    In the expression:
      return person >>= lookup phoneMap >>= lookup carrierMap
      >>= lookup addressMap

/home/bruce/Programming/haskell/real/ch14/hello.hs:21:16:
    Couldn't match type `MobileCarrier' with `[Char]'
    Expected type: M.Map PersonName BillingAddress
      Actual type: M.Map MobileCarrier BillingAddress
    In the first argument of `lookup', namely `addressMap'
    In the second argument of `(>>=)', namely `lookup addressMap'
    In the expression:
      return person >>= lookup phoneMap >>= lookup carrierMap
      >>= lookup addressMap
Failed, modules loaded: none.

The question is.. why the second format using >>= would not type check?

Answer 1

It's just the monomorphism restriction acting up again. Since you have a pattern binding with no type signature the inferred type is monomorphic and therefore determined by the first usage.

Just change it to

lookup m k = flip M.lookup m k

or even

lookup m = flip M.lookup m

You just have to convince GHC to generalize the function which it won't do when it's just a simple pattern binding. Adding a parameter turns it into a function binding which means that it will be fully generalized.

If I lost you a bit up there, I've blogged about this

Answer 2

You are being hit with the Monomorphism Restriction when the type inferencer is trying to deduce the type for your local lookup function.

Rather than deducing the most general type, it determines from the first use of lookup that it should have the type lookup :: Map [Char] [Char] -> [Char] -> Maybe [Char], which cannot be unified when you then try to use it on values of Map [Char] MobileCarrier.

Your first option is to disable the Monomorphism Restriction with the pragma {-# LANGUAGE NoMonomorphismRestriction #-}. The second option is to add a type signature to lookup as so

findCarrierBillingAddress person phoneMap carrierMap addressMap =
    return person >>=
    lookup phoneMap >>=
    lookup carrierMap >>=
    lookup addressMap
  where lookup :: Ord k => M.Map k a -> k -> Maybe a
        lookup = flip M.lookup