how to map functions to multi-level lists in Haskell

Question

This is my first post here, and I have to introduce myself by saying that I am a Haskell beginner. I love the promise of pure functional programming, but after 20 years of imperative programming (mostly Java), Haskell does not come naturally to me.

So here's my first question. I am trying to map a function to a multi-level list. This code works, but the depth level of the list where the mapping occurs is preset at 3:

(map . map . map) (+1) [[[1,4],[2,3]],[[5]]]

I need something more general, where I specify the level where the mapping happens (depth parameter in the line below), like so:

let depth = 3 :: Int
(foldl (.) id (replicate depth map)) (+1) [[[1,4],[2,3]],[[5]]]

Unfortunately, this does not work, I get this error:

Occurs check: cannot construct the infinite type: t0 = [t0]
Expected type: ([[[t0]]] -> [[[t0]]]) -> [[[t0]]] -> [[[t0]]]
  Actual type: ([[[t0]]] -> [[[t0]]]) -> [[[[t0]]]] -> [[[[t0]]]]
In the second argument of `replicate', namely `map'
In the third argument of `foldl', namely `(replicate depth map)'
In the expression:
  (foldl (.) id (replicate depth map))
    (+ 1) [[[1, 4], [2, 3]], [[5]]]

However, this code works:

foldl (.) id (replicate 3 negate) $ 7

So again, the questions is: how do I map a function onto a multi-level list, where the depth of the list is known in advance. I would like to do something like:

(foldl (.) id (replicate 3 map)) (+1) [[[1,4],[2,3]],[[5]]]

and get this result back:

[[[2,5],[3,4]],[[6]]]

Thank you in advance.

J. Abrahamson J. Abrahamson · Accepted Answer · 2014-03-24T17:37:12

What you're asking for is impossible (at least difficult) though it's difficult to see that at first.

The proper tool for analysis here is the compile-time/runtime distinction appearing in your code. In particular, let's say we have a function maps such that maps 3 f maps f into the third layer of a list. What is its type? Well, we can write them out

maps 1 :: (a -> b) -> [a]     -> [b]
maps 2 :: (a -> b) -> [[a]]   -> [[b]]
maps 3 :: (a -> b) -> [[[a]]] -> [[[b]]]
...

This may already look strange, but if it doesn't yet then take careful note of what's going on here: the ultimate type of maps n f depends upon the value of n, something that can only be known at runtime.

Since we have to typecheck things at compile time and the existence of maps would mean that we couldn't know the type of maps n without knowing the runtime value of n then we're sunk. Such a function, maps, cannot exist.

In theory anyway. In practice, we can certainly solve this kind of situation. But, as is usual when there are type errors, we first must become more clear about what we're trying to achieve.

The first interpretation of this function is that we'd like to extend the map operation on to an n-dimensional array. So long as we're fixing n at compile time (which, again, is going to be a bit challenging to escape from) then we may as well be explicit about this idea

newtype TwoD   a = TwoD   { getLists2d :: [[a]] }
newtype ThreeD a = ThreeD { getLists3d :: [[[a]]] }
newtype FourD  a = FourD  { getLists4d :: [[[[a]]]] }
-- etc...

Now each one of these has a natural extension of map. Indeed, this idea of many kinds of types being "mappable" is exactly the intuition of the Functor typeclass, so we can instantiate them all as Functors

instance Functor TwoD   where fmap f (TwoD   lists) = TwoD   ((map . map)       f lists)
instance Functor ThreeD where fmap f (ThreeD lists) = ThreeD ((map . map . map) f lists)
-- etc...

In fact, this is such a natural idea that GHC implements an extension which will derive these Functor instances for us.

{-# LANGUAGE DeriveFunctor #-}

newtype TwoD   a = TwoD   { getLists2d :: [[a]] }     deriving Functor
newtype ThreeD a = ThreeD { getLists3d :: [[[a]]] }   deriving Functor
newtype FourD  a = FourD  { getLists4d :: [[[[a]]]] } deriving Functor
-- etc...

and now fmap can be used over any of our n-dimensional array types quite naturally.

Another possible interpretation is that we'd like not to represent an n-dimensional array but instead a "Rose tree". The difference is that in n-dimensional arrays the "index sequence" of every value is n elements long. For instance, the upper left value is indexed at [0,0,0] in ThreeD. In a Rose tree, we have mixtures of lists and not each value is at the same depth. This means that we no longer have a static guarantee of the depth of a list the way we do with types like [a] versus [[[[a]]]], but it also means that all of the depth information now occurs at runtime.

Which is right where we want it.

Let's define Rose first.

data Rose a = Rose [Rose a] | L a deriving Functor -- Functor for free!

We can also produce a sample value of Rose Char to make it more clear how Rose works.

Rose [Rose [L 'f', L 'o', L 'o', Rose [L 'x', L 'y', L 'z']], L 'b', L 'a', L 'r']

I like to think of Rose as being similar to "lisp"-style lists, i.e. arbitrarily nested trees.

(('f' 'o' 'o' ('x', 'y' 'z')) 'b' 'a' 'r')

Again, however, the fun part is that since we now leave the depth of the Rose tree up to runtime (and indeed it can vary dynamically at runtime) we can use runtime information to map over it.

mapR :: Int -> (a -> a) -> Rose a
mapR 0 f (L a)     = L (f a)
mapR n f (L a)     = L a
mapR n f (Rose as) = Rose (map (mapR (n-1) f) as)

Note that unlike normal map, mapR's function parameter cannot change the type of Rose. This is because we're only mapping over a particular "layer" of the Rose tree and thus cannot uniformly change the types of every value inside of it. To do that, we still must use fmap from our derived Functor instance.

how to map functions to multi-level lists in Haskell

2 Answers