Wednesday, May 16, 2012

F# made Java easier today

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 < dispAmt -> 
           utilizeInternal outputSoFar (DepUtil(dep, disp, depAmt) ::  currentDispOutput) depTail (disp :: dispTail) 0 (dispUsed + depAmt)
       | (depAmt, dispAmt) when dispAmt < depAmt -> 
           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:

public class DepositUtilizer {

    public static class Utilization {
        public final Deposit deposit;
        public final Dispensation dispensation;
        public final long amountInPennies;

        public Utilization(Deposit deposit, Dispensation dispensation, long amountInPennies) {
            this.deposit = deposit;
            this.dispensation = dispensation;
            this.amountInPennies = amountInPennies;
        }
    }

    public Iterable<Utilization> utilize(Iterable<Deposit> deposits, Iterable<Dispensation> dispensations) {
        return utilizeInternal(new ArrayList<Utilization>(), new ArrayList<Utilization>(),
                peekingIterator(deposits.iterator()), peekingIterator(dispensations.iterator()), 0l, 0l);
    }

    private Iterable<Utilization> utilizeInternal(Iterable<Utilization> outputSoFar,
            List<Utilization> currentDispensationOutput, PeekingIterator<Deposit> deposits,
            PeekingIterator<Dispensation> dispensations, long amountUsedSoFarInCurrentDeposit,
            long amountUsedSoFarInCurrentDispensation) {
        if (!deposits.hasNext() || !dispensations.hasNext()) {
            return outputSoFar;
        }

        long dispensationAmount = dispensations.peek().getAmountForJPA() - amountUsedSoFarInCurrentDispensation;
        long depositAmount = deposits.peek().getUnutilizedAmount().getPennies() - amountUsedSoFarInCurrentDeposit;

        if (depositAmount == dispensationAmount) {
            // great, use them both up
            Deposit usedDeposit = deposits.next();
            Dispensation usedDispensation = dispensations.next();
            currentDispensationOutput.add(new Utilization(usedDeposit, usedDispensation, depositAmount));
            return utilizeInternal(concat(outputSoFar, currentDispensationOutput), new ArrayList<Utilization>(), deposits,
                    dispensations, 0l, 0l);
        }
        if (depositAmount < dispensationAmount) {
            // use all of the deposit
            Deposit usedDeposit = deposits.next();
            currentDispensationOutput.add(new Utilization(usedDeposit, dispensations.peek(), depositAmount));
            return utilizeInternal(outputSoFar, currentDispensationOutput, deposits, dispensations, 0l,
                    amountUsedSoFarInCurrentDispensation + depositAmount);
        }
        if (dispensationAmount < depositAmount) {
            // use all of the dispensation
            Dispensation usedDispensation = dispensations.next();
            currentDispensationOutput.add(new Utilization(deposits.peek(), usedDispensation, dispensationAmount));
            return utilizeInternal(concat(outputSoFar, currentDispensationOutput), new ArrayList<Utilization>(), deposits,
                    dispensations, amountUsedSoFarInCurrentDeposit + dispensationAmount, 0l);
        }
        throw new IllegalStateException("The sky is falling!");
    }
}

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!




No comments:

Post a Comment