[SOLVED] Haskell Linked-List Monad

Haskell Linked-List Monad

I am trying to write a Monad for a Linked-List enumerated datatype in haskell and I don't understand why my bind function (>>=) is getting errors in ghci.

data LL a = Sentinel | Node a (LL a)

instance Monad LL where
    return = pure

    (>>=) :: LL a -> (a -> LL b) -> LL b
    Sentinel >>= _ = Sentinel
    Node a Sentinel >>= f = f a
    Node a ll_a >>= f = Node (f a) (ll_a >>= f)

    (>>) :: LL a -> LL b -> LL b
    x >> y = x >>= \_ -> y

The Sentinelrepresents the end of the Linked-List LL and the Node includes a value of type a and another LL-element which is either another Node or a Sentinel

ghci gives me an error for ... = Node (f a) (ll_a >>= f) in the 9th line:

Couldn't match expected type ‘b’ with actual type ‘LL b’
      ‘b’ is a rigid type variable bound by
        the type signature for:
          (>>=) :: forall a b. LL a -> (a -> LL b) -> LL b

But why does it work for line 8 though?

Node a Sentinel >>= f = f a

Solution

Check the type of the result:

(>>=) :: LL a -> (a -> LL b) -> LL b
Sentinel >>= _ =
   Sentinel -- :: LL b , which is OK
Node a Sentinel >>= f =
   f a
   -- We have f :: a -> LL b
   -- Hence f a :: LL b , which is OK
Node a ll_a >>= f =
   Node (f a) (ll_a >>= f)
   -- We have f :: a -> LL b
   -- Hence f a :: LL b
   -- Node :: forall t. t -> LL t -> LL t
   -- To type (Node (f a) (...)) we need to pick t = LL b
   -- Hence Node (f a) (...) :: LL (LL b) , which is NOT OK

Note how in the last line we have LL (LL b) instead of the expected LL b. This is what GHC is complaining about.

This issue is also found in the standard list monad. There x >>= f is defined as concatMap f x, i.e. as concat (map f x). Here, concat is used to "flatten" a list-of-lists into a plain list. You need to do something similar: define concatLL :: LL (LL a) -> LL a, and then use that to define your (>>=).