why can't I use iterate to repeatedly apply map?

Question

I've come to the realization that when I have nested data structures, I've been manually writing code to delve into them. Like this:

--one level
Prelude> map (*2) [1,2,3]
[2,4,6]

--nested two levels
Prelude> let t2 = map $ map (*2)
Prelude> t2 [[1,2,3],[4,5,6]]
[[2,4,6],[8,10,12]]

--nested three levels
Prelude> let t3 = map $ map $ map (*2)
Prelude> t3 [[ [1,2,3],[4,5,6] ],[ [1,2,3],[4,5,6] ]]
[[[2,4,6],[8,10,12]],[[2,4,6],[8,10,12]]]

so it occurs to me that I should be able to automatically construct a function for delving into my nested data structures using a higher order function:

Prelude> let t f n = (iterate map f) !! n

<interactive>:35:22:
    Occurs check: cannot construct the infinite type: b0 = [b0]
    Expected type: (a0 -> b0) -> a0 -> b0
      Actual type: (a0 -> b0) -> [a0] -> [b0]
    In the first argument of `iterate', namely `map'
    In the first argument of `(!!)', namely `(iterate map f)'

Its strikes me that

1. I understand its finding a list where it expected...something else
2. I don't know how to fix this - should I write code to do repeated application even though thats what I thought iterate was for?
3. This seems similar to the concept of "lifting" - but I don't know how to apply that intuition.

Answer 1

The problem is that these "iterations" have different types. For each iteration, you get an extra level of nesting, so you'd want

t f 0 :: a -> b
t f 1 :: [a] -> [b]
t f 2 :: [[a]] -> [[b]]

But iterate :: (a -> a) -> a -> [a] requires that the iterations all have the same type. In fact, a direct implementation of the above would require some form of dependent types since the return type depends on the value of n.

Unless you have a good reason not to, I suggest keeping it simple and just writing out the required number of map calls. It's possible to use Template Haskell to generate them, but this will likely be more trouble than it's worth.

However, if you have complicated nested data structures, you may want to look into SYB which can automatically take care of the boilerplate of applying such transformations in nested structures.

Here's a quick example:

> import Data.Generics
> let t x = everywhere (mkT (*2)) x
> :t t
t :: Data a => a -> a
> t [2,4,6]
[4,8,12]
> t [[2,4,6],[8,10,12]]
[[4,8,12],[16,20,24]]
> t (Just [(1, 2, 3), (4, 5, 6)])
Just [(2,4,6),(8,10,12)]

Answer 2

Think about the type of (iterate map f) !! n. You want it to be a -> a for n = 0, [a] -> [a] for n = 1, [[a]] -> [[a]] for n = 2 - in general, you want the type of this expression to depend on the value of n. But that is impossible to do in Haskell, since it's not a dependently-typed language.