« Rationals! » Draft of my TMR article on multiset partitions

Mapping over a nested functor?

Posted on August 16, 2007
Tagged
The other day I had a triply-nested list of type [[[a]]], and found myself applying this function to it:
sort . map sort . map (map sort)

This annoyed me. I want a way to say, “map this function over every level of this nested functor”. In other words, given a function transf :: (Functor f) => f a -> f a, I want a function nfmap which, given transf and a “nested functor” (i.e. something of type f a, or f (f a), or f (f (f a)), or …) applies transf on all levels (i.e. transf . fmap transf . fmap (fmap transf) …). Ideally, then, I would be able to write nfmap sort :: [[[a]]] -> [[[a]]] in place of the code that annoyed me.

Sadly, how to implement the type class NestedFunctor eludes me at the moment. Has anything like this been done before? (I’d be surprised if it hasn’t.) Anyone with some serious Haskell-type-fu want to show me how to implement this?