Haskell error: Couldn't match type 'a' with 'b'

4
votes

i'm a newish to Haskell and have this piece of code:

import Control.Monad

data NestedList a = Elem a | List [NestedList a] deriving (Show)

instance Monad NestedList where
    return a = List [Elem a]
    (List (Elem a: xs)) >>= f = let a' = f a in a' `joinLists` xs

func :: a -> NestedList a
func a = List ([Elem a] ++ [Elem a])

joinLists :: NestedList a -> [NestedList a] -> NestedList a
joinLists (List a) b = List (a ++ b)

main = do let a = List [Elem 1, Elem 2] >>= func
          print a

What I am trying to do is to take a List with elements, replicate 1st element of the list and add a tail to this list. So List [Elem 1, Elem 2] would be equal to List [Elem 1, Elem 1, Elem 2]. I know that's not a good example of using Monads, but that's for the sake of learning.

I am getting an error like this:

Couldn't match type 'a' with 'b'
   'a' is a rigid type variable bound by
       the type signature for
          '>>= :: NestedList a -> (a -> NestedList b) -> NestedList b
   'b' is a rigid type variable bound by
       the type signature for
          '>>= :: NestedList a -> (a -> NestedList b) -> NestedList b
   Expected type: [NestedList b]
   Actual type: [NestedList a]
   In the second argument of 'joinLists', namely 'xs'

I understand the error is that it expects a different type variable of NestedList. What is the problem here?

2
haskell
your problem is using joinLists, a' is Elem b but xs is [Elem a]. The monad bind is (>>=) :: Monad m => m a -> (a -> m b) -> m b - josejuan
@josejuan a' is of type NestedList a = List [Elem a] and correct, xs is [Elem a] or [NestedList a]. And joinLists takes NestedList a and [NestedList a], so it shouldn't cause a problem. How can I transform [Elem a] to [Elem b]? - Aidas Simkus
@AidasSimkus f has type (a -> m b), that is where that type variable b comes from. - Lee Duhem
@AidasSimkus a' is of type Elem b, because f :: a -> NestedList b for any b. Even if you only use it with f :: a -> NestedList a, Monad should work for functions even with a and b being different. It is up to you how to create NestedList b out of the remaining NestedList a. Perhaps, applying f to each element of xs would work, but that depends on the logic of what you are doing. Also, joinLists doesn't have a pattern for Elem a, so you are going to feel that soon. - Sassa NF

2 Answers

7
votes

I know that's not a good example of using Monads, but that's for the sake of learning.

Specifically, your implementation of >>= is not general enough. What you have given has type:

List a -> (a -> List a) -> List a

but Haskell insists on

List a -> (a -> List b) -> List b

To me it looks like there is no good way to achieve what you want in a monad.

The deeper reason is that you want to modify the structure of the "container", rather than doing something with the "element" in a container specific way.

2
votes

For your reference, here is a working monad instance of NestedList. It should not be very difficult to verify that this instance satisfies the monad laws.

import Control.Monad

data NestedList a = Elem a | List [NestedList a] deriving (Show)

instance Monad NestedList where
    return x = Elem x
    (Elem x)  >>= f = f x
    (List xs) >>= f = List $ map step xs
        where step (Elem a) = f a
              step lst = lst >>= f

Here is a test program:

import Control.Monad

data NestedList a = Elem a | List [NestedList a] deriving (Show)

instance Monad NestedList where
    return x = Elem x
    (Elem x)  >>= f = f x
    (List xs) >>= f = List $ map step xs
        where step (Elem a) = f a
              step lst = lst >>= f


double :: a -> NestedList a
double a = List ([Elem a] ++ [Elem a])


add :: (Num a) => a -> a -> NestedList a
add a e = Elem $ a + e


main = do let a = Elem 1 >>= double
          let b = List [Elem 1, Elem 2] >>= double
          let c = List [Elem 2,List [Elem 3,Elem 4],Elem 5] >>= add 1
          print a
          print b
          print c

And its output:

$ runhaskell t.hs 
List [Elem 1,Elem 1]
List [List [Elem 1,Elem 1],List [Elem 2,Elem 2]]
List [Elem 3,List [Elem 4,Elem 5],Elem 6]