Trouble with creating join when making monad instance of an object

Question

I currently have a newtype instance which I should translate into a monad. I am having trouble with defining the bind to this particular monad where the newtype is defined as:

newtype Thing xs = Thing {runThing :: [[xs]]} deriving (Show)

I have defined a join that takes the monad one level down.

join' :: Thing(Thing a) -> Thing a
join' xs = (concat (map runThing (concat (Thing xs))))

and planned to apply the function in the bind like so

Thing xs >>= f = Thing(map (map f) $ (runThing (Thing xs)))

which doesn't compile and also tried:

join' xs =  head (concat (runThing xs))
Thing a >>= f =join' (fmap f (Thing a)) 

does but I understand that it only maps to the head of a list and uses the fmap I defined in a functor like so:

instance Functor  Thing where
    fmap f (Thing [[]]) = Thing [[]]
    fmap f (Thing a) = Thing (nestedMap f a)

How would I build a join that allows me to map and create a new Thing?

Answer 1

The smallest fix to your original definition of join' is to use runThing instead of Thing, and then add a top-level wrapper:

join' xs = Thing (concat (map runThing (concat (runThing xs))))

We can then define (>>=) in terms of fmap and join' in the standard way:

xss >>= f = join' (fmap f xss)

Unfortunately, this definition doesn't satisfy the monad laws:

> Thing [[1,2]] >>= return
Thing [[1],[2]]

The laws require that the result of that computation be again Thing [[1,2]].

However, using the swap construction from Composing Monads with swap = sequence, we can construct this alternate join':

join' = Thing . join . fmap (fmap join . sequence . fmap runThing) . runThing

I believe, though I have not proven, that the conditions required of swap are satisfied, so that this whole construction may be used to produce a law-abiding monad.

The construction proposed above fails the associativity law. Rats! In conclusion: everything I've tried so far to give an alternate join' fails at least one of the monad laws.

Answer 2

A Thing contains a list of list of as. So that means that a Thing (Thing a) contains a list of list of Thing as, and these thus contain a list of list of as.

We could thus concatenate these lists together. We can first unpack the outer Thing, which will give us a [[ Thing a ]]. By using concat :: Foldable f => f [a] -> [a], we convert this to a [Thing a]. Now we can use concatMap :: Foldable f => (a -> [b]) -> f a -> [b] with runThing as function, to transform this to a [[a]], and then we can wrap that value back in a Thing:

join' :: Thing (Thing a) -> Thing a
join' (Thing xs) = Thing (concatMap runThing (concat xs))