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?

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Deepest functor: fmap over arbitrarily nested collections is probably a good starting point.

Thanks Dan, that looks really interesting! Of course it is not the same thing as what I’m looking for, but it does seem like a good place to start.

Brent,

I don’t know how to completely answer your question, but I think I can give you some places to start.

What it all boils down to is that the functors you’re used to (i.e. those in class Functor) are really functors over values rather than functors over types and values. You can see this by looking at how these type-functions operate: as you already observed, members of class Functor stack up on top of one another making types like [[[a]]] (which I would prefer to write as (List . List . List a).

We, on the other hand, are looking for something different: we’re looking for a functor over types. We can see this because you want something that commutes with composition of types and that behaves nicely with respect to compositions of values and with identities of types and kinds. More concretely, we want to take a type composition like [[a]], write it as `List . List . a’, apply some mysterious G, and wind up with the type `(G List) . (G List) . (G a)’. Furthermore, we desire that this G satisfy all the nice algebraic properties that we desire of regular functors.

Unfortunately, I don’t know off the top of my head how to write down such a type-functor in Haskell, though Oleg, by way of Dan, has given us some excellent hints (thanks!)

Basically, if I understand his example correctly, Oleg wrote a logic program for the type-checker to use to calculate the `depth’ at which his functor should be applied. It works (I think!) by counting in Peano arithmetic: it counts “down” one by popping one type application off the structure it’s decomposing and then it counts up by composing another `fmap’ with the ‘deepest functor’ it’s building, effectively incrementing a (type) accumulator and it stops when it hits zero (an atom) and N (the desired functor), respectively.

The rest of the type-class machinery just what’s required to map atoms to Z (zero) and type applications to S (successor) so that the counting can be performed and to keep track of the correct types of the `fmap’s being composed in the accumulator.

Anyway, if I got all that right, we can probably solve your problem with the same machinery by providing a different increment to the accumulator: one that will make it build up something like

g . (fmap . g) . (fmap . fmap . g)

instead of

fmap . fmap . fmap

Anyway, good luck, and thanks for the fun question!

nfmap n e = foldr composeE [|id|] . take n $ iterate mapE e

where

composeE x y = appE (appE [|(.)|] x) y

mapE = appE [|fmap|]

sort3 :: (Ord a, Ord [a], Ord [[a]]) => [[[a]]] -> [[[a]]]

sort3 = $(nfmap 3 [|sort|])

ephemient: heh, neat. Of course, ultimately I’m interested in how to define the requisite type classes etc. so it will “just work”… but regardless, generating the code at compile-time with TH is pretty slick, too. =)