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.

• Killimanjaro: Happened to see that too when i added that same exact line with bind
• Daniel Wagner: @Killimanjaro Never mind, I was wrong as usual. Even the swap construction doesn't work properly; I should have known I would have to sit down and prove the conditions they stated instead of just guessing. The construction seems to satisfy the identity laws, but the associativity law is still not satisfied.

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))

• Killimanjaro: Isnt that essentially what have in join' originally? Also thank you.
• willeM_ Van Onsem: @Killimanjaro: In your join' you wrapped the value in a Thing, instead of unwrapping. Notice the concat xs, and the the Things xs in the head. Not vice versa.
• Daniel Wagner: ...but even after this fix, the monad laws are not satisfied. See my answer.
• willeM_ Van Onsem: @DanielWagner: no indeed, I'm not sure we can construct a monad here.