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.

Answer 1

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.

Answer 2

The functions you're working with are

foldl (.) id (replicate depth map)

And

foldl (.) id (replicate 3 negate)

The second compiles, but the first does not, why?

The error we suggests that at some point, the compiler is finding an expression that must be both a and [a], which doesn't for obvious reasons. The type a can not be the same as the type [a], otherwise you get infinitely nested lists which would never evaluate to anything. So let's look at our types in GHCi

> :t replicate 3 map
replicate 3 map :: [(a -> b) -> [a] -> [b]]
> :t replicate 3 negate
replicate 3 negate :: Num a => [a -> a]

This is our second clue, the type of replicate 3 map is quite different than replicate 3 negate, if we ignore the Num a

[(a -> b) -> [a] -> [b]]
-- Compared to
[a -> a]

The former has 2 arguments while the second only has 1. So what happens if we manually look at the types as we keep adding another composition?

> :t map
map :: (a -> b) -> [a] -> [b]
> :t map . map
map . map :: (a -> b) -> [[a]] -> [[b]]
> :t map . map . map
map . map . map :: (a -> b) -> [[[a]]] -> [[[b]]]

So we can see a pattern forming, each composition adds a nesting of list. And for negate?

> :t negate
negate :: Num a => a -> a
> :t negate . negate
negate . negate :: Num a => a -> a
> :t negate . negate . negate
negate . negate . negate :: Num a => a -> a

And here we see a different pattern, each composition doesn't change the type at all. Is this important?

Well, the type of foldl is

> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a

So the output type is entirely determined by the first argument. The type itself has nothing to do with what type the input list is or how many elements it has. More specifically

> :t foldl (.) id
foldl (.) id :: [a -> a] -> a -> a

And [a -> a] does not match the type of our of maps [(a -> b) -> [a] -> [b]]. In fact, since Haskell's type arrows are right associative, this means that the compiler is trying to line up the types as

[c        -> c           ]
[(a -> b) -> ([a] -> [b])]

So c ~ a -> b and c ~ [a] -> [b], so then (a -> b) ~ ([a] -> [b]) which implies a ~ [a] and b ~ [b]. This is the source of that compiler error.

---

Now you're probably asking the question "How do I accomplish this sort of thing in Haskell?" The answer might disappoint you, you don't usually. Types are very rigid, so there won't ever be an instance where you would have the option to pass in [Int] or [[Int]] or [[[Int]]] to a single function, it wouldn't compile. I don't know of a way around this off the top of my head, but as @Lee suggests the lens package (which I don't have much experience with) might be the answer. Lenses have very generalized types, so it's likely that there's one out there that can use Traversal to generalize this nicely to any level of nesting.