Mapping over a nested functor?

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 these ads
This entry was posted in haskell, learning. Bookmark the permalink.

5 Responses to Mapping over a nested functor?

  1. Brent says:

    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.

  2. Michael Stone says:

    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!

  3. ephemient says:

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

  4. Brent says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s