The Non–functional in a Functional world?

This post shows an implementation of map/reduce in Haskell. It's a one–liner (if you ignore all the other lines) and begins with this claim:
the type says it all

p_map_reduce :: ([a] -> b) -> (b -> b -> b) -> [a] -> b

The type says a lot, that's for sure. I says that map/reduce results in a value of type b when given a list of values of type a, a function that gives one b given two b's and a function that gives one b given a list of a's. That is a lot of information and it's impressive that it (at least) can be stated on one line. Is it "all", though?

Even allowing for some inter–tubes posting hyperbole "all" is a very strong claim. A Haskell programmer should know that. If one already knows what map/reduce does then the type tells you a lot about how to use this implementation of it. And if you don't, maybe not so much.

But that's not what caught my attention. The point of map/reduce is to recruit large pools of computational resource to operate on very large data sets efficiently. The (14 line, in fact—which is still quite impressive) implementation uses Haskell's Control.Parallel features to chop the list of a's into 16 chunks. That's not in the type. The intention is to have enough lumps of work to 
bump all your cores to 100% usage, and linearly increase overall performance
which it may well do on a large enough data set, if I have fewer than seventeen cores. Currently, I do. There are nine cores in my flat right now. If my other laptop were here, it'd be eleven. But if I'm planning to use map/reduce in the first place, maybe I'm going to recruit all the machines in the office, which would currently be worth over twenty cores. This map/reduce isn't going to pin all of them.

Would Haskell's type system support giving p-map-reduce a dependent type with the number of worker processes in it? I don't know enough about it to tell. And why would we care? Well, that number 16 is a very significant part of the implementation of that function. 

The only reason we'd bother to use map/reduce is because of its non–functional characteristics (as the properties of software that make it actually useful are called) and these are no–where to be seen in its type as a function. 

No comments: