"What curious eye doth quote deformities?"
-- Shakespeare, Romeo and Juliet
Act I, Scene IV, Line 31
I've started using Unquote for my assertions with F# xUnit tests. I find that its step-by-step failure messages really help in figuring out what is going on.
One thing that really throw me when I first used it was the System.MissingMethodException exception that Unquote was throwing at runtime. Luckily I was able to find this StackOverflow answer. It seems that you need to do a binding redirect for FSharp.Core, so you'll need to set up an App.config file in your test project like this example of the Coin Changer kata (using MapFold).
Happy coding.
Showing posts with label coin_changer. Show all posts
Showing posts with label coin_changer. Show all posts
Sunday, February 21, 2016
Monday, January 18, 2016
MapFold OR Set Phasers to Fun
"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.
-- 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.
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.
Saturday, May 10, 2014
The Form of Katas
"Your honour with your form."
-- Shakespeare, Coriolanus
Act II, Scene 2, Line 142.1
Every work day around 6:30 AM you'll find me working on a Code Kata. I find that this is one of my most inventive times of the day. While doing my Code Kata I try out everything and anything. I am truly free doing my Code Kata, I even allow myself to fail.
Around 6:55 AM my kata be it is good, bad, or some where in between comes to an end. I get up and go make some coffee to start my work day. (In case you are wondering, my kata takes place out side of my normal 8+ hour work day. I write this since it has come up in talking with people at conferences about katas.)
Why do I do my Code Kata? I have lots of reasons, but the main ones are the following:
1) I do a Code Kata everyday to get better.
2) I do a Code Kata everyday to try out new things.
I wrote about these in more details in an earlier post called "A Kata a Day".
A Code Kata is simply, focus programming for the joy of programming. Focus because you are working on getting better. Joyous because you want to have fun doing it. (Pro tip, if you do not like programming than why bother doing it?) That is all.
I typical choose from a few simple katas that I know rather well. I do this because I do not want the problem domain to get in the way of what I am focusing on. What does this mean? If I want to try out a new JavaScript framework then I do not want the problem domain of my kata to get in the way of learning how to use the framework.
The FizzBuzz kata is a very simple exercise yet has enough to it to be usable to vet candidates at an interview (we use this where I work to vet our candidates).
Check out this slideshare from the most recent meeting of the Lake County .Net Users Group. (Yeah I know I am a Co-Leader of said group and that link is to my Slideshare! If I do not promote myself than who will?)
Here is a solution using C# with LINQ.
I first saw the Coin Changer kata at SCNA in a battle kata. This is a great kata since you get to work with a collection of data.
This kata has a lot of interesting edge cases to it. Like the following edge case, what should you do if you have only dimes and nickels but need to make change for 36 cents?
Again, check out this slideshare.
Here is a solution using C# with LINQ.
Looking for new ideas for your next kata? Check out the following:
Happy coding.
-- Shakespeare, Coriolanus
Act II, Scene 2, Line 142.1
Intro
Every work day around 6:30 AM you'll find me working on a Code Kata. I find that this is one of my most inventive times of the day. While doing my Code Kata I try out everything and anything. I am truly free doing my Code Kata, I even allow myself to fail.
Around 6:55 AM my kata be it is good, bad, or some where in between comes to an end. I get up and go make some coffee to start my work day. (In case you are wondering, my kata takes place out side of my normal 8+ hour work day. I write this since it has come up in talking with people at conferences about katas.)
Why do I do my Code Kata? I have lots of reasons, but the main ones are the following:
1) I do a Code Kata everyday to get better.
2) I do a Code Kata everyday to try out new things.
I wrote about these in more details in an earlier post called "A Kata a Day".
What is a Code Kata
A Code Kata is simply, focus programming for the joy of programming. Focus because you are working on getting better. Joyous because you want to have fun doing it. (Pro tip, if you do not like programming than why bother doing it?) That is all.
I typical choose from a few simple katas that I know rather well. I do this because I do not want the problem domain to get in the way of what I am focusing on. What does this mean? If I want to try out a new JavaScript framework then I do not want the problem domain of my kata to get in the way of learning how to use the framework.
FizzBuzz
The FizzBuzz kata is a very simple exercise yet has enough to it to be usable to vet candidates at an interview (we use this where I work to vet our candidates).
Examples
FizzBuzz(2) -> “2”
FizzBuzz(3) -> “Fizz”
FizzBuzz(5) -> “Buzz”
FizzBuzz(15) -> “FizzBuzz”
Rules
- If value is divisible by 3 then Fizz
- If value is divisible by 5 then Buzz
- If neither then give value as string
As you see you have one edge case with values which are divisible by both 3 and 5. In fact one such edge case is the value 0 which cause issues in some languages like JavaScript in which 0 is a special value. The great thing about FizzBuzz is that you can use it to try out new ideas like creating a RESTful FizzBuzz API. Yep, FizzBuzz as a service!
Check out this slideshare from the most recent meeting of the Lake County .Net Users Group. (Yeah I know I am a Co-Leader of said group and that link is to my Slideshare! If I do not promote myself than who will?)
A Solution
Here is a solution using C# with LINQ.
Coin Changer
I first saw the Coin Changer kata at SCNA in a battle kata. This is a great kata since you get to work with a collection of data.
Example
Changer.coins = [pennies]
Changer.for(3) -> [3]
Changer.for(3) -> [3]
Changer.coins = [dimes, nickels, pennies]
Changer.for(17) -> [1, 1, 2]
Changer.for(17) -> [1, 1, 2]
Changer.coins = [quarters, dimes, nickels, pennies]
Changer.for(99) -> [3, 2, 0, 4]
Changer.for(99) -> [3, 2, 0, 4]
Changer.coins = [nickels, pennies]
Changer.for(99) -> [19, 4]
Changer.for(99) -> [19, 4]
Rules
- Given coins of different values
- Find the number of coins given back for a given amount
Again, check out this slideshare.
A Solution
Here is a solution using C# with LINQ.
Other Ideas for Your Next Code Katas
Looking for new ideas for your next kata? Check out the following:
Happy coding.
Subscribe to:
Posts (Atom)