By `n-depth structure`

I mean some structure that nests one kind of structure `n`

times, for example `[[a]]`

is a 2-depth list.

I was randomly thinking about an instance of `Functor`

, `Foldable`

and `Traversable`

for a 3-depth list (`[[[a]]]`

) today, and found some regularity as you can see below:

```
instance Functor [[[]]] where
fmap f n = fmap (fmap (fmap f)) n
instance Foldable [[[]]] where
foldMap f n = foldMap (foldMap (foldMap f)) n
instance Traversable [[[]]] where
sequenceA n =
let fz = \z -> sequenceA z
fy = \y -> sequenceA (fmap fz y)
fx = \x -> sequenceA (fmap fy x)
in fx n
```

I think this can be automated typesafely in some way, not only for `[]`

but any structures that have these instances (like `Vector`

), and not only 3-depth but any depths as long as it's more than zero.

I think something like `data Depth = One | Succ Depth`

will be used for compile-time depth calculation, but beyond that, I have no idea how it goes. Do you think this is actually possible? How would you implement it?

# Best How To :

The other answers are quite nice in that they present a single (parameterized) data type that can handle structures of any depth; however, they use advanced type system features to achieve this. On the other hand, there are quite simple features that can be used instead to achieve the same thing, and with greater flexibility. The basic idea is to define functor composition once and for all:

```
newtype Compose f g a = Compose { getComposition :: f (g a) }
instance (Functor f, Functor g) => Functor (Compose f g) where
fmap f (Compose v) = Compose (fmap (fmap f) v)
```

One can similarly define instances for `Foldable`

and `Traversable`

with no extensions. Then you get one-fold, two-fold, and three-fold nesting as, e.g.

```
type DepthOneList = []
type DepthTwoList = Compose [] [] -- = Compose [] DepthOneList
type DepthThreeList = Compose [] (Compose [] []) -- = Compose [] DepthTwoList
```

and these have the requisite `Functor`

, `Foldable`

, and `Traversable`

operations. Moreover, you have great flexibility here; you need not have the same functor at every depth but could have for example

```
type Mixed = Compose [] (Compose Vector [])
```

with no problem. If it is really needed, one can happily unroll type-level nats into this more structured type-level object (though of course this requires similar extensions to the ones used in other answers):

```
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DataKinds #-}
data Nat = Z | S Nat
type family IterCompose (n :: Nat) (f :: * -> *) :: * -> * where
IterCompose Z f = Identity
IterCompose (S n) f = Compose f (IterCompose n f)
```

But this type-level translation is, in most cases, less flexible, less usable, and less readable than just writing the composed type by hand, so I would consider this part the "uninteresting" part in some sense.

A pre-implemented functor composition operation is available from Hackage in the TypeCompose package and, perhaps more canonically, in transformers.