Today I had a sticky problem to solve, the kind business app programmers drool over because it’s nontrivial and contained. Halfway through the TDD process, my logic got all jumbled and I couldn’t see the solution. Stepping back, I took ten minutes to write pseudocode in an F# style, then translated that into Java. Bam! green all over. Turns out this problem is more suited to recursion and pattern matching than loops and variables. The same style works just fine in Java, but thinking in F# brought it to light.
As an illustrative example, here’s the code in both languages.
The problem:
Money comes in through deposits. Money goes out through dispensations. Take an ordered list of each and pair them up into Utilizations, which identify which deposits were used to satisfy which dispensations. If any dispensation cannot be satisfied with the provided deposits, do not satisfy the dispensation at all.
The F#:
type Deposit = { amount : int }
type Dispensation { amount : int }
type Utilization =
| DepUtil of Deposit * Dispensation * int
let rec utilizeInternal outputSoFar currentDispOutput (deposits:Deposit list) (dispensations:Dispensation list) depUsed dispUsed : Utilization list =
match (deposits, dispensations) with
| [] , _ -> outputSoFar
| _ , [] -> outputSoFar
| dep :: depTail, disp:: dispTail ->
match(dep.amount – depUsed, disp.amount – dispUsed) with
| (depAmt, dispAmt) when depAmt = dispAmt ->
utilizeInternal (DepUtil(dep, disp, depAmt) :: currentDispOutput @ outputSoFar) [] depTail dispTail 0 0
| (depAmt, dispAmt) when depAmt
utilizeInternal outputSoFar (DepUtil(dep, disp, depAmt) :: currentDispOutput) depTail (disp :: dispTail) 0 (dispUsed + depAmt)
| (depAmt, dispAmt) when dispAmt
utilizeInternal( DepUtil(dep, disp, dispAmt) :: currentDispOutput @ outputSoFar) [] (dep :: depTail) dispTail (depUsed + dispAmt) 0
let utilize deposits dispensations = utilizeInternal [] [] deposits dispensations 0 0
The key portion, the recursive function definition, works out to nine long lines. It divides the problem up neatly into: the deposit and dispensation match exactly; the deposit is more than the dispensation; the dispensation is more than the deposit. Those are the three non-trivial cases.
Translating this into Java simply puts these cases into if-then statements.
The Java:
The Java is twice as long as the F#, sure, but it works beautifully. What matters is that knowing a different language, and thinking about the problem in terms of the better-suited language, led me to a good solution in the language of my day job.
Functional programming! It’s not just for math geeks!