Encapsulating rod-cutting by Mark Seemann
Focusing on usage over implementation.
This article is a part of a small article series about implementation and usage mindsets. The hypothesis is that programmers who approach a problem with an implementation mindset may gravitate toward dynamically typed languages, whereas developers concerned with long-term maintenance and sustainability of a code base may be more inclined toward statically typed languages. This could be wrong, and is almost certainly too simplistic, but is still, I hope, worth thinking about. In the previous article you saw examples of an implementation-centric approach to problem-solving. In this article, I'll discuss what a usage-first perspective entails.
A usage perspective indicates that you're first and foremost concerned with how useful a programming interface is. It's what you do when you take advantage of test-driven development (TDD). First, you write a test, which furnishes an example of what a usage scenario looks like. Only then do you figure out how to implement the desired API.
In this article I didn't use TDD since I already had a particular implementation. Even so, while I didn't mention it in the previous article, I did add tests to verify that the code works as intended. In fact, because I wrote a few Hedgehog properties, I have more than 10.000 test cases covering my implementation.
I bring this up because TDD is only one way to focus on sustainability and encapsulation. It's the most scientific methodology that I know of, but you can employ more ad-hoc, ex-post analysis processes. I'll do that here.
Imperative origin #
In the previous article you saw how the Extended-Bottom-Up-Cut-Rod pseudocode was translated to this F# function:
let cut (p : _ array) n = let r = Array.zeroCreate (n + 1) let s = Array.zeroCreate (n + 1) r[0] <- 0 for j = 1 to n do let mutable q = Int32.MinValue for i = 1 to j do if q < p[i] + r[j - i] then q <- p[i] + r[j - i] s[j] <- i r[j] <- q r, s
In case anyone is wondering: This is a bona-fide pure function, even if the implementation is as imperative as can be. Given the same input, cut always returns the same output, and there are no side effects. We may wish to implement the function in a more idiomatic way, but that's not our first concern. My first concern, at least, is to make sure that preconditions, invariants, and postconditions are properly communicated.
The same goal applies to the printSolution action, also repeated here for your convenience.
let printSolution p n = let _, s = cut p n let mutable n = n while n > 0 do printfn "%i" s[n] n <- n - s[n]
Not that I'm not interested in more idiomatic implementations, but after all, they're by definition just implementation details, so first, I'll discuss encapsulation. Or, if you will, the usage perspective.
Names and types #
Based on the above two code snippets, we're given two artefacts: cut and printSolution. Since F# is a statically typed language, each operation also has a type.
The type of cut is int array -> int -> int array * int array. If you're not super-comfortable with F# type signatures, this means that cut is a function that takes an integer array and an integer as inputs, and returns a tuple as output. The output tuple is a pair; that is, it contains two elements, and in this particular case, both elements have the same type: They are both integer arrays.
Likewise, the type of printSolution is int array -> int -> unit, which again indicates that inputs must be an integer array and an integer. In this case the output is unit, which, in a sense, corresponds to void in many C-based languages.
Both operations belong to a module called Rod, so their slightly longer, more formal names are Rod.cut and Rod.printSolution. Even so, good names are only skin-deep, and I'm not even convinced that these are particularly good names. To be fair to myself, I adopted the names from the pseudocode from Introduction to Algorithms. Had I been freer to name function and design APIs, I might have chosen different names. As it is, currently, there's no documentation, so the types are the only source of additional information.
Can we infer proper usage from these types? Do they sufficiently well communicate preconditions, invariants, and postconditions? In other words, do the types satisfactorily indicate the contract of each operation? Do the functions exhibit good encapsulation?
We may start with the cut function. It takes as inputs an integer array and an integer. Are empty arrays allowed? Are all integers valid, or perhaps only natural numbers? What about zeroes? Are duplicates allowed? Does the array need to be sorted? Is there a relationship between the array and the integer? Can the single integer parameter be negative?
And what about the return value? Are the two integer arrays related in any way? Can one be empty, but the other large? Can they both be empty? May negative numbers or zeroes be present?
Similar questions apply to the printSolution action.
Not all such questions can be answered by types, but since we already have a type system at our disposal, we might as well use it to address those questions that are easily modelled.
Encapsulating the relationship between price array and rod length #
The first question I decided to answer was this: Is there a relationship between the array and the integer?
The array, you may recall, is an array of prices. The integer is the length of the rod to cut up.
A relationship clearly exists. The length of the rod must not exceed the length of the array. If it does, cut throws an IndexOutOfRangeException. We can't calculate the optimal cuts if we lack price information.
Likewise, we can already infer that the length must be a non-negative number.
While we could choose to enforce this relationship with Guard Clauses, we may also consider a simpler API. Let the function infer the rod length from the array length.
let cut (p : _ array) = let n = p.Length - 1 let r = Array.zeroCreate (n + 1) let s = Array.zeroCreate (n + 1) r[0] <- 0 for j = 1 to n do let mutable q = Int32.MinValue for i = 1 to j do if q < p[i] + r[j - i] then q <- p[i] + r[j - i] s[j] <- i r[j] <- q r, s
You may argue that this API is more implicit, which we generally don't like. The implication is that the rod length is determined by the array length. If you have a (one-indexed) price array of length 10, then how do you calculate the optimal cuts for a rod of length 7?
By shortening the price array:
> let p = [|0; 1; 5; 8; 9; 10; 17; 17; 20; 24; 30|];; val p: int array = [|0; 1; 5; 8; 9; 10; 17; 17; 20; 24; 30|] > cut (p |> Array.take (7 + 1));; val it: int array * int array = ([|0; 1; 5; 8; 10; 13; 17; 18|], [|0; 1; 2; 3; 2; 2; 6; 1|])
This is clearly still sub-optimal. Notice, for example, how you need to add 1 to 7 in order to deal with the prefixed 0. On the other hand, we're not done with the redesign, so it may be worth pursuing this course a little further.
(To be honest, while this is the direction I ultimately choose, I'm not blind to the disadvantages of this implicit design. It makes it less clear to a client developer how to indicate a rod length. An alternative design would keep the price array and the rod length as two separate parameters, but then introduce a Guard Clause to check that the rod length doesn't exceed the length of the price array. Outside of dependent types I can't think of a way to model such a relationship between two values, and I admit to having no practical experience with dependent types. All this said, however, it's also possible that I'm missing an obvious design alternative. If you can think of a way to model this relationship in a non-predicative way, please write a comment.)
I gave the printSolution the same treatment, after first having extracted a solve function in order to separate decisions from effects.
let solve p = let _, s = cut p let l = ResizeArray () let mutable n = p.Length - 1 while n > 0 do l.Add s[n] n <- n - s[n] l |> List.ofSeq let printSolution p = solve p |> List.iter (printfn "%i")
The implementation of the solve function is still imperative, but if you view it as a black box, it's referentially transparent. We'll get back to the implementation later.
Returning a list of cuts #
Let's return to all the questions I enumerated above, particularly the questions about the return value. Are the two integer arrays related?
Indeed they are! In fact, they have the same length.
As explained in the previous article, in the original pseudocode, the r array is supposed to be zero-indexed, but non-empty and containing 0 as the first element. The s array is supposed to be one-indexed, and be exactly one element shorter than the r array. In practice, in all three implementations shown in that article, I made both arrays zero-indexed, non-empty, and of the exact same length. This is also true for the F# implementation.
We can communicate this relationship much better to client developers by changing the return type of the cut function. Currently, the return type is int array * int array, indicating a pair of arrays. Instead, we can change the return type to an array of pairs, thereby indicating that the values are related two-and-two.
That would be a decent change, but we can further improve the API. A pair of integers are still implicit, because it isn't clear which integer represents the revenue and which one represents the size. Instead, we introduce a custom type with clear labels:
type Cut = { Revenue : int; Size : int }
Then we change the cut function to return a collection of Cut values:
let cut (p : _ array) = let n = p.Length - 1 let r = Array.zeroCreate (n + 1) let s = Array.zeroCreate (n + 1) r[0] <- 0 for j = 1 to n do let mutable q = Int32.MinValue for i = 1 to j do if q < p[i] + r[j - i] then q <- p[i] + r[j - i] s[j] <- i r[j] <- q let result = ResizeArray () for i = 0 to n do result.Add { Revenue = r[i]; Size = s[i] } result |> List.ofSeq
The type of cut is now int array -> Cut list. Notice that I decided to return a linked list rather than an array. This is mostly because I consider linked lists to be more idiomatic than arrays in a context of functional programming (FP), but to be honest, I'm not sure that it makes much difference as a return value.
In any case, you'll observe that the implementation is still imperative. The main topic of this article is how to give an API good encapsulation, so I treat the actual code as an implementation detail. It's not the most important thing.
Linked list input #
Although I wrote that I'm not sure it makes much difference whether cut returns an array or a list, it does matter when it comes to input values. Currently, cut takes an int array as input.
As the implementation so amply demonstrates, F# arrays are mutable; you can mutate the cells of an array. A client developer may worry, then, whether cut modifies the input array.
From the implementation code we know that it doesn't, but encapsulation is all about sparing client developers the burden of having to read the implementation. Rather, an API should communicate its contract in as succinct a way as possible, either via documentation or the type system.
In this case, we can use the type system to communicate this postcondition. Changing the input type to a linked list effectively communicates to all users of the API that cut doesn't mutate the input. This is because F# linked lists are truly immutable.
let cut prices = let p = prices |> Array.ofList let n = p.Length - 1 let r = Array.zeroCreate (n + 1) let s = Array.zeroCreate (n + 1) r[0] <- 0 for j = 1 to n do let mutable q = Int32.MinValue for i = 1 to j do if q < p[i] + r[j - i] then q <- p[i] + r[j - i] s[j] <- i r[j] <- q let result = ResizeArray () for i = 0 to n do result.Add { Revenue = r[i]; Size = s[i] } result |> List.ofSeq
The type of the cut function is now int list -> Cut list, which informs client developers of an invariant. You can trust that cut will not change the input arguments.
Natural numbers #
You've probably gotten the point by now, so let's move a bit quicker. There are still issues that we'd like to document. Perhaps the worst part of the current API is that client code is required to supply a prices list where the first element must be zero. That's a very specific requirement. It's easy to forget, and if you do, the cut function just silently fails. It doesn't throw an exception; it just gives you a wrong answer.
We may choose to add a Guard Clause, but why are we even putting that responsibility on the client developer? Why can't the cut function add that prefix itself? It can, and it turns out that once you do that, and also remove the initial zero element from the output, you're now working with natural numbers.
First, add a NaturalNumber wrapper of integers:
type NaturalNumber = private NaturalNumber of int with member this.Value = let (NaturalNumber i) = this in i static member tryCreate candidate = if candidate < 1 then None else Some <| NaturalNumber candidate override this.ToString () = let (NaturalNumber i) = this in string i
Since the case constructor is private, external code can only try to create values. Once you have a NaturalNumber value, you know that it's valid, but creation requires a run-time check. In other words, this is what Hillel Wayne calls predicative data.
Armed with this new type, however, we can now strengthen the definition of the Cut record type:
type Cut = { Revenue : int; Size : NaturalNumber } with static member tryCreate revenue size = NaturalNumber.tryCreate size |> Option.map (fun size -> { Revenue = revenue; Size = size })
The Revenue may still be any integer, because it turns out that the algorithm also works with negative prices. (For a book that's very meticulous in its analysis of algorithms, CLRS is surprisingly silent on this topic. Thorough testing with Hedgehog, however, indicates that this is so.) On the other hand, the Size of the Cut must be a NaturalNumber. Since, again, we don't have any constructive way (outside of using refinement types) of modelling this requirement, we also supply a tryCreate function.
This enables us to define the cut function like this:
let cut prices = let p = prices |> List.append [0] |> Array.ofList let n = p.Length - 1 let r = Array.zeroCreate (n + 1) let s = Array.zeroCreate (n + 1) r[0] <- 0 for j = 1 to n do let mutable q = Int32.MinValue for i = 1 to j do if q < p[i] + r[j - i] then q <- p[i] + r[j - i] s[j] <- i r[j] <- q let result = ResizeArray () for i = 1 to n do Cut.tryCreate r[i] s[i] |> Option.iter result.Add result |> List.ofSeq
It still has the type int list -> Cut list, but the Cut type is now more restrictively designed. In other words, we've provided a more conservative definition of what we return, in keeping with Postel's law.
Furthermore, notice that the first line appends 0 to the p array, so that the client developer doesn't have to do that. Likewise, when returning the result, the for loop goes from 1 to n, which means that it omits the first zero cut.
These changes ripple through and also improves encapsulation of the solve function:
let solve prices = let cuts = cut prices let l = ResizeArray () let mutable n = prices.Length while n > 0 do let idx = n - 1 let s = cuts.[idx].Size l.Add s n <- n - s.Value l |> List.ofSeq
The type of solve is now int list -> NaturalNumber list.
This is about as strong as I can think of making the API using F#'s type system. A type like int list -> NaturalNumber list tells you something about what you're allowed to do, what you're expected to do, and what you can expect in return. You can provide (almost) any list of integers, both positive, zero, or negative. You may also give an empty list. If we had wanted to prevent that, we could have used a NonEmpty list, as seen (among other places) in the article Conservative codomain conjecture.
Okay, to be perfectly honest, there's one more change that might be in order, but this is where I ran out of steam. One remaining precondition that I haven't yet discussed is that the input list must not contain 'too big' numbers. The problem is that the algorithm adds numbers together, and since 32-bit integers are bounded, you could run into overflow situations. Ask me how I know.
Changing the types to use 64-bit integers doesn't solve that problem (it only moves the boundary of where overflow happens), but consistently changing the API to work with BigInteger values might. To be honest, I haven't tried.
Functional programming #
From an encapsulation perspective, we're done now. By using the type system, we've emphasized how to use the API, rather than how it's implemented. Along the way, we even hid away some warts that came with the implementation. If I wanted to take this further, I would seriously consider making the cut function a private helper function, because it doesn't really return a solution. It only returns an intermediary value that makes it easier for the solve function to return the actual solution.
If you're even just a little bit familiar with F# or functional programming, you may have found it painful to read this far. All that imperative code. My eyes! For the love of God, please rewrite the implementation with proper FP idioms and patterns.
Well, the point of the whole article is that the implementation doesn't really matter. It's how client code may use the API that's important.
That is, of course, until you have to go and change the implementation code. In any case, as a little consolation prize for those brave FP readers who've made it all this way, here follows more functional implementations of the functions.
The NaturalNumber and Cut types haven't changed, so the first change comes with the cut function:
let private cons x xs = x :: xs let cut prices = let p = 0 :: prices |> Array.ofList let n = p.Length - 1 let findBestCut revenues j = [1..j] |> List.map (fun i -> p[i] + Map.find (j - i) revenues, i) |> List.maxBy fst let aggregate acc j = let revenues = snd acc let q, i = findBestCut revenues j let cuts = fst acc cuts << (cons (q, i)), Map.add revenues.Count q revenues [1..n] |> List.fold aggregate (id, Map.add 0 0 Map.empty) |> fst <| [] // Evaluate Hughes list |> List.choose (fun (r, i) -> Cut.tryCreate r i)
Even here, however, some implementation choices are dubious at best. For instance, I decided to use a Hughes list or difference list (see Tail Recurse for a detailed explanation of how this works in F#) without measuring whether or not it was better than just using normal list consing followed by List.rev (which is, in fact, often faster). That's one of the advantages of writing code for articles; such things don't really matter that much in that context.
Another choice that may leave you scratching your head is that I decided to model the revenues as a map (that is, an immutable dictionary) rather than an array. I did this because I was concerned that with the move towards immutable code, I'd have n reallocations of arrays. Perhaps, I thought, adding incrementally to a Map structure would be more efficient.
But really, all of that is just wanking, because I haven't measured.
The FP-style implementation of solve is, I believe, less controversial:
let solve prices = let cuts = cut prices let rec imp n = if n <= 0 then [] else let idx = n - 1 let s = cuts[idx].Size s :: imp (n - s.Value) imp prices.Length
This is a fairly standard implementation using a local recursive helper function.
Both cut and solve have the types previously reported. In other words, this final refactoring to functional implementations didn't change their types.
Conclusion #
This article goes through a series of code improvements to illustrate how a static type system can make it easier to use an API. Use it correctly, that is.
There's a common misconception about ease of use that it implies typing fewer characters, or getting instant gratification. That's not my position. Typing is not a bottleneck, and in any case, not much is gained if you make it easier for client developers to get the wrong answers from your API.
Static types gives you a consistent vocabulary you can use to communicate an API's contract to client developers. What must client code do in order to make a valid method or function call? What guarantees can client code rely on? Encapsulation, in other words.
