Here’s another solution to the Secret Santa code kata, this time a scouting mission into functional programming with F#.
- My first solution, written in PowerShell, relied on selecting random pairs of people and using a “hill-climbing” algorithm to avoid getting stuck.
- My second solution I constrained to be deterministic — no randomness.
This one was more about trying to write something meaningful in F# using a problem I’m by now familiar with. Take a look at the code:
As you can see, I left myself a few to-do items. I boxed the effort at three hours, which is why I went ahead and borrowed the shuffle logic from the internet.
The first hour was learning to speak F# again, especially the method signatures. I played with F# when it was in beta, so I didn’t go into the kata stone cold. However, it took me a while to troubleshoot why my methods didn’t have the signature I expected.
I spent the most time writing the
pairings function. Once I had the insight of using the match operator, the algorithm came together very quickly. I decided that I wasn’t happy with it being deterministic. I found that if I provided a file that was already in an appropriate order,
pairings regurgitated the list. Dissatisfied, I went about trying to shuffle the array. Not being familiar with unit testing in F#, I used the F# Interactive console. I got frustrated with trying to implement the shuffle algorithm, so I decided to study a working copy.
The hard part came in integrating it with my code. I resorted to using a while loop, which I know from reading about functional programs means that I’m not thinking of the problem through. I believe I couldn’t convert this into a recursive function because
shuffle returns a
unit (that is, it does the work inline). If it returned an array, I bet I’ve have more luck. I’ll have to experiment further.
My attempts to rewrite the loop badly broke the program. I used comments as poor man’s source control, and I got lucky. I really should have check in the first working version into my local Subversion repository.
Some time passed. I managed to look at the do-while problem again, and after about 90 minutes, I solved both it and another issue that bugged me.
Here’s the second revision:
The do-while loop was solved by making the shuffling function return the shuffled contents instead of unit (void in C# parlance).
The second change was to get away from arrays. Arrays in F# are mutable, and I wanted to only use immutable data structures as much as possible.
The shuffler was the main barrier. Once I hit upon the idea to associate each person with external data, in this case a random weighting, the rest fell into place. You may also notice some language usage improvements, such as using
a.Head instead of