I was trying to make a class of "flattenable" data structures in Haskell. My first thought was to use multi-parameter type classes to assert a relation between two data types, one which is flattened and another which holds flattenable elements. Such a class is the class F below without the functional dependency. When given an instance declaration like F Tree [], applying flt to a structure fails with messages like no instance for `F Tree m`. I ended up writing the following (where foldT is fold over trees, etc.), in order to avoid said errors:

class (Functor m, Monad m) => F t m | t -> m where
flt :: t a -> m a
unflt :: F t' m => t' (t a) -> m a
unflt = join . fmap flt . flt

instance F Tree [] where flt = foldT (\a b c -> a : b ++ c) []
instance F Maybe [] where flt = maybeToList

Now, I would like to have F be a relation between a flattenable data type and, for instance, a monoid in which I can accumulate the flattened data type. Two things: I can't get a monoid constraint to operate properly over the variable m in unflt. This fails with messages like no instance for `Monoid Tree [Integer]`, and so on. I'm not sure why. Secondly, I would like to be able to have flt be able to return different "container structures", e.g., a custom sequence or a list. But the functional dependency I introduced prohibits this.

How would you handle this problem? Thanks.