"If I break time, or flinch in property"
-- Shakespeare, All's Well That Ends Well
Act II, Scene I, Line 187
In Dr. Hutton's excellent paper, "A tutorial on the universality and expressiveness of fold", he gives the following definition of the fusion property of Fold:
h · fold g w = fold f v
Great, but what does this mean to me? Well if we go on in the paper we find the following application of the fusion property of Fold:
(+1) · sum = fold (+) 1
Interesting, we see that adding 1 to the sum (defined as, fold (+) 0) of a collection is the same as folding over that collection with 1 as the seed value. Further down in the paper we see that we can simplify and generalize the application above as:
(⊕ a) · fold (⊕) b = fold (⊕) (b ⊕ a)
Now this is really cool. We can apply an associative binary operation with a value against the results of folding that operation against a collection is the same as applying that binary operation with a value against the seed.
As an aside, an associative binary operation is an operation which takes two values from the same type and outputs a value of that type, examples would be +, -, *, /, min, max, ... We say an operation is associative if and only if:
a ⊕ b = b ⊕ a
This means addition is associative while subtraction is not (2 - 1 != 1 - 2, but 2 + 1 = 1 + 2).
How about looking at some examples of the fusion property?
First we'll look at examples in Clojure.
We see in the Clojure example that we are using reduce to fold over a collection of integers (integers are easier to use in examples but this idea is not limited to integers) applying an associative binary operation against each member. We see that applying the operation with a value against the result is the same as applying that operation and value against the seed.
Next we'll look at examples in ECMAScript 2015 (JavaScript) using Immutable.js.
We see in the ECMAScript example that we are using Immutable's reduce to fold over a List of integers (again this could be applied against any type) applying the associative binary operation against the members. Like the Clojure example we see that applying the operation with a value against the result is the same as applying that operation and value against the seed.
We can go further with this idea but I feel this is a good overview of the concept.
