Haskell: Rigid type variable error when pattern matching bind operator

Question

I'm trying to run this

newtype Test a = Test (Int, a)

instance Monad Test where
    Test (_, []) >>= k =
        k []
    Test (_, a) >>= k =
        k a
    return a =
        Test (0, a)

And I get the error:

Couldn't match expected type `a' with actual type `[t0]'
  `a' is a rigid type variable bound by
      the type signature for >>= :: Test a -> (a -> Test b) -> Test b
      at C:\Users\david.phillips\Documents\code\test.hs:4:5
In the pattern: []
In the pattern: (_, [])
In the pattern: Test (_, [])

I get a similar error when I tried using a case statement instead of 2 versions of >>=.

I'm fairly new to haskell and can't see why this wouldn't work.

---

Edit: Sorry, it's a bad example. Suppose that the first definition of >>= gave a different output.

Answer 1

class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fail :: String -> m a

Monad instances are parameterized over a type variable a. You are essentially claiming that it is not, because in the place of that variable, you have pattern matched on the empty list constructor, [], meaning "a is a list of something." The type of eg. bind could, with explicit quantification, be written:

(>>=) :: forall a. m a -> (a -> m b) -> m b

Your definition cannot possibly hold for ALL a.

Answer 2

As an addition to Sarah's answer, you can actually omit your specific pattern match,

 Test (_, []) >>= f = f []

is the same as

 Test (_, a) >>= f = f a

So you can really just write this as

 Test (_, a) >>= f = f a
 return a          = (0, a)

---

Now remember that in addition to have the right types, we're supposed to have that

 m >>= return    = m
 return a >>= f  = f a
 (a >>= b) >>= c = a >>= (\a' -> b a' >>= c)

This worries me though, as

 m = Test (1, 'c')
 m >>= return === return 'c' === (0, 'c') /== m

So return is no longer functioning as an identity and you're breaking the 1st monad law. Fixing this would mean return would have to preserve the first element of the tuple, problematic since we don't actually tell it about it.

Naively, let's just clobber the first tuple element that our function returns.

 Test (a, b) >>= f = Test (a, snd (f b))

Now

 Test (1, 'c') >>= return == Test (1, snd (return 'c')) == Test (1, 'c')

But we're still in trouble,

 let f a = Test (1, a)
 return a >>= f == Test (0, snd (f a)) == Test (0, a) /== f a

So the trick here is to do what the state monad does

 newtype Test a = Test{ unTest :: Int -> (Int, a) }

 instance Monad Test where
   return a = Test $ \i -> (i, a)
   (Test m) >>= f = Test $ \i -> let (i', a) = m i
                    in unTest (f a) $ i'

Which does satisfy the monad laws*. Happily this already exists in Control.Monad.State.

** modulo seq