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.

	(ns distributes-over-functional-composition-tests
	(require
	[clojure.test :refer [deftest testing are run-tests]]
	[clojure.core.reducers :as r]))
	(deftest map-distributes-over-functional-composition-tests
	(testing "map f · map g = map (f · g)"
	(are [coll]
	(are [f g] (=
	((comp (partial map f) (partial map g)) coll) ; map f · map g
	(map (comp f g) coll)) ; map (f · g)
	identity identity
	inc dec
	#(* % %) (partial * 2)
	(constantly 43) (constantly 42)
	zero? (partial mod 5))
	[1]
	[]
	[1 2 3 4]
	[-1 -2 -3 -4]
	[377 610 987]
	[17711 28657]
	[0.25 0.36 0.42 0.2]
	[1/2 1/3 1/4 1/5]
	[1 -1 2 -3 5 -8]
	[42.0 21.0 10.5 5.25 2.625 1.3125])))
	(deftest reducers-distributes-over-functional-composition-tests
	(testing "map f · map g = map (f · g)"
	(are [coll]
	(are [f g] (=
	((comp (partial map f) (partial map g)) coll) ; map f · map g
	(into [] ((comp (r/map f) (r/map g)) coll)) ; map f · map g
	(map (comp f g) coll)) ; map (f · g)
	identity identity
	inc dec
	#(* % %) (partial * 2)
	(constantly 43) (constantly 42)
	zero? (partial mod 5))
	[1]
	[]
	[1 2 3 4]
	[-1 -2 -3 -4]
	[377 610 987]
	[17711 28657]
	[0.25 0.36 0.42 0.2]
	[1/2 1/3 1/4 1/5]
	[1 -1 2 -3 5 -8]
	[42.0 21.0 10.5 5.25 2.625 1.3125]))
	(testing "reduction f · reduction g = reduction (f · g)"
	(are [coll]
	(are [f g]
	(are [reduct rreduct]
	(=
	((comp (partial reduct f) (partial reduct g)) coll) ; reduction f · reduction g
	(r/foldcat ((comp (rreduct f) (rreduct g)) coll))) ; reduction (f · g)
	take-while r/take-while
	remove r/remove
	filter r/filter
	)
	(constantly true) (constantly true)
	(constantly true) (constantly false)
	(constantly false) (constantly false)
	(constantly false) (constantly true)
	(partial > 2) pos?
	neg? (partial < 1/2)
	)
	[1]
	[]
	[1 2 3 4]
	[-1 -2 -3 -4]
	[377 610 987]
	[17711 28657]
	[0.25 0.36 0.42 0.2]
	[1/2 1/3 1/4 1/5]
	[1 -1 2 -3 5 -8]
	[42.0 21.0 10.5 5.25 2.625 1.3125]))
	)
	(run-tests)

view raw distributes_over_functional_composition_tests.clj hosted with ❤ by GitHub

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.