Partial Calculations in F#

I’ve been playing around with a little project in F# and got stuck on a little problem: how can I use the partial function application to give do a small amount of work and return a function that I can call later to do more?

To begin, let’s start with the canonical example of factorial:

let fact n =
    let rec factrec acc curr =
        if curr = 0 then acc
        else factrec (acc * curr) (curr - 1)
    factrec 1 n

 
This is a tail-recursive implementation of factorial that uses an inner function for the actual calculation.

The problem with this style is that while it writes well, it doesn’t take into account things that your typical user might want, for example, I/O cover-up. In other words, in a lengthy calculation, you might want a spinning cursor or a progress bar or any number of other things to make the user aware that the computer is working and hasn’t hung.

As a side note, there was I/O cover-up built-in to Adobe Illustrator on the Mac, which IIRC instead of having something that took a long time spinning the beach ball cursor once in a while, they installed a VBL interrupt task to spin the beach ball for them so they didn’t have to modify the code at all. This spun the cursor very smoothly, but was anathema to the purpose of the feedback because the main program could very well be hung and the cursor would continue to spin. Oops.

So let’s look at how we can rewrite this code to only do a little work at a time and be able to pick up where we left off. There are two main cases that we care about: a result or more work to do. That feels like a discriminated union to me.

type Partial<'a> =
    | Result of 'a
    | Continuation of (unit -> Partial<'a>)

The important case here is the continuation, which encapsulates a function of no arguments that returns a Partial.
So given the partial type, we can write a function that executes the partial to completion.

let rec performUntilDone (cont:Partial<'a>) =
    match cont with
    | Partial.Result (r) -> r
    | Partial.Continuation(f) ->
        printfn "Continuing..."
        performUntilDone (f ())

From here, we can rewrite our factorial function to use the Partial type:

let factpartial n =
    let rec factrec acc curr () =
        if curr = 0 then Partial.Result(acc)
        else Partial.Continuation(factrec (acc * curr) (curr - 1))
    Partial.Continuation(factrec 1 n)

The differences are few, but notable. First, the inner function has a new argument, which is the type unit. This is because we’re going to do a partial application on that function, but we need to bind to all the arguments and that’s not partial application. For the base case of curr = 0, we return a Partial.Result(acc) instead of acc and instead of the recursive call, we return a Partial.Continuation of the partial application of the inner function.
When we run this with 5, we get this at output:

Continuing...
Continuing...
Continuing...
Continuing...
Continuing...
Continuing...
120

What if instead we wanted to have more information about the calculation that’s going on? For that we need to redefine the Partial type to also encapsulate intermediate results as well as the performUntilDone function and make a change to factorial to use the PartialIntermediate type.

type PartialIntermediate<'a, 'b> =
    | Result of 'a
    | Continuation of 'b * (unit -> PartialIntermediate<'a, 'b>)
 
let rec performIntermediateUntilDone (cont:PartialIntermediate<'a, 'b>) =
    match cont with
    | PartialIntermediate.Result(r) -> r
    | PartialIntermediate.Continuation(intermediate, f) ->
        printfn "Continuing (%A)" intermediate
        performIntermediateUntilDone (f ())
 
let factintermediate n =
    let rec factrec (acc:int) curr () =
        if curr = 0 then PartialIntermediate.Result(acc)
        else PartialIntermediate.Continuation((acc, (factrec (acc * curr) (curr - 1))))
    PartialIntermediate.Continuation((1, factrec 1 n))

When you run this, you get this output:

Continuing (1)
Continuing (1)
Continuing (5)
Continuing (20)
Continuing (60)
Continuing (120)
120

We can see that it’s very easy to transform traditional tail-recursive code and transform it into code that can run incrementally. Certainly, there are other ways that this code could be formatted. For example, you could rewrite the function to take a callback function and run it in a thread. Both approaches have their benefits and detriments.

One thought on “Partial Calculations in F#”

Leave a Reply

Your email address will not be published. Required fields are marked *