"Back to our brother of England."
-- Shakespeare, Henry V
Act II, Scene IV, Line 115.1
One of the things I love about functional programming is you can tell a lot about how a function works by just looking at its type signature. In F# 4.0 there is a new function to work with collections, here is it type signature:
('State -> 'T -> 'U * 'State) -> 'State -> C<'T> -> C<'U> * 'State
What do you think it does?
That's right this is a MapFold. Looking at its full definition we see the following:
let mapFold<'T,'State,'Result>
(f:'State -> 'T -> 'Result * 'State) acc list =
How does this work?
Looking at F#'s unit tests we see the following test name:
let ``mapFold works like map + fold`` () =
MapFold works like a map with a fold to maintain state. I know what you are thinking maintaining state is bad, that's why functional programming is easier to reason about. This is very true, but this is not a mutable state, this is an evolving state.
Let us look at an example, the Coin Changer kata:
The Coin Changer kata simulates one of those machines which give you back coins at a store. It takes a list of coin values and the amount of change to be given.
The Coin Changer kata is interesting since it has two things going on at the same time: 1) state and 2) list processing. In the Coin Changer kata you must maintain the amount of change you have left to give along with the amount of each coin to be given back. An example would be 99 cents with an US register, you would get back 3 quarters, 2 dimes, 0 nickels, and 4 pennies.
How would this example of 99 cents with an US register work with MapFold?
changeFor [25; 10; 5; 1] 99
We'll use s to hold the state, r to hold the result, and x to hold the current coin value we are looking at .
Processing the first value: x = 25, s = 99, r = [] resulting in s = 24, r = [3]
Second value: x = 10, s = 24, r = [3] resulting in s = 4, r = [3; 2]
Third: x = 5, s = 4, r = [3; 2] resulting in s = 4, r = [3; 2; 0]
Last: x = 1, s = 4, r = [3; 2; 0] resulting in s = 0, r = [3; 2; 0; 4]
There you have it, step-by-step through the Coin Changer kata using MapFold.
Guess what the source code to MapFold looks for the most part like what we just experienced. Here it is:
We see that it loops through each member of the collection, applying the function given against the state and current member. Once there are no more members it returns a tuple of the result along with the state. For the Coin Changer kata we do not care about the state (maybe we could use it verify that we have 0 cents) so we just drop it and get the result using fst.
There you have it the Coin Changer kata and MapFold seem to be made for each other.
