"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.
Sunday, October 18, 2015
Sunday, October 11, 2015
Folding Up the Coin Changer Kata
"Whate'er the course, the end is the renown."
-- Shakespeare, All's Well That Ends Well
Act IV Scene IV, Line 36
The Coin Changer kata has three things which make it a good kata.
The user story is very simple:
Given a collection of coins of different denominational value
When an amount of change is given
Then it will give back the number of coins for each denomination needed using the least amount of coins possible
A type signature for the function needed could look like the following:
changeFor(coins: int[], amount: int): int[]
We are expecting an array of integers which have different denomination of coins (in the US something like: [25, 10, 5, 1]) and the amount of change needed (something like: 99) giving a resulting array of integers showing how many of each denomination (something like: [3, 2, 0, 4]).
What would we need to be able to do this kata using just Fold?
We'll need to use a tuple (or something like one) to manage the state of the amount of change needed and the resulting array of integers.
Now lets look at an example using a typical full US register with quarters, dimes, nickels, and pennies. We'll look at getting change for 99 cents.
First Memorize has (99, empty) and X has 25 giving the result of (24, [3]).
Next Memorize has (24, [3]) and X has 10 giving the result of (4, [3, 2]).
Then Memorize has (4, [3, 2]) and X has 5 giving the result of (4, [3, 2, 0]).
Last Memorize has (4, [3, 2, 0]) and X has 1 giving the result of (0, [3, 2, 0, 4]).
Finally obtaining the tuple item with the resulting array of integers to get the change.
We see with the Clojure code that we seed with a map with a key for the :amount and one for the :result. We fold over the coins using reduce destructing the memoize value into the amount and result. We then just calculate the new amount using: amount % coin, follow by inserting the number of coins we get using: amount / coin. We use cons to show off the coolness that is the thread-last macro (at least that is why I think I coded it this way, it was a little bit ago that I did the gist and I cannot remember why I code with cons over conj).
We see with the C# code that we seed using a Tuple (which I think has very ugly syntax in C#). We then fold over the coins using aggregate just like the Clojure code above. We calculate the changer results and place them into a new Tuple which we return as the memoize.
In this ECAMScript 2015 example we use lodash's foldl to fold over the coins just like the two examples above. The seed value is a simple JavaScript object with the members of amount and result given. We are a bit dirty and mutate the memoize on each call with the changer results but we could argue that this is still "pure" since the mutation happens to an item which is created and used only in side the function.
Last we look at Facebook's open source Immutable.js. We create an immutable List with the coins which we use to fold over the values using reduce. The seed value we give it is a simple JavaScript array with an immutable List to hold the results and the amount passed in. We could use an immutable Map if we wanted to keep it purely immutable. Like this:
I am not a huge fan of stringly typed accessors, but I understand why they use them. Both ways are good and would really come down to to performance and readability.
Thus ends our tour of All You Need is Fold, but this is not the end of the uses of Fold, for Fold is universal.
-- Shakespeare, All's Well That Ends Well
Act IV Scene IV, Line 36
Coin Changer Kata
The Coin Changer kata has three things which make it a good kata.
- easy to understand
- rich set of features
- lots of realistic possible implementations
The user story is very simple:
Given a collection of coins of different denominational value
When an amount of change is given
Then it will give back the number of coins for each denomination needed using the least amount of coins possible
A type signature for the function needed could look like the following:
changeFor(coins: int[], amount: int): int[]
We are expecting an array of integers which have different denomination of coins (in the US something like: [25, 10, 5, 1]) and the amount of change needed (something like: 99) giving a resulting array of integers showing how many of each denomination (something like: [3, 2, 0, 4]).
What would we need to be able to do this kata using just Fold?
We'll need to use a tuple (or something like one) to manage the state of the amount of change needed and the resulting array of integers.
Now lets look at an example using a typical full US register with quarters, dimes, nickels, and pennies. We'll look at getting change for 99 cents.
First Memorize has (99, empty) and X has 25 giving the result of (24, [3]).
Next Memorize has (24, [3]) and X has 10 giving the result of (4, [3, 2]).
Then Memorize has (4, [3, 2]) and X has 5 giving the result of (4, [3, 2, 0]).
Last Memorize has (4, [3, 2, 0]) and X has 1 giving the result of (0, [3, 2, 0, 4]).
Finally obtaining the tuple item with the resulting array of integers to get the change.
Clojure
We see with the Clojure code that we seed with a map with a key for the :amount and one for the :result. We fold over the coins using reduce destructing the memoize value into the amount and result. We then just calculate the new amount using: amount % coin, follow by inserting the number of coins we get using: amount / coin. We use cons to show off the coolness that is the thread-last macro (at least that is why I think I coded it this way, it was a little bit ago that I did the gist and I cannot remember why I code with cons over conj).
C#
We see with the C# code that we seed using a Tuple (which I think has very ugly syntax in C#). We then fold over the coins using aggregate just like the Clojure code above. We calculate the changer results and place them into a new Tuple which we return as the memoize.
ECMAScript 2015
In this ECAMScript 2015 example we use lodash's foldl to fold over the coins just like the two examples above. The seed value is a simple JavaScript object with the members of amount and result given. We are a bit dirty and mutate the memoize on each call with the changer results but we could argue that this is still "pure" since the mutation happens to an item which is created and used only in side the function.
ECMAScript 2015 and Immutable.js
Last we look at Facebook's open source Immutable.js. We create an immutable List with the coins which we use to fold over the values using reduce. The seed value we give it is a simple JavaScript array with an immutable List to hold the results and the amount passed in. We could use an immutable Map if we wanted to keep it purely immutable. Like this:
I am not a huge fan of stringly typed accessors, but I understand why they use them. Both ways are good and would really come down to to performance and readability.
The End
Thus ends our tour of All You Need is Fold, but this is not the end of the uses of Fold, for Fold is universal.
Sunday, October 4, 2015
Fold the Zip Up
"They fell together all, as by consent."
-- Shakespeare, The Tempest
Act II, Scene I, Line 207
Zip can be thought of as the more generic form of Map. Think of Zip as applying a function against each member of the collections given to it, thus mapping more than one collection to another collection. It is a lot easier to see than to explain in words.
I believe Zip2 would get the following definition:
zip2 :: (α → β → γ) → ([α] → [β] → [γ])
zip2 f = fold (λx y xs ys → f x y : xs ys) [ ]
This would be if we limit Zip to being used on 2 collections (this is mine definition, Dr. Graham Hutton has nothing to do with this definition, blame me if it is wrong).
Folding a Zip we'll need a collection to seed with then we just apply the given function against each member from each collection concatenating it with the seed, just as we did with Map.
Next we'll look at a simple example adding the members of two collections together.
First Memoize has nothing and X has 1 while Y has 10 giving the result of 11.
Next Memoize has 11 and X has 2 while Y has 20 giving the result of 11, 22.
Lets see some code examples.
With Clojure we do not have to worry about the number of collection we'll give our Zip function since we can use destructing to say and everything else. We can then apply map to create a vector containing all the elements next to each other, we'll see this is common in the other languages since the implementation of reduce is only design to work with a single collection. From here it is just like Map except that we need to use apply since are members are a collection themselves.
With C# we have to specify the number of collection we are going to Zip, in this case we'll do two. We need to Zip the members from the two collections together into a Tuple (which is a bit of cheating but I can find no other way to do it with LINQ). From there it is just like Map. With this implementation we do have a limitation in that the two collections must be the same size, since to get around that would be a bit of work and we rather have a readable implementation than perfect code.
In ECMAScript 2015 (also known as JavaScript ES6), we see an implementation similar to the C# code except we use lodash's zip to place the members in a single collection (lodash's zipWith is like LINQ's Zip). From there it is just like Map. With this implementation like the C# implementation we have a limitation in that the two collections must be the same size, and again the work around would be a lot of work so we'll error on keeping the code readable.
There you have it showing once again that all you need is Zip.
-- Shakespeare, The Tempest
Act II, Scene I, Line 207
Zip
Zip can be thought of as the more generic form of Map. Think of Zip as applying a function against each member of the collections given to it, thus mapping more than one collection to another collection. It is a lot easier to see than to explain in words.
I believe Zip2 would get the following definition:
zip2 :: (α → β → γ) → ([α] → [β] → [γ])
zip2 f = fold (λx y xs ys → f x y : xs ys) [ ]
This would be if we limit Zip to being used on 2 collections (this is mine definition, Dr. Graham Hutton has nothing to do with this definition, blame me if it is wrong).
Folding a Zip we'll need a collection to seed with then we just apply the given function against each member from each collection concatenating it with the seed, just as we did with Map.
Next we'll look at a simple example adding the members of two collections together.
First Memoize has nothing and X has 1 while Y has 10 giving the result of 11.
Next Memoize has 11 and X has 2 while Y has 20 giving the result of 11, 22.
Lets see some code examples.
Clojure
With Clojure we do not have to worry about the number of collection we'll give our Zip function since we can use destructing to say and everything else. We can then apply map to create a vector containing all the elements next to each other, we'll see this is common in the other languages since the implementation of reduce is only design to work with a single collection. From here it is just like Map except that we need to use apply since are members are a collection themselves.
C#
With C# we have to specify the number of collection we are going to Zip, in this case we'll do two. We need to Zip the members from the two collections together into a Tuple (which is a bit of cheating but I can find no other way to do it with LINQ). From there it is just like Map. With this implementation we do have a limitation in that the two collections must be the same size, since to get around that would be a bit of work and we rather have a readable implementation than perfect code.
ECMAScript 2015
In ECMAScript 2015 (also known as JavaScript ES6), we see an implementation similar to the C# code except we use lodash's zip to place the members in a single collection (lodash's zipWith is like LINQ's Zip). From there it is just like Map. With this implementation like the C# implementation we have a limitation in that the two collections must be the same size, and again the work around would be a lot of work so we'll error on keeping the code readable.
Done
There you have it showing once again that all you need is Zip.
Subscribe to:
Posts (Atom)