## Wednesday, August 5, 2009

### How would you map a map?

This occurred to me today. Imagine we have a list of things.

```list = [1, 2, 3, 4]
```

Given that we have a mutation function "fn", how do we change all of the elements in the list with that function?

If we're just using idiomatic procedural code, we'd use a loop, but since we're fancy smarty pants, we're gonna use higher order functions. Like so:

`map(list, fn)`

Then the function could have the following arbitrary mutation algorithm:

`function fn(x) {return x * x}`

Nothing exciting so far.

But the data structure I want isn't a list. It's a map. You know, a list of key-value pairs. How do I map that?

My previous function no longer works because I need to be able to work on the key, as well as the value. The problem is that I can only return one thing. What do I return? The value? The key? A pair?

`function fn(k, v) {return [k, v]} //two inputs, infinite output arity`

Well, we'd have to follow some sort of convention to get around that infinite arity problem. Even in Java, we could potentially pass a null instead of an Entry and then you'd get a null ref exception inside the map function. Not very nice.

Would it be ok to just give up and throw an error? Hmm. Maybe. If there's no other option, I guess that'd be ok.

Oh, I know, what if we had two mapping functions?

`map(myMap, keyFn, valueFn)`

Then I can guarantee that I'll get reasonable arities.

```function keyFn(k, v) {return k * k + v * v} //one input, one output
function valueFn(k, v) {return k / v} //one input, one output
```

Is it mathematically possible to have logic that cannot be split into two functions? I'm thinking if we start introducing closures and side effects, things would probably get weird, but I can't really picture how. Can anyone think of a way where this API would fail spectacularly?