I’m still earring a colleague of mine saying: “all the human problems are solvable with an Object Oriented approach.” I didn’t argue a long time with her. She maybe never had to think about other kind of problems, problems that require to break that paradigm apart.
Google offers an interesting introduction to the Map/Reduce paradigm. Map/Reduce is a way to distribute
operations on datas (map) on several computers and then
to aggregate the outputs to get the result (reduce).
I made the warm up sheet using Functional JavaScript on SpiderMonkey because my Haskell skills are still bad.
First, set it up, make sure functional.js is in the same directory:
$ js > var window = this > load(['functional.js']) > Functional.install()
Before Functional JavaScript is built for web browser, you have to set window
to the context (loading will fail instead). Then here we go with the first
exercise: concat([[1,2],[3,4,5],[6]]) → [1,2,3,4,5,6].
function concat(list){
return foldl("x.concat(y)", [], list)
}
Next one is a group by key, or an object merger: group([{'a':0},{'b':1},{'a':2}]) → {'a':[0,2],'b':[1]}.
function group(list){
return foldl(function(x,y){
for(var key in y)
if (typeof x[key] === "undefined")
x[key] = [y[key]];
else
x[key].push(y[key]);
return x
}, {}, list)
}
the for loop is the only way to discover the keys of an object,
so don’t tweak Object.prototype. Next one a way to split a
list with an arbitrate key: foldk([1,2,3,4], 3) → [[1,2],[3,4]]
function foldk(list, k){
return foldl(function(x,y){
x[y>=k?1:0].push(y);
return x
}, [[],[]], list)
}
And the next one, more trivial about composing two functions.
function compose(f, g) {
return function() {
return f(g.apply(this, arguments))
}
}
NB: there are maybe better solution. I would be thankful to ear them from you.
If all this looks pointless, some people are already thinking about using JSON for Map/Reduce (JSON is JavaScript) which is all about building applications like CouchDB that works this way.
Last but not least, two posts on Raganwald about doing the same things in Ruby (1.9) that Functional Programming in JavaScript able you to. update: find the source code here.
Il n’est pas simple de sortir de toutes les choses qu’on a pu nous enseigner comme étant la ou les manières de faire, de penser. Dans une école d’ingénieur où la programmation orientée-objet a été ensensée, à coup de Java, de C++ et d’UML, je me souviens de la peine qu’avaient certains professeurs à, ne serait-ce que, faire prendre conscience de l’existance d’autres univers comme Prolog, Lisp, XSLT, ou voire même SQL. Et qui sont au combien importants.
Une collègue me disait que la programmation orientée-objet était la manière dont on pensait tous, qu’elle était la solution aux problèmes courants. À part lui dire qu’elle avait bien retenu sa leçon, il a été difficile d’avoir une discussion constructive malheureusement.
Une classe de problèmes pouvant être applicable au modèle distribué comme
un moteur de recherche, du calcul (type seti@home) sortent
clairement de ce paradigme là en se servant du Map/Reduce utilisé
(défini?) par Google. En entrée une liste de données sur laquel va être appliqué
une fonction pour chaque élément (map) puis reduite dans le but
d’obtenir un résultat (reduce). Voir également Hadoop.
Un cours d’introduction à Map/Reduce offre des excercices pour ce familiariser avec ces principes là. Étant prévu pour Haskell et n’ayant que peu d’expérience avec le bestiau, j’ai choisi d’utiliser Functional JavaScript et SpiderMonkey, bref du JavaScript. (voir la partie anglaise)
Map/Reduce et JavaScript est un couple qui risque de voir le jour, ou existe déjà au sein de CouchDB. Donc il n’y a pas là d’alliance contre nature.
Et enfin, derrière les fonctions obscures fournies par Functional Javascript, le langage Ruby (version 1.9) devrait se voir gratifié d’outils similaires (code source). Il est difficile de faire du fonctionnel pur, mais le jeu en vaut la chandelle je pense pour gagner en solidité (pas d’effet de bord), lisibilité, montée en charge.
