The *Aufgabenstellung* quite clearly suggests that code from the other homework exercises can be reused. And indeed, one finds that:

index0 xs n = (n, n+1) index1 = foldlMap index0 index2 = foldlMap index1 … …

Now, to quote the MC himself:

If you find yourself copy-pasting code, you must be doing something wrong. Copy-paste occurs when you notice some similarity and exploit it. But there are almost always better ways of exploiting the similarity.

So how can we exploit this similarity? Well, one way would be to write lots of auxiliary functions and stack function composition in such a way that we get an exponential nesting depth; as far as I know, one can get to a depth of 1728 with ≤60 tokens with this approach. But we ought not be satisfied with a mere 1728 levels of nesting. The structure is quite simple, is it not? We know how to write `index0` and given `indexn`, we know how to write `index(n+1)`, so to speak. Why not let the compiler figure out how to index a list of a certain type?

To this end, I have a quote of my own, which I call the Rule 34 of Haskell:

No matter what your problem is, there is a GHC language extension to solve it.

In this case, a fairly modest number of two extensions suffices, namely *MultiParamTypeClasses* and *FlexibleInstances*. There are a lot of these extensions and each of them makes Haskell (usually Haskell's type system) more powerful. However, with great power comes great responsibility: each of them can impede type inference and some even make type checking undecidable. More experienced Haskell type hackers, like Lars Hupel, have been known to lead GHC to produce the error message My brain just exploded

.

But I digress. So how can we solve our little problem with MultiParamTypeClasses and FlexibleInstances? Let me show you. First of all, we declare a type class `Index` with parameters i and o.

class Index i o where index :: i -> Int -> (o, Int)

You can think of that as a predicate on pairs of types; `Index i o` means “There exists an indexing function with input type `i` and output type `o`”. Next, we have to tell Haskell for which types `i` and `o` this predicate holds. This is done in an inductive way: one simply declares instances for certain types, and the “predicate” holds for exactly those types for which an instance can be derived. Well, we can index any type with a single Integer (this corresponds to `index0`):

instance Index a Int where index _ n = (n, n+1)

Also, in order to index a [i], we can simply apply foldlMap on the function that indexes i, so we write:

instance Index i o => Index [i] [o] where index = foldlMap index

This means that if we have an index function for input type `i` and output type `o`, we also have one for input type `[i]` and output type `[o]`. If the `=>` reminds you of a logical implication, that is not a coincidence – that is exactly what it is. `Index i o` implies `Index [i] [o]` for all types `i`, `o`.

So what is the type of `index`? Let's ask GHCI:

index :: Index i o => i -> Int -> (o, Int)

Aha. So for any types `i`, `o` that satisfy `Index i o`, index has the type `i -> Int -> (o, Int)`. Great, let's apply it to an example!

> index ["pelle", "foretag", "se"] 0 No instance for (Index [[Char]] o0) arising from a use of `index' The type variable `o0' is ambiguous

Huh. So what is the problem here? GHC finds from the context that `index` must have the type `[String] -> Int -> (o, Int)` with `Index [String] o`. It also finds that it has type class instances for `Index [String] Int` and for `Index [String] [Int]`, depending on which of the two instance declarations it uses first. So which one should it use?
Well, luckily, GHCI also tells how to solve the problem: *Possible fix: add a type signature that fixes these type variable(s)*

> index ["pelle", "foretag", "se"] 0 :: (Int, Int) (0,1) > index ["pelle", "foretag", "se"] 0 :: ([Int], Int) ([0,1,2],3) > index ["pelle", "foretag", "se"] 0 :: ([[Int]], Int) ([[0,1,2,3,4],[5,6,7,8,9,10,11],[12,13]],14)

If the last one surprised you, remember that `String = [Char]`. We really do need to annotate the result type, because otherwise, Haskell really could not possibly know what it is that we want.

To wrap up, in order to satisfy the *Aufgabenstellung*, we can now write a specific indexn function like this:

index2 :: [[a]] -> Int -> ([[Int]], Int) index2 = index

Et voilà, a generic solution for our problem for arbitrarily high nesting depths in 52 tokens.