Sunday, November 8, 2015

Showing Map Distributes Over Functional Composition OR Fun With Clojure

"Here by the cheeks I'll drag thee up and down."
-- Shakespeare, Henry VI Part 1
Act I, Scene III, Line 51

I love to try things out for myself.  Whenever I am trying to understand idea I need to show myself that the idea is valid.  Sometimes I will just accept something, but if I really want to understand it I will show myself that it makes sense.

While rereading Dr. Hutton's paper "A tutorial on the universality and expressiveness of fold", I came back across the following statement, "the map operator distributes over function composition".  Being the kind of person which likes to show things to myself I figured I'd show myself this idea in Clojure as part of my daily kata.

Looking at the code above we see the following:

  • map f · map g = map (f · g)
  • r/map f · r/map g = r/map (f · g)
  • reduction f · reduction g = reduction (f · g)

So what does this give us?  Having this property we are allowed to improve the performance of our code by composing a series of transformation against a collection to a single transformation of the collection dragged through a series of composed functions.  In fact this is the whole idea behind streams.

Taken straight from Raoul-Gabriel Urma's article in Java Magazine, "[i]n a nutshell, collections are about data and streams are about computations."  Thinking about processing as a series of computation we see how we can naturally think about composing our computations together and then drag the data through using a higher order function like map to preform the series of transformations in one pass.