Monad error (Could not deduce)

Question

I'm trying to build a simple monad calculator, but it wont compile for some reason.

{-# LANGUAGE GADTs #-}

module Main where

data Result a = Value a | Undefined deriving (Show, Eq)

data Calculator x a where
  Bind :: Calculator x a -> (a -> Calculator x b) -> Calculator x b
  Return :: a -> Calculator x a
  Add :: a -> a -> Calculator x a
  Div :: a -> a -> Calculator x a

instance Monad (Calculator x) where
  return = Return
  (>>=) = Bind

calculate :: Calculator (Result Integer) Integer
calculate = do
  value <- addr 1 2
  divr 1 value

addr :: a -> a -> Calculator (Result a) a
addr a b = Add a b

divr :: a -> a -> Calculator (Result a) a
divr a b = Div a b

eval :: (Integral a, Num a, Eq a) => Calculator (Result a) a -> Result a
eval (Add a b) = Value (a + b)
eval (Div a b)
  | b == 0    = Undefined
  | otherwise = Value $ a `div` b

eval (Bind m f) =
  case eval m of
    Value v -> eval $ f v
    _       -> undefined -- for now

The error I'm getting is this

Main.hs:35:13:
    Could not deduce (a1 ~ a)
    from the context (Integral a, Num a, Eq a)
      bound by the type signature for
                 eval :: (Integral a, Num a, Eq a) =>
                         Calculator (Result a) a -> Result a
      at Main.hs:28:9-72
      ‘a1’ is a rigid type variable bound by
           a pattern with constructor
             Bind :: forall x b a.
                     Calculator x a -> (a -> Calculator x b) -> Calculator x b,
           in an equation for ‘eval’
           at Main.hs:34:7
      ‘a’ is a rigid type variable bound by
          the type signature for
            eval :: (Integral a, Num a, Eq a) =>
                    Calculator (Result a) a -> Result a
          at Main.hs:28:9
    Expected type: Calculator (Result a) a
      Actual type: Calculator (Result a) a1
    Relevant bindings include
      f :: a1 -> Calculator (Result a) a (bound at Main.hs:34:14)
      m :: Calculator (Result a) a1 (bound at Main.hs:34:12)
      eval :: Calculator (Result a) a -> Result a (bound at Main.hs:29:1)
    In the first argument of ‘eval’, namely ‘m’
    In the expression: eval m

The error occurs on the third to last line. Any one knows why?

I'm using ghci 7.8.4. What I'm I missing?

Answer 1

First of all, your constraints need to be pushed into the Calculator constructors. To see why, let's rename the type variables in Bind's signature slightly:

data Calculator x a where
  Bind :: Calculator x b -> (b -> Calculator x a) -> Calculator x a

eval :: (Integral a, Num a, Eq a) => ...
eval (Bind m f) = ...

Here, m has type Calculator x b, and the constraints on a (namely, (Integral a, Num a, Eq a)) don't impose anything on b, so you don't have a hope of recursively calling eval on m.

This one is straightforward to fix:

data Calculator x a where
  Bind :: Calculator x a -> (a -> Calculator x b) -> Calculator x b
  Return :: a -> Calculator x a
  Add :: (Num a) => a -> a -> Calculator x a
  Div :: (Num a, Eq a, Integral a) => a -> a -> Calculator x a

and then eval no longer needs constraints on a since it will be provided by pattern matching on the relevant constructor.

The other problem stems from the x type parameter of Calculator. In

Bind :: Calculator x b -> (b -> Calculator x a) -> Calculator x a

note that the choice of x stays the same. So when you pattern match on Bind m f :: Calculator (Result a) a, you get

m :: Calculator (Result a) b
f :: b -> Calculator (Result a) a

However, eval's type can only be instantiated to Calculator (Result a) a -> Result a or Calculator (Result b) b -> Result b, so we can't apply it recursively on m.

The solution is to parametrize Calculator on a functor instead of a type, because then we can type eval :: Calculator Result a -> Result a:

{-# LANGUAGE GADTs, KindSignatures #-}

module Main where

data Result a = Value a | Undefined deriving (Show, Eq)

data Calculator (f :: * -> *) a where
  Bind :: Calculator f a -> (a -> Calculator f b) -> Calculator f b
  Return :: a -> Calculator f a
  Add :: (Num a) => a -> a -> Calculator f a
  Div :: (Num a, Eq a, Integral a) => a -> a -> Calculator f a

instance Monad (Calculator f) where
  return = Return
  (>>=) = Bind

calculate :: Calculator Result Integer
calculate = do
  value <- addr 1 2
  divr 1 value

addr :: (Num a) => a -> a -> Calculator Result a
addr a b = Add a b

divr :: (Num a, Eq a, Integral a) => a -> a -> Calculator Result a
divr a b = Div a b

eval :: Calculator Result a -> Result a
eval (Add a b) = Value (a + b)
eval (Div a b)
  | b == 0    = Undefined
  | otherwise = Value $ a `div` b

eval (Bind m f) =
  case eval m of
    Value v -> eval $ f v
    _       -> undefined -- for now