[Haskell-beginners] Functional Dependencies

[dan portin]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20101209/4ebb8b45/attachment.htm>