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?

No comments:

Post a Comment