Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Strange type error in Haskell let-expression -- what's the issue?

I came across a frustrating something in Haskell today.

Here's what happened:

  1. I wrote a function in ghci and gave it a type signature
  2. ghci complained about the type
  3. I removed the type signature
  4. ghci accepted the function
  5. I checked the inferred type
  6. the inferred type was exactly the same as the type I tried to give it
  7. I was very distressed
  8. I discovered that I could reproduce the problem in any let-expression
  9. Gnashing of teeth; decided to consult with the experts at SO

Attempt to define the function with a type signature:

Prelude Control.Monad> let myFilterM f m = do {x <- m; guard (f x); return x} :: (MonadPlus m) => (b -> Bool) -> m b -> m b

<interactive>:1:20:
    Inferred type is less polymorphic than expected
      Quantified type variable `b' is mentioned in the environment:
        m :: (b -> Bool) -> m b -> m b (bound at <interactive>:1:16)
        f :: (m b -> m b) -> Bool (bound at <interactive>:1:14)
      Quantified type variable `m' is mentioned in the environment:
        m :: (b -> Bool) -> m b -> m b (bound at <interactive>:1:16)
        f :: (m b -> m b) -> Bool (bound at <interactive>:1:14)
    In the expression:
          do { x <- m;
               guard (f x);
               return x } ::
            (MonadPlus m) => (b -> Bool) -> m b -> m b
    In the definition of `myFilterM':
        myFilterM f m
                    = do { x <- m;
                           guard (f x);
                           return x } ::
                        (MonadPlus m) => (b -> Bool) -> m b -> m b

Defined the function without a type signature, checked the inferred type:

Prelude Control.Monad> let myFilterM f m = do {x <- m; guard (f x); return x}
Prelude Control.Monad> :t myFilterM 
myFilterM :: (MonadPlus m) => (b -> Bool) -> m b -> m b

Used the function for great good -- it worked properly:

Prelude Control.Monad> myFilterM (>3) (Just 4)
Just 4
Prelude Control.Monad> myFilterM (>3) (Just 3)
Nothing

My best guess as to what is going on:
type annotations somehow don't work well with let-expressions, when there's a do-block.

For bonus points:
is there a function in the standard Haskell distribution that does this? I was surprised that filterM does something very different.

like image 312
Matt Fenwick Avatar asked Oct 05 '11 14:10

Matt Fenwick


2 Answers

The problem is the precedence of the type operator (::). You're trying to describe the type of myFilterM but what you're actually doing is this:

ghci> let myFilterM f m = (\
        do {x <- m; guard (f x); return x} \
        :: \
        (MonadPlus m) => (b -> Bool) -> m b -> m b)\
      )

(backslashes inserted for readability only, not legit ghci syntax)

Do you see the issue? I get the same problem for something simple like

ghci> let f x = x + 1 :: (Int -> Int)
<interactive>:1:15:
    No instance for (Num (Int -> Int))
      arising from the literal `1'
    Possible fix: add an instance declaration for (Num (Int -> Int))
    In the second argument of `(+)', namely `1'
    In the expression: x + 1 :: Int -> Int
    In an equation for `f': f x = x + 1 :: Int -> Int

The solution is to attach the type signature to the proper element:

ghci> let f :: Int -> Int ; f x = x + 1
ghci> let myFilterM :: (MonadPlus m) => (b -> Bool) -> m b -> m b; myFilterM f m = do {x <- m; guard (f x); return x}

And for bonus points, you want mfilter (hoogle is your friend).

like image 158
rampion Avatar answered Sep 21 '22 13:09

rampion


This is likely just an issue of type annotation syntax and binding precendence. If you write your example as,

let myFilterM :: (MonadPlus m) => (b -> Bool) -> m b -> m b; myFilterM f m = do {x <- m; guard (f x); return x} 

then GHCi will give you a high-five and send you on your way.

like image 40
Anthony Avatar answered Sep 25 '22 13:09

Anthony