"So, geophf," I was asked during a recent interview for a software quality-assurance tester job, "have you heard of the product map-reduce?"
"Well," sez I, "no, but I'm familiar with the concept from functional programming."
That was a good enough answer for me.
The test manager had heard of functional programming and (from me) category theory. I was talking with Ph.D.s who were test managers.
A refreshing conversation, actually.
"Yes," he said, "but what is all this stuff good for?"
I gave him a "you've got to be kidding me" look.
What is category theory good for? Coming on the heels of have I heard of map-reduce?
Like where did the concept of map-reduce come from?
So, here's what it's good for.
The Joke
An infinite number of mathematicians walk into a bar. The first math dude sez, "Bartender, I'll have half-a-beer." The next one sez, "I'll have half what he's having." Then next: "I'll have half of hers." And the next one goes to speak.
And they want to get in this specification, because that's how mathematicians roll, but the bartender holds up his hands.
"Ladies and gentlemen," he says, "know your limits, please!"
And pours out one beer which the infinite number of mathematicians enjoy.
The proof in the pudding
let nat = [1..]
let halflings = map (\x → 1 / 2 ** x) nat
let onebeer = sum halflings
onebeer
Now, that may take some time to return (geophf cackles evilly at his phrasing of 'some time'), but we've just used map-reduce. How? map we used directly above in halflings, as you see, and reduce (a.k.a. the fold function) is embedded in the definition of sum:
let sum :: Num a ↠ [a] → a = foldl (+) 0
So, if we look at the the above we just used map-reduce to solve the beering-mathematicians problem (as opposed to solving the dining philosophers problem, because, anyway, those philosophers really should go on a diet. Just sayin').
Piece of cake, right?
Well, not really. Our solution, to use a technical term, sucks.
Let's look at it. What does our set of equations reduce to? The reduce to this one formula:
let onebeer = sum (map (\x → 1 / 2 ** x) [1..])
What's wrong with this?
Well, for any n, where n is the length of the set of natural numbers, we have a least a double-linear complexity to solve this problem.
But let's look at the sequence we create by unwinding the problem.
First we have [1,2,3,4, ...]
Then we have [1/2, 1/4, 1/8, 1/16, ...]
Then we have [1/2 (+ 0), 1/4 + 1/2, 1/8 + 3/4, 1/16 + 7/8, ...]
Huh. What's interesting about this pattern?
Story time
Once upon a time, there was a bad little boy in maths class, named Gauss, and he was held after school. The teacher told him he could go home after he summed the first 100 'numbers' (positive integers, I believe the teacher meant).
Gauss left for home after writing the solution down in less than one second.
The teacher was furious, believing that Gauss had cheated.
He didn't. He just noticed a pattern.
1 = 1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
sum [1..n] = ... what?
Well, what does it equal?
When n = 1, sum [1..1] = n
when n = 2, sum [1..2] = n + 1
when n = 3, sum [1..3] = n * 2
when n = 4, sum [1..4] = ... hm, well, it equals ... what?
It equals n (n + 1) / 2, doesn't it.
n = 100, sum [1..100] = 100 * 101 / 2 = 5,050
... and Gauss was done. He went home, serving the shortest detention ever, and put egg on his prof's face, too.
Good times. Good times.
Well, what about this problem?
We can map and sum all we want, but can't we do what Gauss did and reduce the double-linear (at least) problem complexity down to some constant on the number n?
Yes, we can.
The pattern is this, after we've done our reduction to the simplest forms:
[1/2, 3/4, 7/8, 15/16, ... blah-blah-blah, boring-boring-boring]
Who needs map-reduce when we just simply return
limn (1 - 1 / 2n)
for any n even as n approaches infinity?
Who, indeed.
The take-away? Yes, I could have used map and reduce and exponentiation and all that to get to the answer, but sometimes we just have to take a step back from trying to solve a problem and just observe what we're solving.
"Hey," algorist exclaims, "I'm just solving to get this simple fraction! I don't have to map-sum anything!"
It's amazing what meta-problem-solving saves us as we go about solving problems, isn't it?
Epilogue
Oh, map is reduce, did you know that?
Specifically, for every function f, there is a reduce function that is isomorphic to map f.
What is it?
No comments:
Post a Comment