ploeh blog

Recawr Sandwich

2025-01-13T15:52:00+00:00

A pattern variation.

After writing the articles Collecting and handling result values and Short-circuiting an asynchronous traversal, I realized that it might be valuable to describe a more disciplined variation of the Impureim Sandwich pattern.

The book Design Patterns describes each pattern over a number of sections. There's a description of the overall motivation, the structure of the pattern, UML diagrams, examples code, and more. One section discusses various implementation variations. I find it worthwhile, too, to explicitly draw attention to a particular variation of the more overall Impureim Sandwich pattern.

This variation imposes an additional constraint to the general pattern. While this may, at first glance, seem limiting, constraints liberate.

As a specialization, you may consider Recawr Sandwiches as a subset of all Impureim Sandwiches.

Read, calculate, write #

In short, the constraint is that the Sandwich should be organized in the following order:

Read data. This step is impure.
Calculate a result from the data. This step is a pure function.
Write data. This step is impure.

If the sandwich has more than three layers, this order should still be maintained. Once you start writing data to the network, to disk, to a database, or to the user interface, you shouldn't go back to reading in more data.

Naming #

The name Recawr Sandwich is made from the first letters of REad CAlculate WRite. It's pronounced recover sandwich.

When the idea of naming this variation originally came to me, I first thought of the name read/write sandwich, but then I thought that the most important ingredient, the pure function, was missing. I've considered some other variations, such as read, pure, write sandwich or input, referential transparency, output sandwich, but none of them quite gets the point across, I think, in the same way as read, calculate, write.

Precipitating example #

To be clear, I've been applying the Recawr Sandwich pattern for years, but it sometimes takes a counter-example before you realize that some implicit, tacit knowledge should be made explicit. This happened to me as I was discussing this implementation of Impureim Sandwich:

// Impure
IEnumerable<OneOf<ShoppingListItem, NotFound<ShoppingListItem>, Error>> results =
    await itemsToUpdate.Traverse(item => UpdateItem(item, dbContext));
 
// Pure
var result = results.Aggregate(
    new BulkUpdateResult([], [], []),
    (state, result) =>
        result.Match(
            storedItem => state.Store(storedItem),
            notFound => state.Fail(notFound.Item),
            error => state.Error(error)));
 
// Impure
await dbContext.SaveChangesAsync();
return new OkResult(result);

Notice that the top impure step traverses a collection of items to apply each to an action called UpdateItem. As I discussed in the article, I don't actually know what UpdateItem does, but the name strongly suggests that it updates a particular database row. Even if the actual write doesn't happen until SaveChangesAsync is called, this still seems off.

To be honest, I didn't realize this until I started thinking about how I'd go about solving the implied problem, if I had to do it from scratch. Because I probably wouldn't do it like that at all.

It strikes me that doing the update 'too early' makes the code more complicated than it has to be.

What would a Recawr Sandwich look like?

Recawr example #

Perhaps one could instead start by querying the database about which items are actually in it, then prepare the result, and finally make the update.

// Read
var existing = await FilterExisting(itemsToUpdate, dbContext);
 
// Calculate
var result = new BulkUpdateResult([.. existing], [.. itemsToUpdate.Except(existing)], []);
 
// Write
var results = await existing.Traverse(item => UpdateItem(item, dbContext));
await dbContext.SaveChangesAsync();
return new OkResult(result);

To be honest, this variation has different behaviour when Error values occur, but then again, I wasn't entirely sure what was even the purpose of the error value. If it's to model errors that client code can't recover from, throw an exception instead.

In any case, the example is typical of many I/O-heavy operations, which veer dangerously close to the degenerate. There really isn't a lot of logic required, so one may reasonably ask whether the example is useful. It was, however, the example that got me thinking about giving the Recawr Sandwich an explicit name.

Other examples #

All the examples in the original Impureim Sandwich article are actually Recawr Sandwiches. Other articles with clear Recawr Sandwich examples are:

In other words, I'm just retroactively giving these examples a more specific label.

What's an example of an Impureim Sandwich which is not a Recawr Sandwich? Ironically, the first example in this article.

Conclusion #

A Recawr Sandwich is a specialization of the slightly more general Impureim Sandwich pattern. It specializes by assigning roles to the two impure layers of the sandwich. In the first, the code reads data. In the second impure layer, it writes data. In between, it performs referentially transparent calculations.

While more constraining, this specialization offers a good rule of thumb. Most well-designed sandwiches follow this template.

This blog is totally free, but if you like it, please consider supporting it.

Encapsulating rod-cutting

2025-01-06T10:45:00+00:00

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 prepends 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.

This blog is totally free, but if you like it, please consider supporting it.

Pytest is fast

2024-12-30T16:01:00+00:00

One major attraction of Python. A recent realization.

Ever since I became aware of the distinction between statically and dynamically typed languages, I've struggled to understand the attraction of dynamically typed languages. As regular readers may have noticed, this is a bias that doesn't sit well with me. Clearly, there are advantages to dynamic languages that I fail to notice. Is it a question of mindset? Or is it a combination of several small advantages?

In this article, I'll discuss another potential benefit of at least one dynamically typed language, Python.

Fast feedback #

Rapid feedback is a cornerstone of modern software engineering. I've always considered the feedback from the compiler an important mechanism, but I've recently begun to realize that it comes with a price. While a good type system keeps you honest, compilation takes time, too.

Since I've been so entrenched in the camp of statically typed languages (C#, F#, Haskell), I've tended to regard compilation as a mandatory step. And since the compiler needs to run anyway, you might as well take advantage of it. Use the type system to make illegal states unrepresentable, and all that.

Even so, I've noticed that compilation time isn't a fixed size. This observation surely borders on the banal, but with sufficient cognitive bias, it can, apparently, take years to come to even such a trivial conclusion. After initial years with various programming languages, my formative years as a programmer were spent with C#. As it turns out, the C# compiler is relatively fast.

This is probably a combination of factors. Since C# is a one of the most popular languages, it has a big and skilled engineering team, and it's my impression that much effort goes into making it as fast and efficient as possible.

I also speculate that, since the C# type system isn't as powerful as F#'s or Haskell's, there's simply work that it can't do. When you can't expression certain constraints or relationships with the type system, the compiler can't check them, either.

That said, the C# compiler seems to have become slower over the years. This could be a consequence of all the extra language features that accumulate.

The F# compiler, in comparison, has always taken longer than the C# compiler. Again, this may be due to a combination of a smaller engineering team and that it actually can check more things at compile time, since the type system is more expressive.

This, at least, seems to fit with the observation that the Haskell compiler is even slower than F#. The language is incredibly expressive. There's a lot of constraints and relationships that you can model with the type system. Clearly, the compiler has to perform extra work to check that your types line up.

You're often left with the impression that if it compiles, it works. The drawback is that getting Haskell code to compile may be a non-trivial undertaking.

One thing is that you'll have to wait for the compiler. Another is that if you practice test-driven development (TDD), you'll have to compile the test code, too. Only once the tests are compiled can you run them. And TDD test suites should run in 10 seconds or less.

Skipping compilation with pytest #

A few years ago I had to learn a bit of Python, so I decided to try Advent of Code 2022 in Python. As the puzzles got harder, I added unit tests with pytest. When I ran them, I was taken aback at how fast they ran.

There's no compilation step, so the test suite runs immediately. Obviously, if you've made a mistake that a compiler would have caught, the test fails, but if the code makes sense to the interpreter, it just runs.

For various reasons, I ran out of steam, as one does with Advent of Code, but I managed to write a good little test suite. Until day 17, it ran in 0.15-0.20 seconds on my little laptop. To be honest, though, once I added tests for day 17, feedback time jumped to just under two seconds. This is clearly because I'd written some inefficient code for my System Under Test.

I can't really blame a test framework for being slow, when it's really my own code that slows it down.

A counter-argument is that a compiled language is much faster than an interpreted one. Thus, one might think that a faster language would counter poor implementations. Not so.

TDD with Haskell #

As I've already outlined, the Haskell compiler takes more time than C#, and obviously it takes more time than a language that isn't compiled at all. On the other hand, Haskell compiles to native machine code. My experience with it is that once you've compiled your program, it's fast.

In order to compare the two styles, I decided to record compilation and test times while doing Advent of Code 2024 in Haskell. I set up a Haskell code base with Stack and HUnit, as I usually do. As I worked through the puzzles, I'd be adding and running tests. Every time I recorded the time it took, using the time command to measure the time it took for stack test to run.

I've plotted the observations in this chart:

The chart shows more than a thousand observations, with the first to the left, and the latest to the right. The times recorded are the entire time it took from I started a test run until I had an answer. For this, I used the time command's real time measurement, rather than user or sys time. What matters is the feedback time; not the CPU time.

Each measurement is in seconds. The dashed orange line indicates the linear trend.

It's not the first time I've written Haskell code, so I knew what to expect. While you get the occasional fast turnaround time, it easily takes around ten seconds to compile even an empty code base. It seems that there's a constant overhead of that size. While there's an upward trend line as I added more and more code, and more tests, actually running the tests takes almost no time. The initial 'average' feedback time was around eight seconds, and 1100 observations later, the trends sits around 11.5 seconds. At this time, I had more than 200 test cases.

You may also notice that the observations vary quite a bit. You occasionally see sub-second times, but also turnaround times over thirty seconds. There's an explanation for both.

The sub-second times usually happen if I run the test suite twice without changing any code. In that case, the Haskell Stack correctly skips recompiling the code and instead just reruns the tests. This only highlights that I'm not waiting for the tests to execute. The tests are fast. It's the compiler that causes over 90% of the delay.

(Why would I rerun a test suite without changing any code? This mostly happens when I take a break from programming, or if I get distracted by another task. In such cases, when I return to the code, I usually run the test suite in order to remind myself of the state in which I left it. Sometimes, it turns out, I'd left the code in a state were the last thing I did was to run all tests.)

The other extremes have a different explanation.

IDE woes #

Why do I have to suffer through those turnaround times over twenty seconds? A few times over thirty?

The short answer is that these represent complete rebuilds. Most of these are caused by problems with the IDE. For Haskell development, I use Visual Studio Code with the Haskell extension.

Perhaps it's only my setup that's messed up, but whenever I change a function in the System Under Test (SUT), I can. not. make. VS Code pick up that the API changed. Even if I correct my tests so that they still compile and run successfully from the command line, VS Code will keep insisting that the code is wrong.

This is, of course, annoying. One of the major selling points of statically type languages is that a good IDE can tell you if you made mistakes. Well, if it operates on an outdated view of what the SUT looks like, this no longer works.

I've tried restarting the Haskell Language Server, but that doesn't work. The only thing that works, as far as I've been able to discover, is to close VS Code, delete .stack-work, recompile, and reopen VS Code. Yes, that takes a minute or two, so not something I like doing too often.

Deleting .stack-work does trigger a full rebuild, which is why we see those long build times.

Striking a good balance #

What bothers me about dynamic languages is that I find discoverability and encapsulation so hard. I can't just look at the type of an operation and deduce what inputs it might take, or what the output might look like.

To be honest, if you give me a plain text file with F# or Haskell, I can't do that either. A static type system doesn't magically surface that kind of information. Instead, you may rely on an IDE to provide such information at your fingertips. The Haskell extension, for example, gives you a little automatic type annotation above your functions, as discussed in the article Pendulum swing: no Haskell type annotation by default, and shown in a figure reprinted here for your convenience:

If this is to work well, this information must be immediate and responsive. On my system it isn't.

It may, again, be that there's some problem with my particular tool chain setup. Or perhaps a four-year-old Lenovo X1 Carbon is just too puny a machine to effectively run such a tool.

On the other hand, I don't have similar issues with C# in Visual Studio (not VS Code). When I make changes, the IDE quickly responds and tells me if I've made a mistake. To be honest, even here, I feel that it was faster and more responsive a decade ago, but compared to Haskell programming, the feedback I get with C# is close to immediate.

My experience with F# is somewhere in between. Visual Studio is quicker to pick up changes in F# code than VS Code is to reflect changes in Haskell, but it's not as fast as C#.

With Python, what little IDE integration is available is usually not trustworthy. Essentially, when suggesting callable operations, the IDE is mostly guessing, based on what it's already seen.

But, good Lord! The tests run fast.

Conclusion #

My recent experiences with both Haskell and Python programming is giving me a better understanding of the balances and trade-offs involved with picking a language. While I still favour statically typed languages, I'm beginning to see some attractive qualities on the other side.

Particularly, if you buy the argument that TDD suites should run in 10 seconds or less, this effectively means that I can't do TDD in Haskell. Not with the hardware I'm running. Python, on the other hand, seems eminently well-suited for TDD.

That doesn't sit too well with me, but on the other hand, I'm glad. I've learned about a benefit of a dynamically typed language. While you may consider all of this ordinary and trite, it feels like a small breakthrough to me. I've been trying hard to see past my own limitations, and it finally feels as though I've found a few chinks in the armour of my biases.

I'll keep pushing those envelopes to see what else I may learn.

Comments

Daniel Tartaglia #

An interesting insight, but if you consider that the compiler is effectively an additional test suit that is verifying the types are being used correctly, that extra compilation time is really just a whole suite of tests that you didn't have to write. I can't help but wonder how long it would take to manually implement all the tests that would be required to satisfy those checks in Python, and how much slower the Python test suite would then be.

Like you, I have a strong bias for typesafe languages (or at least moderately typesafe ones). The way I've always explained it is as follows: Developers tend to work faster when writing with dynamic typed languages because they don't have to explain as much to a compiler. This literally means less code to write. However, because the developer hasen't fully explained themself, any follow-on developer does not have as much context to work with.

After all, whether the language requires it or not, the developers need to define and consider types. The only question is, do they have to write it down

2025-01-01 01:26 UTC

Mark Seemann #

Daniel, thank you for writing. I'm well aware that a type checker is a 'first line of defence', and I agree that if we truly had to replicate everything that a type checker does, as tests, it would take a long time. It would take a long time to write all those tests, and it would probably also take a long time to execute them all.

That said, I think that any sane proponent of dynamically typed languages would counter that that's an unreasonable demand. After all, in most cases, it's hardly the case that the code was written by a monkey with a typewriter, but rather by a well-meaning human who did his or her best to write correct code.

In the end, however, it's all a question about context. How important is correctness, after all? Dan North once kindly pointed out to me that in many cases, the software owner doesn't even know what he or she wants. It's only through a series of iterations that we learn what a business system is supposed to do. Until we reach that point, correctness is, at best, a secondary priority. On the other hand, you should really test your outer space proble software.

But you're right. The types are still there, either way.

The last word in this debate are hardly said yet, but you may also find my recent article series Implementation and usage mindsets interesting.

2025-01-07 06:53 UTC

This blog is totally free, but if you like it, please consider supporting it.

Implementing rod-cutting

2024-12-23T08:53:00+00:00

From pseudocode to implementation in three languages.

This article picks up where Implementation and usage mindsets left off, examining how easy it is to implement an algorithm in three different programming languages.

As an example, I'll use the bottom-up rod-cutting algorithm from Introduction to Algorithms.

Rod-cutting #

The problem is simple:

"Serling Enterprises buys long steel rods and cuts them into shorter rods, which it then sells. Each cut is free. The management of Serling Enterprises wants to know the best way to cut up the rods."

Introduction to Algorithms. Fourth edition, ch. 14.1

You're given an array of prices, or rather revenues, that each size is worth. The example from the book is given as a table:

length i	1	2	3	4	5	6	7	8	9	10
price p_i	1	5	8	9	10	17	17	20	24	30

Notice that while this implies an array like [1, 5, 8, 9, 10, 17, 17, 20, 24, 30], the array is understood to be one-indexed, as is the most common case in the book. Most languages, including all three languages in this article, have zero-indexed arrays, but it turns out that we can get around the issue by adding a leading zero to the array: [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30].

Thus, given that price array, the best you can do with a rod of length 10 is to leave it uncut, yielding a revenue of 30.

On the other hand, if you have a rod of length 7, you can cut it into two rods of lengths 1 and 6.

Another solution for a rod of length 7 is to cut it into three rods of sizes 2, 2, and 3. Both solutions yield a total revenue of 18. Thus, while more than one optimal solution exists, the algorithm given here only identifies one of them.

Extended-Bottom-Up-Cut-Rod(p, n)
 1 let r[0:n] and s[1:n] be new arrays
 2 r[0] = 0
 3 for j = 1 to n                // for increasing rod length j
 4     q = -∞
 5     for i = 1 to j            // i is the position of the first cut
 6         if q < p[i] + r[j - i]
 7             q = p[i] + r[j - i]
 8             s[j] = i         // best cut location so far for length j
 9     r[j] = q                 // remember the solution value for length j
10 return r and s

Which programming language is this? It's no particular language, but rather pseudocode.

The reason that the function is called Extended-Bottom-Up-Cut-Rod is that the book pedagogically goes through a few other algorithms before arriving at this one. Going forward, I don't intend to keep that rather verbose name, but instead just call the function cut_rod, cutRod, or Rod.cut.

The p parameter is a one-indexed price (or revenue) array, as explained above, and n is a rod size (e.g. 10 or 7, reflecting the above examples).

Given the above price array and n = 10, the algorithm returns two arrays, r for maximum possible revenue for a given cut, and s for the size of the maximizing cut.

i	0	1	2	3	4	5	6	7	8	9	10
r[i]	0	1	5	8	10	13	17	18	22	25	30
s[i]		1	2	3	2	2	6	1	2	3	10

Such output doesn't really give a solution, but rather the raw data to find a solution. For example, for n = 10 (= i), you consult the table for (one-indexed) index 10, and see that you can get the revenue 30 from making a cut at position 10 (which effectively means no cut). For n = 7, you consult the table for index 7 and observe that you can get the total revenue 18 by making a cut at position 1. This leaves you with two rods, and you again consult the table. For n = 1, you can get the revenue 1 by making a cut at position 1; i.e. no further cut. For n = 7 - 1 = 6 you consult the table and observe that you can get the revenue 17 by making a cut at position 6, again indicating that no further cut is necessary.

Another procedure prints the solution, using the above process:

Print-Cut-Rod-Solution(p, n)
 1 (r, s) = Extended-Bottom-Up-Cut-Rod(p, n)
 2 while n > 0
 3     print s[n]    // cut location for length n
 4     n = n - s[n]  // length of the remainder of the rod

Again, the procedure is given as pseudocode.

How easy is it translate this algorithm into code in a real programming language? Not surprisingly, this depends on the language.

Translation to Python #

The hypothesis of the previous article is that dynamically typed languages may be more suited for implementation tasks. The dynamically typed language that I know best is Python, so let's try that.

def cut_rod(p, n):
    r = [0] * (n + 1)
    s = [0] * (n + 1)
    r[0] = 0
    for j in range(1, n + 1):
        q = float('-inf')
        for i in range(1, j + 1):
            if q < p[i] + r[j - i]:
                q = p[i] + r[j - i]
                s[j] = i
        r[j] = q
    return r, s

That does, indeed, turn out to be straightforward. I had to figure out the syntax for initializing arrays, and how to represent negative infinity, but a combination of GitHub Copilot and a few web searches quickly cleared that up.

The same is true for the Print-Cut-Rod-Solution procedure.

def print_cut_rod_solution(p, n):
    r, s = cut_rod(p, n)
    while n > 0:
        print(s[n])
        n = n - s[n]

Apart from minor syntactical differences, the pseudocode translates directly to Python.

So far, the hypothesis seems to hold. This particular dynamically typed language, at least, easily implements that particular algorithm. If we must speculate about underlying reasons, we may argue that a dynamically typed language is low on ceremony. You don't have to get side-tracked by declaring types of parameters, variables, or return values.

That, at least, is a common complaint about statically typed languages that I hear when I discuss with lovers of dynamically typed languages.

Let us, then, try to implement the rod-cutting algorithm in a statically typed language.

Translation to Java #

Together with other C-based languages, Java is infamous for requiring a high amount of ceremony to get anything done. How easy is it to translate the rod-cutting pseudocode to Java? Not surprisingly, it turns out that one has to jump through a few more hoops.

First, of course, one has to set up a code base and choose a build system. I'm not well-versed in Java development, but here I (more or less) arbitrarily chose gradle. When you're new to an ecosystem, this can be a significant barrier, but I know from decades of C# programming that tooling alleviates much of that pain. Still, a single .py file this isn't.

Apart from that, the biggest hurdle turned out to be that, as far as I can tell, Java doesn't have native tuple support. Thus, in order to return two arrays, I would have to either pick a reusable package that implements tuples, or define a custom class for that purpose. Object-oriented programmers often argue that tuples represent poor design, since a tuple doesn't really communicate the role or intent of each element. Given that the rod-cutting algorithm returns two integer arrays, I'd be inclined to agree. You can't even tell them apart based on their types. For that reason, I chose to define a class to hold the result of the algorithm.

public class RodCuttingSolution {
    private int[] revenues;
    private int[] sizes;
 
    public RodCuttingSolution(int[] revenues, int[] sizes) {
        this.revenues = revenues;
        this.sizes = sizes;
    }
 
    public int[] getRevenues() {
        return revenues;
    }
 
    public int[] getSizes() {
        return sizes;
    }
}

Armed with this return type, the rest of the translation went smoothly.

public static RodCuttingSolution cutRod(int[] p, int n) {
    var r = new int[n + 1];
    var s = new int[n + 1];
    r[0] = 0;
    for (int j = 1; j <= n; j++) {
        var q = Integer.MIN_VALUE;
        for (int i = 1; i <= j; i++) {
            if (q < p[i] + r[j - i]) {
                q = p[i] + r[j - i];
                s[j] = i;
            }
        }
        r[j] = q;
    }
    return new RodCuttingSolution(r, s);
}

Granted, there's a bit more ceremony involved compared to the Python code, since one must declare the types of both input parameters and method return type. You also have to declare the type of the arrays when initializing them, and you could argue that the for loop syntax is more complicated than Python's for ... in range ... syntax. One may also complain that all the brackets and parentheses makes it harder to read the code.

While I'm used to such C-like code, I'm not immune to such criticism. I actually do find the Python code more readable.

Translating the Print-Cut-Rod-Solution pseudocode is a bit easier:

public static void printCutRodSolution(int[] p, int n) {
    var result = cutRod(p, n);
    while (n > 0) {
        System.out.println(result.getSizes()[n]);
        n = n - result.getSizes()[n];
    }
}

The overall structure of the code remains intact, but again we're burdened with extra ceremony. We have to declare input and output types, and call that awkward getSizes method to retrieve the array of cut sizes.

It's possible that my Java isn't perfectly idiomatic. After all, although I've read many books with Java examples over the years, I rarely write Java code. Additionally, you may argue that static methods exhibit a code smell like Feature Envy. I might agree, but the purpose of the current example is to examine how easy or difficult it is to implement a particular algorithm in various languages. Now that we have an implementation in Java, we might wish to refactor to a more object-oriented design, but that's outside the scope of this article.

Given that the rod-cutting algorithm isn't the most complex algorithm that exists, we may jump to the conclusion that Java isn't that bad compared to Python. Consider, however, how the extra ceremony on display here impacts your work if you have to implement a larger algorithm, or if you need to iterate to find an algorithm on your own.

To be clear, C# would require a similar amount of ceremony, and I don't even want to think about doing this in C.

All that said, it'd be irresponsible to extrapolate from only a few examples. You'd need both more languages and more problems before it even seems reasonable to draw any conclusions. I don't, however, intend the present example to constitute a full argument. Rather, it's an illustration of an idea that I haven't pulled out of thin air.

One of the points of Zone of Ceremony is that the degree of awkwardness isn't necessarily correlated to whether types are dynamically or statically defined. While I'm sure that I miss lots of points made by 'dynamists', this is a point that I often feel is missed by that camp. One language that exemplifies that 'beyond-ceremony' zone is F#.

Translation to F# #

If I'm right, we should be able to translate the rod-cutting pseudocode to F# with approximately the same amount of trouble than when translating to Python. How do we fare?

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

Fairly well, as it turns out, although we do have to annotate p by indicating that it's an array. Still, the underscore in front of the array keyword indicates that we're happy to let the compiler infer the type of array (which is int array).

(We can get around that issue by writing Array.item i p instead of p[i], but that's verbose in a different way.)

Had we chosen to instead implement the algorithm based on an input list or map, we wouldn't have needed the type hint. One could therefore argue that the reason that the hint is even required is because arrays aren't the most idiomatic data structure for a functional language like F#.

Otherwise, I don't find that this translation was much harder than translating to Python, and I personally prefer for j = 1 to n do over for j in range(1, n + 1):.

We also need to add the mutable keyword to allow q to change during the loop. You could argue that this is another example of additional ceremony, While I agree, it's not much related to static versus dynamic typing, but more to how values are immutable by default in F#. If I recall correctly, JavaScript similarly distinguishes between let, var, and const.

Translating Print-Cut-Rod-Solution requires, again due to values being immutable by default, a bit more effort than Python, but not much:

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]

I had to shadow the n parameter with a mutable variable to stay as close to the pseudocode as possible. Again, one may argue that the overall problem here isn't the static type system, but that programming based on mutation isn't idiomatic for F# (or other functional programming languages). As you'll see in the next article, a more idiomatic implementation is even simpler than this one.

Notice, however, that the printSolution action requires no type declarations or annotations.

Let's see it all in use:

> 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|]

> Rod.printSolution p 7;;
1
6

This little interactive session reproduces the example illustrated in the beginning of this article, when given the price array from the book and a rod of size 7, the solution printed indicates cuts at positions 1 and 6.

I find it telling that the translation to F# is on par with the translation to Python, even though the structure of the pseudocode is quite imperative.

Conclusion #

You could, perhaps, say that if your mindset is predominantly imperative, implementing an algorithm using Python is likely easier than both F# or Java. If, on the other hand, you're mostly in an implementation mindset, but not strongly attached to whether the implementation should be imperative, object-oriented, or functional, I'd offer the conjecture that a language like F# is as implementation-friendly as a language like Python.

If, on the other hand, you're more focused on encapsulating and documenting how an existing API works, perhaps that shift of perspective suggests another evaluation of dynamically versus statically typed languages.

In any case, the F# code shown here is hardly idiomatic, so it might be illuminating to see what happens if we refactor it.

Next: Encapsulating rod-cutting.

This blog is totally free, but if you like it, please consider supporting it.

A restaurant sandwich

2024-12-16T19:11:00+00:00

An Impureim Sandwich example in C#.

When learning functional programming (FP) people often struggle with how to organize code. How do you discern and maintain purity? How do you do Dependency Injection in FP? What does a functional architecture look like?

A common FP design pattern is the Impureim Sandwich. The entry point of an application is always impure, so you push all impure actions to the boundary of the system. This is also known as Functional Core, Imperative Shell. If you have a micro-operation-based architecture, which includes all web-based systems, you can often get by with a 'sandwich'. Perform impure actions to collect all the data you need. Pass all data to a pure function. Finally, use impure actions to handle the referentially transparent return value from the pure function.

No design pattern applies universally, and neither does this one. In my experience, however, it's surprisingly often possible to apply this architecture. We're far past the Pareto principle's 80 percent.

Examples may help illustrate the pattern, as well as explore its boundaries. In this article you'll see how I refactored an entry point of a REST API, specifically the PUT handler in the sample code base that accompanies Code That Fits in Your Head.

Starting point #

As discussed in the book, the architecture of the sample code base is, in fact, Functional Core, Imperative Shell. This isn't, however, the main theme of the book, and the code doesn't explicitly apply the Impureim Sandwich. In spirit, that's actually what's going on, but it isn't clear from looking at the code. This was a deliberate choice I made, because I wanted to highlight other software engineering practices. This does have the effect, though, that the Impureim Sandwich is invisible.

For example, the book follows the 80/24 rule closely. This was a didactic choice on my part. Most code bases I've seen in the wild have far too big methods, so I wanted to hammer home the message that it's possible to develop and maintain a non-trivial code base with small code blocks. This meant, however, that I had to split up HTTP request handlers (in ASP.NET known as action methods on Controllers).

The most complex HTTP handler is the one that handles PUT requests for reservations. Clients use this action when they want to make changes to a restaurant reservation.

The action method actually invoked by an HTTP request is this Put method:

[HttpPut("restaurants/{restaurantId}/reservations/{id}")]
public async Task<ActionResult> Put(
    int restaurantId,
    string id,
    ReservationDto dto)
{
    if (dto is null)
        throw new ArgumentNullException(nameof(dto));
    if (!Guid.TryParse(id, out var rid))
        return new NotFoundResult();
 
    Reservation? reservation = dto.Validate(rid);
    if (reservation is null)
        return new BadRequestResult();
 
    var restaurant = await RestaurantDatabase
        .GetRestaurant(restaurantId).ConfigureAwait(false);
    if (restaurant is null)
        return new NotFoundResult();
 
    return
        await TryUpdate(restaurant, reservation).ConfigureAwait(false);
}

Since I, for pedagogical reasons, wanted to fit each method inside an 80x24 box, I made a few somewhat unnatural design choices. The above code is one of them. While I don't consider it completely indefensible, this method does a bit of up-front input validation and verification, and then delegates execution to the TryUpdate method.

This may seem all fine and dandy until you realize that the only caller of TryUpdate is that Put method. A similar thing happens in TryUpdate: It calls a method that has only that one caller. We may try to inline those two methods to see if we can spot the Impureim Sandwich.

Inlined Transaction Script #

Inlining those two methods leave us with a larger, Transaction Script-like entry point:

[HttpPut("restaurants/{restaurantId}/reservations/{id}")]
public async Task<ActionResult> Put(
    int restaurantId,
    string id,
    ReservationDto dto)
{
    if (dto is null)
        throw new ArgumentNullException(nameof(dto));
    if (!Guid.TryParse(id, out var rid))
        return new NotFoundResult();
 
    Reservation? reservation = dto.Validate(rid);
    if (reservation is null)
        return new BadRequestResult();
 
    var restaurant = await RestaurantDatabase
        .GetRestaurant(restaurantId).ConfigureAwait(false);
    if (restaurant is null)
        return new NotFoundResult();
 
    using var scope = new TransactionScope(
        TransactionScopeAsyncFlowOption.Enabled);
 
    var existing = await Repository
        .ReadReservation(restaurant.Id, reservation.Id)
        .ConfigureAwait(false);
    if (existing is null)
        return new NotFoundResult();
 
    var reservations = await Repository
        .ReadReservations(restaurant.Id, reservation.At)
        .ConfigureAwait(false);
    reservations =
        reservations.Where(r => r.Id != reservation.Id).ToList();
    var now = Clock.GetCurrentDateTime();
    var ok = restaurant.MaitreD.WillAccept(
        now,
        reservations,
        reservation);
    if (!ok)
        return NoTables500InternalServerError();
 
    await Repository.Update(restaurant.Id, reservation)
        .ConfigureAwait(false);
 
    scope.Complete();
 
    return new OkObjectResult(reservation.ToDto());
}

While I've definitely seen longer methods in the wild, this variation is already so big that it no longer fits on my laptop screen. I have to scroll up and down to read the whole thing. When looking at the bottom of the method, I have to remember what was at the top, because I can no longer see it.

A major point of Code That Fits in Your Head is that what limits programmer productivity is human cognition. If you have to scroll your screen because you can't see the whole method at once, does that fit in your brain? Chances are, it doesn't.

Can you spot the Impureim Sandwich now?

If you can't, that's understandable. It's not really clear because there's quite a few small decisions being made in this code. You could argue, for example, that this decision is referentially transparent:

if (existing is null)
    return new NotFoundResult();

These two lines of code are deterministic and have no side effects. The branch only returns a NotFoundResult when existing is null. Additionally, these two lines of code are surrounded by impure actions both before and after. Is this the Sandwich, then?

No, it's not. This is how idiomatic imperative code looks. To borrow a diagram from another article, pure and impure code is interleaved without discipline:

Even so, the above Put method implements the Functional Core, Imperative Shell architecture. The Put method is the Imperative Shell, but where's the Functional Core?

Shell perspective #

One thing to be aware of is that when looking at the Imperative Shell code, the Functional Core is close to invisible. This is because it's typically only a single function call.

In the above Put method, this is the Functional Core:

var ok = restaurant.MaitreD.WillAccept(
    now,
    reservations,
    reservation);
if (!ok)
    return NoTables500InternalServerError();

It's only a few lines of code, and had I not given myself the constraint of staying within an 80 character line width, I could have instead laid it out like this and inlined the ok flag:

if (!restaurant.MaitreD.WillAccept(now, reservations, reservation))
    return NoTables500InternalServerError();

Now that I try this, in fact, it turns out that this actually still stays within 80 characters. To be honest, I don't know exactly why I had that former code instead of this, but perhaps I found the latter alternative too dense. Or perhaps I simply didn't think of it. Code is rarely perfect. Usually when I revisit a piece of code after having been away from it for some time, I find some thing that I want to change.

In any case, that's beside the point. What matters here is that when you're looking through the Imperative Shell code, the Functional Core looks insignificant. Blink and you'll miss it. Even if we ignore all the other small pure decisions (the if statements) and pretend that we already have an Impureim Sandwich, from this viewpoint, the architecture looks like this:

It's tempting to ask, then: What's all the fuss about? Why even bother?

This is a natural experience for a code reader. After all, if you don't know a code base well, you often start at the entry point to try to understand how the application handles a certain stimulus. Such as an HTTP PUT request. When you do that, you see all of the Imperative Shell code before you see the Functional Core code. This could give you the wrong impression about the balance of responsibility.

After all, code like the above Put method has inlined most of the impure code so that it's right in your face. Granted, there's still some code hiding behind, say, Repository.ReadReservations, but a substantial fraction of the imperative code is visible in the method.

On the other hand, the Functional Core is just a single function call. If we inlined all of that code, too, the picture might rather look like this:

This obviously depends on the de-facto ratio of pure to imperative code. In any case, inlining the pure code is a thought experiment only, because the whole point of functional architecture is that a referentially transparent function fits in your head. Regardless of the complexity and amount of code hiding behind that MaitreD.WillAccept function, the return value is equal to the function call. It's the ultimate abstraction.

Standard combinators #

As I've already suggested, the inlined Put method looks like a Transaction Script. The cyclomatic complexity fortunately hovers on the magical number seven, and branching is exclusively organized around Guard Clauses. Apart from that, there are no nested if statements or for loops.

Apart from the Guard Clauses, this mostly looks like a procedure that runs in a straight line from top to bottom. The exception is all those small conditionals that may cause the procedure to exit prematurely. Conditions like this:

if (!Guid.TryParse(id, out var rid))
    return new NotFoundResult();

if (reservation is null)
    return new BadRequestResult();

Such checks occur throughout the method. Each of them are actually small pure islands amidst all the imperative code, but each is ad hoc. Each checks if it's possible for the procedure to continue, and returns a kind of error value if it decides that it's not.

Is there a way to model such 'derailments' from the main flow?

If you've ever encountered Scott Wlaschin's Railway Oriented Programming you may already see where this is going. Railway-oriented programming is a fantastic metaphor, because it gives you a way to visualize that you have, indeed, a main track, but then you have a side track that you may shuffle some trains too. And once the train is on the side track, it can't go back to the main track.

That's how the Either monad works. Instead of all those ad-hoc if statements, we should be able to replace them with what we may call standard combinators. The most important of these combinators is monadic bind. Composing a Transaction Script like Put with standard combinators will 'hide away' those small decisions, and make the Sandwich nature more apparent.

If we had had pure code, we could just have composed Either-valued functions. Unfortunately, most of what's going on in the Put method happens in a Task-based context. Thankfully, Either is one of those monads that nest well, implying that we can turn the combination into a composed TaskEither monad. The linked article shows the core TaskEither SelectMany implementations.

The way to encode all those small decisions between 'main track' or 'side track', then, is to wrap 'naked' values in the desired Task<Either<L, R>> container:

Task.FromResult(id.TryParseGuid().OnNull((ActionResult)new NotFoundResult()))

This little code snippet makes use of a few small building blocks that we also need to introduce. First, .NET's standard TryParse APIs don't, compose, but since they're isomorphic to Maybe-valued functions, you can write an adapter like this:

public static Guid? TryParseGuid(this string candidate)
{
    if (Guid.TryParse(candidate, out var guid))
        return guid;
    else
        return null;
}

In this code base, I treat nullable reference types as equivalent to the Maybe monad, but if your language doesn't have that feature, you can use Maybe instead.

To implement the Put method, however, we don't want nullable (or Maybe) values. We need Either values, so we may introduce a natural transformation:

public static Either<L, R> OnNull<L, R>(this R? candidate, L left) where R : struct
{
    if (candidate.HasValue)
        return Right<L, R>(candidate.Value);
 
    return Left<L, R>(left);
}

In Haskell one might just make use of the built-in Maybe catamorphism:

ghci> maybe (Left "boo!") Right $ Just 123
Right 123
ghci> maybe (Left "boo!") Right $ Nothing
Left "boo!"

Such conversions from Maybe to Either hover just around the Fairbairn threshold, but since we are going to need it more than once, it makes sense to add a specialized OnNull transformation to the C# code base. The one shown here handles nullable value types, but the code base also includes an overload that handles nullable reference types. It's almost identical.

Support for query syntax #

There's more than one way to consume monadic values in C#. While many C# developers like LINQ, most seem to prefer the familiar method call syntax; that is, just call the Select, SelectMany, and Where methods as the normal extension methods they are. Another option, however, is to use query syntax. This is what I'm aiming for here, since it'll make it easier to spot the Impureim Sandwich.

You'll see the entire sandwich later in the article. Before that, I'll highlight details and explain how to implement them. You can always scroll down to see the end result, and then scroll back here, if that's more to your liking.

The sandwich starts by parsing the id into a GUID using the above building blocks:

var sandwich =
    from rid in Task.FromResult(id.TryParseGuid().OnNull((ActionResult)new NotFoundResult()))

It then immediately proceeds to Validate (parse, really) the dto into a proper Domain Model:

from reservation in dto.Validate(rid).OnNull((ActionResult)new BadRequestResult())

Notice that the second from expression doesn't wrap the result with Task.FromResult. How does that work? Is the return value of dto.Validate already a Task? No, this works because I added 'degenerate' SelectMany overloads:

public static Task<Either<L, R1>> SelectMany<L, R, R1>(
    this Task<Either<L, R>> source,
    Func<R, Either<L, R1>> selector)
{
    return source.SelectMany(x => Task.FromResult(selector(x)));
}
 
public static Task<Either<L, R1>> SelectMany<L, U, R, R1>(
    this Task<Either<L, R>> source,
    Func<R, Either<L, U>> k,
    Func<R, U, R1> s)
{
    return source.SelectMany(x => k(x).Select(y => s(x, y)));
}

Notice that the selector only produces an Either<L, R1> value, rather than Task<Either<L, R1>>. This allows query syntax to 'pick up' the previous value (rid, which is 'really' a Task<Either<ActionResult, Guid>>) and continue with a function that doesn't produce a Task, but rather just an Either value. The first of these two overloads then wraps that Either value and wraps it with Task.FromResult. The second overload is just the usual ceremony that enables query syntax.

Why, then, doesn't the sandwich use the same trick for rid? Why does it explicitly call Task.FromResult?

As far as I can tell, this is because of type inference. It looks as though the C# compiler infers the monad's type from the first expression. If I change the first expression to

from rid in id.TryParseGuid().OnNull((ActionResult)new NotFoundResult())

the compiler thinks that the query expression is based on Either<L, R>, rather than Task<Either<L, R>>. This means that once we run into the first Task value, the entire expression no longer works.

By explicitly wrapping the first expression in a Task, the compiler correctly infers the monad we'd like it to. If there's a more elegant way to do this, I'm not aware of it.

Values that don't fail #

The sandwich proceeds to query various databases, using the now-familiar OnNull combinators to transform nullable values to Either values.

from restaurant in RestaurantDatabase
    .GetRestaurant(restaurantId)
    .OnNull((ActionResult)new NotFoundResult())
from existing in Repository
    .ReadReservation(restaurant.Id, reservation.Id)
    .OnNull((ActionResult)new NotFoundResult())

This works like before because both GetRestaurant and ReadReservation are queries that may fail to return a value. Here's the interface definition of ReadReservation:

Task<Reservation?> ReadReservation(int restaurantId, Guid id);

Notice the question mark that indicates that the result may be null.

The GetRestaurant method is similar.

The next query that the sandwich has to perform, however, is different. The return type of the ReadReservations method is Task<IReadOnlyCollection<Reservation>>. Notice that the type contained in the Task is not nullable. Barring database connection errors, this query can't fail. If it finds no data, it returns an empty collection.

Since the value isn't nullable, we can't use OnNull to turn it into a Task<Either<L, R>> value. We could try to use the Right creation function for that.

public static Either<L, R> Right<L, R>(R right)
{
    return Either<L, R>.Right(right);
}

This works, but is awkward:

from reservations in Repository
    .ReadReservations(restaurant.Id, reservation.At)
    .Traverse(rs => Either.Right<ActionResult, IReadOnlyCollection<Reservation>>(rs))

The problem with calling Either.Right is that while the compiler can infer which type to use for R, it doesn't know what the L type is. Thus, we have to tell it, and we can't tell it what L is without also telling it what R is. Even though it already knows that.

In such scenarios, the F# compiler can usually figure it out, and GHC always can (unless you add some exotic language extensions to your code). C# doesn't have any syntax that enables you to tell the compiler about only the type that it doesn't know about, and let it infer the rest.

All is not lost, though, because there's a little trick you can use in cases such as this. You can let the C# compiler infer the R type so that you only have to tell it what L is. It's a two-stage process. First, define an extension method on R:

public static RightBuilder<R> ToRight<R>(this R right)
{
    return new RightBuilder<R>(right);
}

The only type argument on this ToRight method is R, and since the right parameter is of the type R, the C# compiler can always infer the type of R from the type of right.

What's RightBuilder<R>? It's this little auxiliary class:

public sealed class RightBuilder<R>
{
    private readonly R right;
 
    public RightBuilder(R right)
    {
        this.right = right;
    }
 
    public Either<L, R> WithLeft<L>()
    {
        return Either.Right<L, R>(right);
    }
}

The code base for Code That Fits in Your Head was written on .NET 3.1, but today you could have made this a record instead. The only purpose of this class is to break the type inference into two steps so that the R type can be automatically inferred. In this way, you only need to tell the compiler what the L type is.

from reservations in Repository
    .ReadReservations(restaurant.Id, reservation.At)
    .Traverse(rs => rs.ToRight().WithLeft<ActionResult>())

As indicated, this style of programming isn't language-neutral. Even if you find this little trick neat, I'd much rather have the compiler just figure it out for me. The entire sandwich query expression is already defined as working with Task<Either<ActionResult, R>>, and the L type can't change like the R type can. Functional compilers can figure this out, and while I intend this article to show object-oriented programmers how functional programming sometimes work, I don't wish to pretend that it's a good idea to write code like this in C#. I've covered that ground already.

Not surprisingly, there's a mirror-image ToLeft/WithRight combo, too.

Working with Commands #

The ultimate goal with the Put method is to modify a row in the database. The method to do that has this interface definition:

Task Update(int restaurantId, Reservation reservation);

I usually call that non-generic Task class for 'asynchronous void' when explaining it to non-C# programmers. The Update method is an asynchronous Command.

Task and void aren't legal values for use with LINQ query syntax, so you have to find a way to work around that limitation. In this case I defined a local helper method to make it look like a Query:

async Task<Reservation> RunUpdate(int restaurantId, Reservation reservation, TransactionScope scope)
{
    await Repository.Update(restaurantId, reservation).ConfigureAwait(false);
    scope.Complete();
    return reservation;
}

It just echoes back the reservation parameter once the Update has completed. This makes it composable in the larger query expression.

You'll probably not be surprised when I tell you that both F# and Haskell handle this scenario gracefully, without requiring any hoop-jumping.

Full sandwich #

Those are all the building block. Here's the full sandwich definition, colour-coded like the examples in Impureim sandwich.

Task<Either<ActionResult, OkObjectResult>> sandwich =
    from rid in Task.FromResult(
        id.TryParseGuid().OnNull((ActionResult)new NotFoundResult()))
    from reservation in
        dto.Validate(rid).OnNull(
            (ActionResult)new BadRequestResult())
 
    from restaurant in RestaurantDatabase
            .GetRestaurant(restaurantId)
        .OnNull((ActionResult)new NotFoundResult())
    from existing in Repository
        .ReadReservation(restaurant.Id, reservation.Id)
        .OnNull((ActionResult)new NotFoundResult())
    from reservations in Repository
        .ReadReservations(restaurant.Id, reservation.At)
        .Traverse(rs => rs.ToRight().WithLeft<ActionResult>())
    let now = Clock.GetCurrentDateTime()
 
    let reservations2 =
            reservations.Where(r => r.Id != reservation.Id)
    let ok = restaurant.MaitreD.WillAccept(
        now,
        reservations2,
        reservation)
    from reservation2 in
        ok 
            ? reservation.ToRight().WithLeft<ActionResult>()
            : NoTables500InternalServerError().ToLeft().WithRight<Reservation>()
 
    from reservation3 in 
        RunUpdate(restaurant.Id, reservation2, scope)
        .Traverse(r => r.ToRight().WithLeft<ActionResult>())
    select new OkObjectResult(reservation3.ToDto());

As is evident from the colour-coding, this isn't quite a sandwich. The structure is honestly more accurately depicted like this:

As I've previously argued, while the metaphor becomes strained, this still works well as a functional-programming architecture.

As defined here, the sandwich value is a Task that must be awaited.

Either<ActionResult, OkObjectResult> either = await sandwich.ConfigureAwait(false);
return either.Match(x => x, x => x);

By awaiting the task, we get an Either value. The Put method, on the other hand, must return an ActionResult. How do you turn an Either object into a single object?

By pattern matching on it, as the code snippet shows. The L type is already an ActionResult, so we return it without changing it. If C# had had a built-in identity function, I'd used that, but idiomatically, we instead use the x => x lambda expression.

The same is the case for the R type, because OkObjectResult inherits from ActionResult. The identity expression automatically performs the type conversion for us.

This, by the way, is a recurring pattern with Either values that I run into in all languages. You've essentially computed an Either<T, T>, with the same type on both sides, and now you just want to return whichever T value is contained in the Either value. You'd think this is such a common pattern that Haskell has a nice abstraction for it, but even Hoogle fails to suggest a commonly-accepted function that does this. Apparently, either id id is considered below the Fairbairn threshold, too.

Conclusion #

This article presents an example of a non-trivial Impureim Sandwich. When I introduced the pattern, I gave a few examples. I'd deliberately chosen these examples to be simple so that they highlighted the structure of the idea. The downside of that didactic choice is that some commenters found the examples too simplistic. Therefore, I think that there's value in going through more complex examples.

The code base that accompanies Code That Fits in Your Head is complex enough that it borders on the realistic. It was deliberately written that way, and since I assume that the code base is familiar to readers of the book, I thought it'd be a good resource to show how an Impureim Sandwich might look. I explicitly chose to refactor the Put method, since it's easily the most complicated process in the code base.

The benefit of that code base is that it's written in a programming language that reach a large audience. Thus, for the reader curious about functional programming I thought that this could also be a useful introduction to some intermediate concepts.

As I've commented along the way, however, I wouldn't expect anyone to write production C# code like this. If you're able to do this, you're also able to do it in a language better suited for this programming paradigm.

This blog is totally free, but if you like it, please consider supporting it.

Implementation and usage mindsets

2024-12-09T21:45:00+00:00

A one-dimensional take on the enduring static-versus-dynamic debate.

It recently occurred to me that one possible explanation for the standing, and probably never-ending, debate about static versus dynamic types may be that each camp have disjoint perspectives on the kinds of problems their favourite languages help them solve. In short, my hypothesis is that perhaps lovers of dynamically-typed languages often approach a problem from an implementation mindset, whereas proponents of static types emphasize usage.

I'll expand on this idea here, and then provide examples in two subsequent articles.

Background #

For years I've struggled to understand 'the other side'. While I'm firmly in the statically typed camp, I realize that many highly skilled programmers and thought leaders enjoy, or get great use out of, dynamically typed languages. This worries me, because it might indicate that I'm stuck in a local maximum.

In other words, just because I, personally, prefer static types, it doesn't follow that static types are universally better than dynamic types.

In reality, it's probably rather the case that we're dealing with a false dichotomy, and that the problem is really multi-dimensional.

"Let me stop you right there: I don't think there is a real dynamic typing versus static typing debate.

"What such debates normally are is language X vs language Y debates (where X happens to be dynamic and Y happens to be static)."

Kevlin Henney

Even so, I can't help thinking about such things. Am I missing something?

For the past few years, I've dabbled with Python to see what writing in a popular dynamically typed language is like. It's not a bad language, and I can clearly see how it's attractive. Even so, I'm still frustrated every time I return to some Python code after a few weeks or more. The lack of static types makes it hard for me to pick up, or revisit, old code.

A question of perspective? #

Whenever I run into a difference of opinion, I often interpret it as a difference in perspective. Perhaps it's my academic background as an economist, but I consider it a given that people have different motivations, and that incentives influence actions.

A related kind of analysis deals with problem definitions. Are we even trying to solve the same problem?

I've discussed such questions before, but in a different context. Here, it strikes me that perhaps programmers who gravitate toward dynamically typed languages are focused on another problem than the other group.

Again, I'd like to emphasize that I don't consider the world so black and white in reality. Some developers straddle the two camps, and as the above Kevlin Henney quote suggests, there really aren't only two kinds of languages. C and Haskell are both statically typed, but the similarities stop there. Likewise, I don't know if it's fair to put JavaScript and Clojure in the same bucket.

That said, I'd still like to offer the following hypothesis, in the spirit that although all models are wrong, some are useful.

The idea is that if you're trying to solve a problem related to implementation, dynamically typed languages may be more suitable. If you're trying to implement an algorithm, or even trying to invent one, a dynamic language seems useful. One year, I did a good chunk of Advent of Code in Python, and didn't find it harder than in Haskell. (I ultimately ran out of steam for reasons unrelated to Python.)

On the other hand, if your main focus may be usage of your code, perhaps you'll find a statically typed language more useful. At least, I do. I can use the static type system to communicate how my APIs work. How to instantiate my classes. How to call my functions. How return values are shaped. In other words, the preconditions, invariants, and postconditions of my reusable code: Encapsulation.

Examples #

Some examples may be in order. In the next two articles, I'll first examine how easy it is to implement an algorithm in various programming languages. Then I'll discuss how to encapsulate that algorithm.

The articles will both discuss the rod-cutting problem from Introduction to Algorithms, but I'll introduce the problem in the next article.

Conclusion #

I'd be naive if I believed that a single model can fully explain why some people prefer dynamically typed languages, and others rather like statically typed languages. Even so, suggesting a model helps me understand how to analyze problems.

My hypothesis is that dynamically typed languages may be suitable for implementing algorithms, whereas statically typed languages offer better encapsulation.

This may be used as a heuristic for 'picking the right tool for the job'. If I need to suss out an algorithm, perhaps I should do it in Python. If, on the other hand, I need to publish a reusable library, perhaps Haskell is a better choice.

Next: Implementing rod-cutting.

This blog is totally free, but if you like it, please consider supporting it.

Short-circuiting an asynchronous traversal

2024-12-02T09:32:00+00:00

Another C# example.

This article is a continuation of an earlier post about refactoring a piece of imperative code to a functional architecture. It all started with a Stack Overflow question, but read the previous article, and you'll be up to speed.

Imperative outset #

To begin, consider this mostly imperative code snippet:

var storedItems = new List<ShoppingListItem>();
var failedItems = new List<ShoppingListItem>();
var state = (storedItems, failedItems, hasError: false);
foreach (var item in itemsToUpdate)
{
    OneOf<ShoppingListItem, NotFound, Error> updateResult = await UpdateItem(item, dbContext);
    state = updateResult.Match<(List<ShoppingListItem>, List<ShoppingListItem>, bool)>(
        storedItem => { storedItems.Add(storedItem); return state;  },
        notFound => { failedItems.Add(item); return state; },
        error => { state.hasError = true; return state; }
        );
    if (state.hasError)
        return Results.BadRequest();
}
 
await dbContext.SaveChangesAsync();
 
return Results.Ok(new BulkUpdateResult([.. storedItems], [.. failedItems]));

I'll recap a few points from the previous article. Apart from one crucial detail, it's similar to the other post. One has to infer most of the types and APIs, since the original post didn't show more code than that. If you're used to engaging with Stack Overflow questions, however, it's not too hard to figure out what most of the moving parts do.

The most non-obvious detail is that the code uses a library called OneOf, which supplies general-purpose, but rather abstract, sum types. Both the container type OneOf, as well as the two indicator types NotFound and Error are defined in that library.

The Match method implements standard Church encoding, which enables the code to pattern-match on the three alternative values that UpdateItem returns.

One more detail also warrants an explicit description: The itemsToUpdate object is an input argument of the type IEnumerable<ShoppingListItem>.

The major difference from before is that now the update process short-circuits on the first Error. If an error occurs, it stops processing the rest of the items. In that case, it now returns Results.BadRequest(), and it doesn't save the changes to dbContext.

The implementation makes use of mutable state and undisciplined I/O. How do you refactor it to a more functional design?

Short-circuiting traversal #

The standard Traverse function isn't lazy, or rather, it does consume the entire input sequence. Even various Haskell data structures I investigated do that. And yes, I even tried to traverse ListT. If there's a data structure that you can traverse with deferred execution of I/O-bound actions, I'm not aware of it.

That said, all is not lost, but you'll need to implement a more specialized traversal. While consuming the input sequence, the function needs to know when to stop. It can't do that on just any IEnumerable<T>, because it has no information about T.

If, on the other hand, you specialize the traversal to a sequence of items with more information, you can stop processing if it encounters a particular condition. You could generalize this to, say, IEnumerable<Either<L, R>>, but since I already have the OneOf library in scope, I'll use that, instead of implementing or pulling in a general-purpose Either data type.

In fact, I'll just use a three-way OneOf type compatible with the one that UpdateItem returns.

internal static async Task<IEnumerable<OneOf<T1, T2, Error>>> Sequence<T1, T2>(
    this IEnumerable<Task<OneOf<T1, T2, Error>>> tasks)
{
    var results = new List<OneOf<T1, T2, Error>>();
    foreach (var task in tasks)
    {
        var result = await task;
        results.Add(result);
        if (result.IsT2)
            break;
    }
    return results;
}

This implementation doesn't care what T1 or T2 is, so they're free to be ShoppingListItem and NotFound. The third type argument, on the other hand, must be Error.

The if conditional looks a bit odd, but as I wrote, the types that ship with the OneOf library have rather abstract APIs. A three-way OneOf value comes with three case tests called IsT0, IsT1, and IsT2. Notice that the library uses a zero-indexed naming convention for its type parameters. IsT2 returns true if the value is the third kind, in this case Error. If a task turns out to produce an Error, the Sequence method adds that one error, but then stops processing any remaining items.

Some readers may complain that the entire implementation of Sequence is imperative. It hardly matters that much, since the mutation doesn't escape the method. The behaviour is as functional as it's possible to make it. It's fundamentally I/O-bound, so we can't consider it a pure function. That said, if we hypothetically imagine that all the tasks are deterministic and have no side effects, the Sequence function does become a pure function when viewed as a black box. From the outside, you can't tell that the implementation is imperative.

It is possible to implement Sequence in a proper functional style, and it might make a good exercise. I think, however, that it'll be difficult in C#. In F# or Haskell I'd use recursion, and while you can do that in C#, I admit that I've lost sight of whether or not tail recursion is supported by the C# compiler.

Be that as it may, the traversal implementation doesn't change.

internal static Task<IEnumerable<OneOf<TResult, T2, Error>>> Traverse<T1, T2, TResult>(
    this IEnumerable<T1> items,
    Func<T1, Task<OneOf<TResult, T2, Error>>> selector)
{
    return items.Select(selector).Sequence();
}

You can now Traverse the itemsToUpdate:

// Impure
IEnumerable<OneOf<ShoppingListItem, NotFound<ShoppingListItem>, Error>> results =
    await itemsToUpdate.Traverse(item => UpdateItem(item, dbContext));

As the // Impure comment may suggest, this constitutes the first impure layer of an Impureim Sandwich.

Aggregating the results #

Since the above statement awaits the traversal, the results object is a 'pure' object that can be passed to a pure function. This does, however, assume that ShoppingListItem is an immutable object.

The next step must collect results and NotFound-related failures, but contrary to the previous article, it must short-circuit if it encounters an Error. This again suggests an Either-like data structure, but again I'll repurpose a OneOf container. I'll start by defining a seed for an aggregation (a left fold).

var seed =
    OneOf<(IEnumerable<ShoppingListItem>, IEnumerable<ShoppingListItem>), Error>
        .FromT0(([], []));

This type can be either a tuple or an error. The .NET tendency is often to define an explicit Result<TSuccess, TFailure> type, where TSuccess is defined to the left of TFailure. This, for example, is how F# defines Result types, and other .NET libraries tend to emulate that design. That's also what I've done here, although I admit that I'm regularly confused when going back and forth between F# and Haskell, where the Right case is idiomatically considered to indicate success.

As already discussed, OneOf follows a zero-indexed naming convention for type parameters, so FromT0 indicates the first (or leftmost) case. The seed is thus initialized with a tuple that contains two empty sequences.

As in the previous article, you can now use the Aggregate method to collect the result you want.

OneOf<BulkUpdateResult, Error> result = results
    .Aggregate(
        seed,
        (state, result) =>
            result.Match(
                storedItem => state.MapT0(
                    t => (t.Item1.Append(storedItem), t.Item2)),
                notFound => state.MapT0(
                    t => (t.Item1, t.Item2.Append(notFound.Item))),
                e => e))
    .MapT0(t => new BulkUpdateResult(t.Item1.ToArray(), t.Item2.ToArray()));

This expression is a two-step composition. I'll get back to the concluding MapT0 in a moment, but let's first discuss what happens in the Aggregate step. Since the state is now a discriminated union, the big lambda expression not only has to Match on the result, but it also has to deal with the two mutually exclusive cases in which state can be.

Although it comes third in the code listing, it may be easiest to explain if we start with the error case. Keep in mind that the seed starts with the optimistic assumption that the operation is going to succeed. If, however, we encounter an error e, we now switch the state to the Error case. Once in that state, it stays there.

The two other result cases map over the first (i.e. the success) case, appending the result to the appropriate sequence in the tuple t. Since these expressions map over the first (zero-indexed) case, these updates only run as long as the state is in the success case. If the state is in the error state, these lambda expressions don't run, and the state doesn't change.

After having collected the tuple of sequences, the final step is to map over the success case, turning the tuple t into a BulkUpdateResult. That's what MapT0 does: It maps over the first (zero-indexed) case, which contains the tuple of sequences. It's a standard functor projection.

Saving the changes and returning the results #

The final, impure step in the sandwich is to save the changes and return the results:

// Impure
return await result.Match(
    async bulkUpdateResult =>
    {
        await dbContext.SaveChangesAsync();
        return Results.Ok(bulkUpdateResult);
    },
    _ => Task.FromResult(Results.BadRequest()));

Note that it only calls dbContext.SaveChangesAsync() in case the result is a success.

Accumulating the bulk-update result #

So far, I've assumed that the final BulkUpdateResult class is just a simple immutable container without much functionality. If, however, we add some copy-and-update functions to it, we can use that to aggregate the result, instead of an anonymous tuple.

internal BulkUpdateResult Store(ShoppingListItem item) =>
    new([.. StoredItems, item], FailedItems);
 
internal BulkUpdateResult Fail(ShoppingListItem item) =>
    new(StoredItems, [.. FailedItems, item]);

I would have personally preferred the name NotFound instead of Fail, but I was going with the original post's failedItems terminology, and I thought that it made more sense to call a method Fail when it adds to a collection called FailedItems.

Adding these two instance methods to BulkUpdateResult simplifies the composing code:

// Pure
OneOf<BulkUpdateResult, Error> result = results
    .Aggregate(
        OneOf<BulkUpdateResult, Error>.FromT0(new([], [])),
        (state, result) =>
            result.Match(
                storedItem => state.MapT0(bur => bur.Store(storedItem)),
                notFound => state.MapT0(bur => bur.Fail(notFound.Item)),
                e => e));

This variation starts with an empty BulkUpdateResult and then uses Store or Fail as appropriate to update the state. The final, impure step of the sandwich remains the same.

Conclusion #

It's a bit more tricky to implement a short-circuiting traversal than the standard traversal. You can, still, implement a specialized Sequence or Traverse method, but it requires that the input stream carries enough information to decide when to stop processing more items. In this article, I used a specialized three-way union, but you could generalize this to use a standard Either or Result type.

This blog is totally free, but if you like it, please consider supporting it.

Nested monads

2024-11-25T07:31:00+00:00

You can stack some monads in such a way that the composition is also a monad.

This article is part of a series of articles about functor relationships. In a previous article you learned that nested functors form a functor. You may have wondered if monads compose in the same way. Does a monad nested in a monad form a monad?

As far as I know, there's no universal rule like that, but some monads compose well. Fortunately, it's been my experience that the combinations that you need in practice are among those that exist and are well-known. In a Haskell context, it's often the case that you need to run some kind of 'effect' inside IO. Perhaps you want to use Maybe or Either nested within IO.

In .NET, you may run into a similar need to compose task-based programming with an effect. This happens more often in F# than in C#, since F# comes with other native monads (option and Result, to name the most common).

Abstract shape #

You'll see some real examples in a moment, but as usual it helps to outline what it is that we're looking for. Imagine that you have a monad. We'll call it F in keeping with tradition. In this article series, you've seen how two or more functors compose. When discussing the abstract shapes of things, we've typically called our two abstract functors F and G. I'll stick to that naming scheme here, because monads are functors (that you can flatten).

Now imagine that you have a value that stacks two monads: F<G<T>>. If the inner monad G is the 'right' kind of monad, that configuration itself forms a monad.

In the diagram, I've simply named the combined monad FG, which is a naming strategy I've seen in the real world, too: TaskResult, etc.

As I've already mentioned, if there's a general theorem that says that this is always possible, I'm not aware of it. To the contrary, I seem to recall reading that this is distinctly not the case, but the source escapes me at the moment. One hint, though, is offered in the documentation of Data.Functor.Compose:

"The composition of applicative functors is always applicative, but the composition of monads is not always a monad."

Thankfully, the monads that you mostly need to compose do, in fact, compose. They include Maybe, Either, State, Reader, and Identity (okay, that one maybe isn't that useful). In other words, any monad F that composes with e.g. Maybe, that is, F<Maybe<T>>, also forms a monad.

Notice that it's the 'inner' monad that determines whether composition is possible. Not the 'outer' monad.

For what it's worth, I'm basing much of this on my personal experience, which was again helpfully guided by Control.Monad.Trans.Class. I don't, however, wish to turn this article into an article about monad transformers, because if you already know Haskell, you can read the documentation and look at examples. And if you don't know Haskell, the specifics of monad transformers don't readily translate to languages like C# or F#.

The conclusions do translate, but the specific language mechanics don't.

Let's look at some common examples.

TaskMaybe monad #

We'll start with a simple, yet realistic example. The article Asynchronous Injection shows a simple operation that involves reading from a database, making a decision, and potentially writing to the database. The final composition, repeated here for your convenience, is an asynchronous (that is, Task-based) process.

return await Repository.ReadReservations(reservation.Date)
    .Select(rs => maîtreD.TryAccept(rs, reservation))
    .SelectMany(m => m.Traverse(Repository.Create))
    .Match(InternalServerError("Table unavailable"), Ok);

The problem here is that TryAccept returns Maybe<Reservation>, but since the overall workflow already 'runs in' an asynchronous monad (Task), the monads are now nested as Task<Maybe<T>>.

The way I dealt with that issue in the above code snippet was to rely on a traversal, but it's actually an inelegant solution. The way that the SelectMany invocation maps over the Maybe<Reservation> m is awkward. Instead of composing a business process, the scaffolding is on display, so to speak. Sometimes this is unavoidable, but at other times, there may be a better way.

In my defence, when I wrote that article in 2019 I had another pedagogical goal than teaching nested monads. It turns out, however, that you can rewrite the business process using the Task<Maybe<T>> stack as a monad in its own right.

A monad needs two functions: return and either bind or join. In C# or F#, you can often treat return as 'implied', in the sense that you can always wrap new Maybe<T> in a call to Task.FromResult. You'll see that in a moment.

While you can be cavalier about monadic return, you'll need to explicitly implement either bind or join. In this case, it turns out that the sample code base already had a SelectMany implementation:

public static async Task<Maybe<TResult>> SelectMany<T, TResult>(
    this Task<Maybe<T>> source,
    Func<T, Task<Maybe<TResult>>> selector)
{
    Maybe<T> m = await source;
    return await m.Match(
        nothing: Task.FromResult(new Maybe<TResult>()),
        just: x => selector(x));
}

The method first awaits the Maybe value, and then proceeds to Match on it. In the nothing case, you see the implicit return being used. In the just case, the SelectMany method calls selector with whatever x value was contained in the Maybe object. The result of calling selector already has the desired type Task<Maybe<TResult>>, so the implementation simply returns that value without further ado.

This enables you to rewrite the SelectMany call in the business process so that it instead looks like this:

return await Repository.ReadReservations(reservation.Date)
    .Select(rs => maîtreD.TryAccept(rs, reservation))
    .SelectMany(r => Repository.Create(r).Select(i => new Maybe<int>(i)))
    .Match(InternalServerError("Table unavailable"), Ok);

At first glance, it doesn't look like much of an improvement. To be sure, the lambda expression within the SelectMany method no longer operates on a Maybe value, but rather on the Reservation Domain Model r. On the other hand, we're now saddled with that graceless Select(i => new Maybe<int>(i)).

Had this been Haskell, we could have made this more succinct by eta reducing the Maybe case constructor and used the <$> infix operator instead of fmap; something like Just <$> create r. In C#, on the other hand, we can do something that Haskell doesn't allow. We can overload the SelectMany method:

public static Task<Maybe<TResult>> SelectMany<T, TResult>(
    this Task<Maybe<T>> source,
    Func<T, Task<TResult>> selector)
{
    return source.SelectMany(x => selector(x).Select(y => new Maybe<TResult>(y)));
}

This overload generalizes the 'pattern' exemplified by the above business process composition. Instead of a specific method call, it now works with any selector function that returns Task<TResult>. Since selector only returns a Task<TResult> value, and not a Task<Maybe<TResult>> value, as actually required in this nested monad, the overload has to map (that is, Select) the result by wrapping it in a new Maybe<TResult>.

This now enables you to improve the business process composition to something more readable.

return await Repository.ReadReservations(reservation.Date)
    .Select(rs => maîtreD.TryAccept(rs, reservation))
    .SelectMany(Repository.Create)
    .Match(InternalServerError("Table unavailable"), Ok);

It even turned out to be possible to eta reduce the lambda expression instead of the (also valid, but more verbose) r => Repository.Create(r).

If you're interested in the sample code, I've pushed a branch named use-monad-stack to the GitHub repository.

Not surprisingly, the F# bind function is much terser:

let bind f x = async {
    match! x with
    | Some x' -> return! f x'
    | None -> return None }

You can find that particular snippet in the code base that accompanies the article Refactoring registration flow to functional architecture, although as far as I can tell, it's not actually in use in that code base. I probably just added it because I could.

You can find Haskell examples of combining MaybeT with IO in various articles on this blog. One of them is Dependency rejection.

TaskResult monad #

A similar, but slightly more complex, example involves nesting Either values in asynchronous workflows. In some languages, such as F#, Either is rather called Result, and asynchronous workflows are modelled by a Task container, as already demonstrated above. Thus, on .NET at least, this nested monad is often called TaskResult, but you may also see AsyncResult, AsyncEither, or other combinations. Depending on the programming language, such names may be used only for modules, and not for the container type itself. In C# or F# code, for example, you may look in vain after a class called TaskResult<T>, but rather find a TaskResult static class or module.

In C# you can define monadic bind like this:

public static async Task<Either<L, R1>> SelectMany<L, R, R1>(
    this Task<Either<L, R>> source,
    Func<R, Task<Either<L, R1>>> selector)
{
    if (source is null)
        throw new ArgumentNullException(nameof(source));
 
    Either<L, R> x = await source.ConfigureAwait(false);
    return await x.Match(
        l => Task.FromResult(Either.Left<L, R1>(l)),
        selector).ConfigureAwait(false);
}

Here I've again passed the eta-reduced selector straight to the right case of the Either value, but r => selector(r) works, too.

The left case shows another example of 'implicit monadic return'. I didn't bother defining an explicit Return function, but rather use Task.FromResult(Either.Left<L, R1>(l)) to return a Task<Either<L, R1>> value.

As is the case with C#, you'll also need to add a special overload to enable the syntactic sugar of query expressions:

public static Task<Either<L, R1>> SelectMany<L, U, R, R1>(
    this Task<Either<L, R>> source,
    Func<R, Task<Either<L, U>>> k,
    Func<R, U, R1> s)
{
    return source.SelectMany(x => k(x).Select(y => s(x, y)));
}

You'll see a comprehensive example using these functions in a future article.

In F# I'd often first define a module with a few functions including bind, and then use those implementations to define a computation expression, but in one article, I jumped straight to the expression builder:

type AsyncEitherBuilder () =
    // Async<Result<'a,'c>> * ('a -> Async<Result<'b,'c>>)
    // -> Async<Result<'b,'c>>
    member this.Bind(x, f) =
        async {
            let! x' = x
            match x' with
            | Success s -> return! f s
            | Failure f -> return Failure f }
    // 'a -> 'a
    member this.ReturnFrom x = x
 
let asyncEither = AsyncEitherBuilder ()

That article also shows usage examples. Another article, A conditional sandwich example, shows more examples of using this nested monad, although there, the computation expression is named taskResult.

Stateful computations that may fail #

To be honest, you mostly run into a scenario where nested monads are useful when some kind of 'effect' (errors, mostly) is embedded in an I/O-bound computation. In Haskell, this means IO, in C# Task, and in F# either Task or Async.

Other combinations are possible, however, but I've rarely encountered a need for additional nested monads outside of Haskell. In multi-paradigmatic languages, you can usually find other good designs that address issues that you may occasionally run into in a purely functional language. The following example is a Haskell-only example. You can skip it if you don't know or care about Haskell.

Imagine that you want to keep track of some statistics related to a software service you offer. If the variance of some number (say, response time) exceeds 10 then you want to issue an alert that the SLA was violated. Apparently, in your system, reliability means staying consistent.

You have millions of observations, and they keep arriving, so you need an online algorithm. For average and variance we'll use Welford's algorithm.

The following code uses these imports:

import Control.Monad
import Control.Monad.Trans.State.Strict
import Control.Monad.Trans.Maybe

First, you can define a data structure to hold the aggregate values required for the algorithm, as well as an initial, empty value:

data Aggregate = Aggregate { count :: Int, meanA :: Double, m2 :: Double } deriving (Eq, Show)
 
emptyA :: Aggregate
emptyA = Aggregate 0 0 0

You can also define a function to update the aggregate values with a new observation:

update :: Aggregate -> Double -> Aggregate
update (Aggregate count mean m2) x =
  let count' = count + 1
      delta = x - mean
      mean' = mean + delta / fromIntegral count'
      delta2 = x - mean'
      m2' = m2 + delta * delta2
  in Aggregate count' mean' m2'

Given an existing Aggregate record and a new observation, this function implements the algorithm to calculate a new Aggregate record.

The values in an Aggregate record, however, are only intermediary values that you can use to calculate statistics such as mean, variance, and sample variance. You'll need a data type and function to do that, as well:

data Statistics =
  Statistics
    { mean :: Double, variance :: Double, sampleVariance :: Maybe Double }
    deriving (Eq, Show)
 
extractStatistics :: Aggregate -> Maybe Statistics
extractStatistics (Aggregate count mean m2) =
  if count < 1 then Nothing
  else
    let variance = m2 / fromIntegral count
        sampleVariance =
          if count < 2 then Nothing else Just $ m2 / fromIntegral (count - 1)
    in Just $ Statistics mean variance sampleVariance

This is where the computation becomes 'failure-prone'. Granted, we only have a real problem when we have zero observations, but this still means that we need to return a Maybe Statistics value in order to avoid division by zero.

(There might be other designs that avoid that problem, or you might simply decide to tolerate that edge case and code around it in other ways. I've decided to design the extractStatistics function in this particular way in order to furnish an example. Work with me here.)

Let's say that as the next step, you'd like to compose these two functions into a single function that both adds a new observation, computes the statistics, but also returns the updated Aggregate.

You could write it like this:

addAndCompute :: Double -> Aggregate -> Maybe (Statistics, Aggregate)
addAndCompute x agg = do
  let agg' = update agg x
  stats <- extractStatistics agg'
  return (stats, agg')

This implementation uses do notation to automate handling of Nothing values. Still, it's a bit inelegant with its two agg values only distinguishable by the prime sign after one of them, and the need to explicitly return a tuple of the value and the new state.

This is the kind of problem that the State monad addresses. You could instead write the function like this:

addAndCompute :: Double -> State Aggregate (Maybe Statistics)
addAndCompute x = do
  modify $ flip update x
  gets extractStatistics

You could actually also write it as a one-liner, but that's already a bit too terse to my liking:

addAndCompute :: Double -> State Aggregate (Maybe Statistics)
addAndCompute x = modify (`update` x) >> gets extractStatistics

And if you really hate your co-workers, you can always visit pointfree.io to entirely obscure that expression, but I digress.

The point is that the State monad amplifies the essential and eliminates the irrelevant.

Now you'd like to add a function that issues an alert if the variance is greater than 10. Again, you could write it like this:

monitor :: Double -> State Aggregate (Maybe String)
monitor x = do
  stats <- addAndCompute x
  case stats of
    Just Statistics { variance } -> return $
      if 10 < variance
      then Just "SLA violation"
      else Nothing
    Nothing -> return Nothing

But again, the code is graceless with its explicit handling of Maybe cases. Whenever you see code that matches Maybe cases and maps Nothing to Nothing, your spider sense should be tingling. Could you abstract that away with a functor or monad?

Yes you can! You can use the MaybeT monad transformer, which nests Maybe computations inside another monad. In this case State:

monitor :: Double -> State Aggregate (Maybe String)
monitor x = runMaybeT $ do
  Statistics { variance } <- MaybeT $ addAndCompute x
  guard (10 < variance)
  return "SLA Violation"

The function type is the same, but the implementation is much simpler. First, the code lifts the Maybe-valued addAndCompute result into MaybeT and pattern-matches on the variance. Since the code is now 'running in' a Maybe-like context, this line of code only executes if there's a Statistics value to extract. If, on the other hand, addAndCompute returns Nothing, the function already short-circuits there.

The guard works just like imperative Guard Clauses. The third line of code only runs if the variance is greater than 10. In that case, it returns an alert message.

The entire do workflow gets unwrapped with runMaybeT so that we return back to a normal stateful computation that may fail.

Let's try it out:

ghci> (evalState $ monitor 1 >> monitor 7) emptyA
Nothing
ghci> (evalState $ monitor 1 >> monitor 8) emptyA
Just "SLA Violation"

Good, rigorous testing suggests that it's working.

Conclusion #

You sometimes run into situations where monads are nested. This mostly happens in I/O-bound computations, where you may have a Maybe or Either value embedded inside Task or IO. This can sometimes make working with the 'inner' monad awkward, but in many cases there's a good solution at hand.

Some monads, like Maybe, Either, State, Reader, and Identity, nest nicely inside other monads. Thus, if your 'inner' monad is one of those, you can turn the nested arrangement into a monad in its own right. This may help simplify your code base.

In addition to the common monads listed here, there are few more exotic ones that also play well in a nested configuration. Additionally, if your 'inner' monad is a custom data structure of your own creation, it's up to you to investigate if it nests nicely in another monad. As far as I can tell, though, if you can make it nest in one monad (e.g Task, Async, or IO) you can probably make it nest in any monad.

Next: Software design isomorphisms.

This blog is totally free, but if you like it, please consider supporting it.

Collecting and handling result values

2024-11-18T07:39:00+00:00

The answer is traverse. It's always traverse.

I recently came across a Stack Overflow question about collecting and handling sum types (AKA discriminated unions or, in this case, result types). While the question was tagged functional-programming, the overall structure of the code was so imperative, with so much interleaved I/O, that it hardly qualified as functional architecture.

Instead, I gave an answer which involved a minimal change to the code. Subsequently, the original poster asked to see a more functional version of the code. That's a bit too large a task for a Stack Overflow answer, I think, so I'll do it here on the blog instead.

Further comments and discussion on the original post reveal that the poster is interested in two alternatives. I'll start with the alternative that's only discussed, but not shown, in the question. The motivation for this ordering is that this variation is easier to implement than the other one, and I consider it pedagogical to start with the simplest case.

I'll do that in this article, and then follow up with another article that covers the short-circuiting case.

Imperative outset #

To begin, consider this mostly imperative code snippet:

var storedItems = new List<ShoppingListItem>();
var failedItems = new List<ShoppingListItem>();
var errors = new List<Error>();
var state = (storedItems, failedItems, errors);
foreach (var item in itemsToUpdate)
{
    OneOf<ShoppingListItem, NotFound, Error> updateResult = await UpdateItem(item, dbContext);
    state = updateResult.Match<(List<ShoppingListItem>, List<ShoppingListItem>, List<Error>)>(
        storedItem => { storedItems.Add(storedItem); return state;  },
        notFound => { failedItems.Add(item); return state; },
        error => { errors.Add(error); return state; }
        );
}
 
await dbContext.SaveChangesAsync();
 
return Results.Ok(new BulkUpdateResult([.. storedItems], [.. failedItems], [.. errors]));

There's quite a few things to take in, and one has to infer most of the types and APIs, since the original post didn't show more code than that. If you're used to engaging with Stack Overflow questions, however, it's not too hard to figure out what most of the moving parts do.

The Match method implements standard Church encoding, which enables the code to pattern-match on the three alternative values that UpdateItem returns.

One more detail also warrants an explicit description: The itemsToUpdate object is an input argument of the type IEnumerable<ShoppingListItem>.

The implementation makes use of mutable state and undisciplined I/O. How do you refactor it to a more functional design?

Standard traversal #

I'll pretend that we only need to turn the above code snippet into a functional design. Thus, I'm ignoring that the code is most likely part of a larger code base. Because of the implied database interaction, the method isn't a pure function. Unless it's a top-level method (that is, at the boundary of the application), it doesn't exemplify larger-scale functional architecture.

That said, my goal is to refactor the code to an Impureim Sandwich: Impure actions first, then the meat of the functionality as a pure function, and then some more impure actions to complete the functionality. This strongly suggests that the first step should be to map over itemsToUpdate and call UpdateItem for each.

If, however, you do that, you get this:

IEnumerable<Task<OneOf<ShoppingListItem, NotFound, Error>>> results =
    itemsToUpdate.Select(item => UpdateItem(item, dbContext));

The results object is a sequence of tasks. If we consider Task as a surrogate for IO, each task should be considered impure, as it's either non-deterministic, has side effects, or both. This means that we can't pass results to a pure function, and that frustrates the ambition to structure the code as an Impureim Sandwich.

This is one of the most common problems in functional programming, and the answer is usually: Use a traversal.

IEnumerable<OneOf<ShoppingListItem, NotFound<ShoppingListItem>, Error>> results =
    await itemsToUpdate.Traverse(item => UpdateItem(item, dbContext));

Because this first, impure layer of the sandwich awaits the task, results is now an immutable value that can be passed to the pure step. This, by the way, assumes that ShoppingListItem is immutable, too.

Notice that I adjusted one of the cases of the discriminated union to NotFound<ShoppingListItem> rather than just NotFound. While the OneOf library ships with a NotFound type, it doesn't have a generic container of that name, so I defined it myself:

internal sealed record NotFound<T>(T Item);

I added it to make the next step simpler.

Aggregating the results #

The next step is to sort the results into three 'buckets', as it were.

// Pure
var seed =
    (
        Enumerable.Empty<ShoppingListItem>(),
        Enumerable.Empty<ShoppingListItem>(),
        Enumerable.Empty<Error>()
    );
var result = results.Aggregate(
    seed,
    (state, result) =>
        result.Match(
            storedItem => (state.Item1.Append(storedItem), state.Item2, state.Item3),
            notFound => (state.Item1, state.Item2.Append(notFound.Item), state.Item3),
            error => (state.Item1, state.Item2, state.Item3.Append(error))));

It's also possible to inline the seed value, but here I defined it in a separate expression in an attempt at making the code a little more readable. I don't know if I succeeded, because regardless of where it goes, it's hardly idiomatic to break tuple initialization over multiple lines. I had to, though, because otherwise the code would run too far to the right.

The lambda expression handles each result in results and uses Match to append the value to its proper 'bucket'. The outer result is a tuple of the three collections.

Saving the changes and returning the results #

The final, impure step in the sandwich is to save the changes and return the results:

// Impure
await dbContext.SaveChangesAsync();
return new OkResult(
    new BulkUpdateResult([.. result.Item1], [.. result.Item2], [.. result.Item3]));

To be honest, the last line of code is pure, but that's not unusual when it comes to Impureim Sandwiches.

Accumulating the bulk-update result #

So far, I've assumed that the final BulkUpdateResult class is just a simple immutable container without much functionality. If, however, we add some copy-and-update functions to it, we can use them to aggregate the result, instead of an anonymous tuple.

internal BulkUpdateResult Store(ShoppingListItem item) =>
    new([.. StoredItems, item], FailedItems, Errors);
 
internal BulkUpdateResult Fail(ShoppingListItem item) =>
    new(StoredItems, [.. FailedItems, item], Errors);
 
internal BulkUpdateResult Error(Error error) =>
    new(StoredItems, FailedItems, [.. Errors, error]);

Adding these three instance methods to BulkUpdateResult simplifies the composing code:

// Impure
IEnumerable<OneOf<ShoppingListItem, NotFound<ShoppingListItem>, Error>> results =
    await itemsToUpdate.Traverse(item => UpdateItem(item, dbContext));
 
// Pure
var result = results.Aggregate(
    new BulkUpdateResult([], [], []),
    (state, result) =>
        result.Match(
            storedItem => state.Store(storedItem),
            notFound => state.Fail(notFound.Item),
            error => state.Error(error)));
 
// Impure
await dbContext.SaveChangesAsync();
return new OkResult(result);

This variation starts with an empty BulkUpdateResult and then uses Store, Fail, or Error as appropriate to update the state.

Parallel Sequence #

If the tasks you want to traverse are thread-safe, you might consider making the traversal concurrent. You can use Task.WhenAll for that. It has the same type as Sequence, so if you can live with the extra non-determinism that comes with parallel execution, you can use that instead:

internal static async Task<IEnumerable<T>> Sequence<T>(this IEnumerable<Task<T>> tasks)
{
    return await Task.WhenAll(tasks);
}

Since the method signature doesn't change, the rest of the code remains unchanged.

Conclusion #

One of the most common stumbling blocks in functional programming is when you have a collection of values, and you need to perform an impure action (typically I/O) for each. This leaves you with a collection of impure values (Task in C#, Task or Async in F#, IO in Haskell, etc.). What you actually need is a single impure value that contains the collection of results.

The solution to this kind of problem is to traverse the collection, rather than mapping over it (with Select, map, fmap, or similar). Note that computer scientists often talk about traversing a data structure like a tree. This is a less well-defined use of the word, and not directly related. That said, you can also write Traverse and Sequence functions for trees.

This article used a Stack Overflow question as the starting point for an example showing how to refactor imperative code to an Impureim Sandwich.

This completes the first variation requested in the Stack Overflow question.

Next: Short-circuiting an asynchronous traversal.

This blog is totally free, but if you like it, please consider supporting it.

Traversals

2024-11-11T07:45:00+00:00

How to convert a list of tasks into an asynchronous list, and similar problems.

This article is part of a series of articles about functor relationships. In a previous article you learned about natural transformations, and then how functors compose. You can skip several of them if you like, but you might find the one about functor compositions relevant. Still, this article can be read independently of the rest of the series.

You can go a long way with just a single functor or monad. Consider how useful C#'s LINQ API is, or similar kinds of APIs in other languages - typically map and flatMap methods. These APIs work exclusively with the List monad (which is also a functor). Working with lists, sequences, or collections is so useful that many languages have other kinds of special syntax specifically aimed at working with multiple values: List comprehension.

Asynchronous monads like Task<T> or F#'s Async<'T> are another kind of functor so useful in their own right that languages have special async and await keywords to compose them.

Sooner or later, though, you run into situations where you'd like to combine two different functors.

Lists and tasks #

It's not unusual to combine collections and asynchrony. If you make an asynchronous database query, you could easily receive something like Task<IEnumerable<Reservation>>. This, in isolation, hardly causes problems, but things get more interesting when you need to compose multiple reads.

Consider a query like this:

public static Task<Foo> Read(int id)

What happens if you have a collection of IDs that you'd like to read? This happens:

var ids = new[] { 42, 1337, 2112 };
IEnumerable<Task<Foo>> fooTasks = ids.Select(id => Foo.Read(id));

You get a collection of Tasks, which may be awkward because you can't await it. Perhaps you'd rather prefer a single Task that contains a collection: Task<IEnumerable<Foo>>. In other words, you'd like to flip the functors:

IEnumerable<Task<Foo>>
Task<IEnumerable<Foo>>

The top type is what you have. The bottom type is what you'd like to have.

The combination of asynchrony and collections is so common that .NET has special methods to do that. I'll briefly mention one of these later, but what's the general solution to this problem?

Whenever you need to flip two functors, you need a traversal.

Sequence #

As is almost always the case, we can look to Haskell for a canonical definition of traversals - or, as the type class is called: Traversable.

A traversable functor is a functor that enables you to flip that functor and another functor, like the above C# example. In more succinct syntax:

t (f a) -> f (t a)

Here, t symbolises any traversable functor (like IEnumerable<T> in the above C# example), and f is another functor (like Task<T>, above). By flipping the functors I mean making t and f change places; just like IEnumerable and Task, above.

Thinking of functors as containers we might depict the function like this:

To the left, we have an outer functor t (e.g. IEnumerable) that contains another functor f (e.g. Task) that again 'contains' values of type a (in C# typically called T). We'd like to flip how the containers are nested so that f contains t.

Contrary to what you might expect, the function that does that isn't called traverse; it's called sequence. (For those readers who are interested in Haskell specifics, the function I'm going to be talking about is actually called sequenceA. There's also a function called sequence, but it's not as general. The reason for the odd names are related to the evolution of various Haskell type classes.)

The sequence function doesn't work for any old functor. First, t has to be a traversable functor. We'll get back to that later. Second, f has to be an applicative functor. (To be honest, I'm not sure if this is always required, or if it's possible to produce an example of a specific functor that isn't applicative, but where it's still possible to implement a sequence function. The Haskell sequenceA function has Applicative f as a constraint, but as far as I can tell, this only means that this is a sufficient requirement - not that it's necessary.)

Since tasks (e.g. Task<T>) are applicative functors (they are, because they are monads, and all monads are applicative functors), that second requirement is fulfilled for the above example. I'll show you how to implement a Sequence function in C# and how to use it, and then we'll return to the general discussion of what a traversable functor is:

public static Task<IEnumerable<T>> Sequence<T>(
    this IEnumerable<Task<T>> source)
{
    return source.Aggregate(
        Task.FromResult(Enumerable.Empty<T>()),
        async (acc, t) =>
        {
            var xs = await acc;
            var x = await t;
            return xs.Concat(new[] { x });
        });
}

This Sequence function enables you to flip any IEnumerable<Task<T>> to a Task<IEnumerable<T>>, including the above fooTasks:

Task<IEnumerable<Foo>> foosTask = fooTasks.Sequence();

You can also implement sequence in F#:

// Async<'a> list -> Async<'a list>
let sequence asyncs =
    let go acc t = async {
        let! xs = acc
        let! x  = t
        return List.append xs [x] }
    List.fold go (fromValue []) asyncs

and use it like this:

let fooTasks = ids |> List.map Foo.Read
let foosTask = fooTasks |> Async.sequence

For this example, I put the sequence function in a local Async module; it's not part of any published Async module.

These C# and F# examples are specific translations: From lists of tasks to a task of list. If you need another translation, you'll have to write a new function for that particular combination of functors. Haskell has more general capabilities, so that you don't have to write functions for all combinations. I'm not assuming that you know Haskell, however, so I'll proceed with the description.

Traversable functor #

The sequence function requires that the 'other' functor (the one that's not the traversable functor) is an applicative functor, but what about the traversable functor itself? What does it take to be a traversable functor?

I have to admit that I have to rely on Haskell specifics to a greater extent than normal. For most other concepts and abstractions in the overall article series, I've been able to draw on various sources, chief of which are Category Theory for Programmers. In various articles, I've cited my sources whenever possible. While I've relied on Haskell libraries for 'canonical' ways to represent concepts in a programming language, I've tried to present ideas as having a more universal origin than just Haskell.

When it comes to traversable functors, I haven't come across universal reasoning like that which gives rise to concepts like monoids, functors, Church encodings, or catamorphisms. This is most likely a failing on my part.

Traversals of the Haskell kind are, however, so useful that I find it appropriate to describe them. When consulting, it's a common solution to a lot of problems that people are having with functional programming.

Thus, based on Haskell's Data.Traversable, a traversable functor must:

be a functor
be a 'foldable' functor
define a sequence or traverse function

You've already seen examples of sequence functions, and I'm also assuming that (since you've made it so far in the article already) you know what a functor is. But what's a foldable functor?

Haskell comes with a Foldable type class. It defines a class of data that has a particular type of catamorphism. As I've outlined in my article on catamorphisms, Haskell's notion of a fold sometimes coincides with a (or 'the') catamorphism for a type, and sometimes not. For Maybe and List they do coincide, while they don't for Either or Tree. It's not that you can't define Foldable for Either or Tree, it's just that it's not 'the' general catamorphism for that type.

I can't tell whether Foldable is a universal abstraction, or if it's just an ad-hoc API that turns out to be useful in practice. It looks like the latter to me, but my knowledge is only limited. Perhaps I'll be wiser in a year or two.

I will, however, take it as licence to treat this topic a little less formally than I've done with other articles. While there are laws associated with Traversable, they are rather complex, so I'm going to skip them.

The above requirements will enable you to define traversable functors if you run into some more exotic ones, but in practice, the common functors List, Maybe, Either, Tree, and Identity are all traversable. That it useful to know. If any of those functors is the outer functor in a composition of functors, then you can flip them to the inner position as long as the other functor is an applicative functor.

Since IEnumerable<T> is traversable, and Task<T> (or Async<'T>) is an applicative functor, it's possible to use Sequence to convert IEnumerable<Task<Foo>> to Task<IEnumerable<Foo>>.

Traverse #

The C# and F# examples you've seen so far arrive at the desired type in a two-step process. First they produce the 'wrong' type with ids.Select(Foo.Read) or ids |> List.map Foo.Read, and then they use Sequence to arrive at the desired type.

When you use two expressions, you need two lines of code, and you also need to come up with a name for the intermediary value. It might be easier to chain the two function calls into a single expression:

Task<IEnumerable<Foo>> foosTask = ids.Select(Foo.Read).Sequence();

Or, in F#:

let foosTask = ids |> List.map Foo.Read |> Async.sequence

Chaining Select/map with Sequence/sequence is so common that it's a named function: traverse. In C#:

public static Task<IEnumerable<TResult>> Traverse<T, TResult>(
    this IEnumerable<T> source,
    Func<T, Task<TResult>> selector)
{
    return source.Select(selector).Sequence();
}

This makes usage a little easier:

Task<IEnumerable<Foo>> foosTask = ids.Traverse(Foo.Read);

In F# the implementation might be similar:

// ('a -> Async<'b>) -> 'a list -> Async<'b list>
let traverse f xs = xs |> List.map f |> sequence

Usage then looks like this:

let foosTask = ids |> Async.traverse Foo.Read

As you can tell, if you've already implemented sequence you can always implement traverse. The converse is also true: If you've already implemented traverse, you can always implement sequence. You'll see an example of that later.

A reusable idea #

If you know the .NET Task Parallel Library (TPL), you may demur that my implementation of Sequence seems like an inefficient version of Task.WhenAll, and that Traverse could be written like this:

public static async Task<IEnumerable<TResult>> Traverse<T, TResult>(
    this IEnumerable<T> source,
    Func<T, Task<TResult>> selector)
{
    return await Task.WhenAll(source.Select(selector));
}

This alternative is certainly possible. Whether it's more efficient I don't know; I haven't measured. As foreshadowed in the beginning of the article, the combination of collections and asynchrony is so common that .NET has special APIs to handle that. You may ask, then: What's the point?

The point of is that a traversable functor is a reusable idea.

You may be able to find existing APIs like Task.WhenAll to deal with combinations of collections and asynchrony, but what if you need to deal with asynchronous Maybe or Either? Or a List of Maybes?

There may be no existing API to flip things around - before you add it. Now you know that there's a (dare I say it?) design pattern you can implement.

Asynchronous Maybe #

Once people go beyond collections they often run into problems. You may, for example, decide to use the Maybe monad in order to model the presence or absence of a value. Then, once you combine Maybe-based decision values with asynchronous processesing, you may run into problems.

For example, in my article Asynchronous Injection I modelled the core domaim logic as returning Maybe<Reservation>. When handling an HTTP request, the application should use that value to determine what to do next. If the return value is empty it should do nothing, but when the Maybe value is populated, it should save the reservation in a data store using this method:

Task<int> Create(Reservation reservation)

Finally, if accepting the reservation, the HTTP handler (ReservationsController) should return the resevation ID, which is the int returned by Create. Please refer to the article for details. It also links to the sample code on GitHub.

The entire expression is, however, Task-based:

public async Task<IActionResult> Post(Reservation reservation)
{
    return await Repository.ReadReservations(reservation.Date)
        .Select(rs => maîtreD.TryAccept(rs, reservation))
        .SelectMany(m => m.Traverse(Repository.Create))
        .Match(InternalServerError("Table unavailable"), Ok);
}

The Select and SelectMany methods are defined on the Task monad. The m in the SelectMany lambda expression is the Maybe<Reservation> returned by TryAccept. What would happen if you didn't have a Traverse method?

Task<Maybe<Task<int>>> whatIsThis = Repository.ReadReservations(reservation.Date)
    .Select(rs => maîtreD.TryAccept(rs, reservation))
    .Select(m => m.Select(Repository.Create));

Notice that whatIsThis (so named because it's a temporary variable used to investigate the type of the expression so far) has an awkward type: Task<Maybe<Task<int>>>. That's a Task within a Maybe within a Task.

This makes it difficult to continue the composition and return an HTTP result.

Instead, use Traverse:

Task<Task<Maybe<int>>> whatIsThis = Repository.ReadReservations(reservation.Date)
    .Select(rs => maîtreD.TryAccept(rs, reservation))
    .Select(m => m.Traverse(Repository.Create));

This flips the inner Maybe<Task<int>> to Task<Maybe<int>>. Now you have a Maybe within a Task within a Task. The outer two Tasks are now nicely nested, and it's a job for a monad to remove one level of nesting. That's the reason that the final composition uses SelectMany instead of Select.

The Traverse function is implemented like this:

public static Task<Maybe<TResult>> Traverse<T, TResult>(
    this Maybe<T> source,
    Func<T, Task<TResult>> selector)
{
    return source.Match(
        nothing: Task.FromResult(new Maybe<TResult>()),
        just: async x => new Maybe<TResult>(await selector(x)));
}

The idea is reusable. You can also implement a similar traversal in F#:

// ('a -> Async<'b>) -> 'a option -> Async<'b option>
let traverse f = function
    | Some x -> async {
        let! x' = f x
        return Some x' }
    | None -> async { return None }

You can see the F# function as well as a usage example in the article Refactoring registration flow to functional architecture.

Sequence from traverse #

You've already seen that if you have a sequence function, you can implement traverse. I also claimed that the reverse is true: If you have traverse you can implement sequence.

When you've encountered these kinds of dual definitions a couple of times, you start to expect the ubiquitous identity function to make an appearance, and indeed it does:

let sequence x = traverse id x

That's the F# version where the identity function is built in as id. In C# you'd use a lambda expression:

public static Task<Maybe<T>> Sequence<T>(this Maybe<Task<T>> source)
{
    return source.Traverse(x => x);
}

Since C# doesn't come with a predefined identity function, it's idiomatic to use x => x instead.

Conclusion #

Traversals are useful when you need to 'flip' the order of two different, nested functors. The outer one must be a traversable functor, and the inner an applicative functor.

Common traversable functors are List, Maybe, Either, Tree, and Identity, but there are more than those. In .NET you often need them when combining them with Tasks. In Haskell, they are useful when combined with IO.

Next: Nested monads.

Comments

qfilip #

Thanks for this one. You might be interested in Andrew Lock's take on the whole subject as well.

2024-11-17 14:51 UTC

This blog is totally free, but if you like it, please consider supporting it.

Pendulum swing: no Haskell type annotation by default

2024-11-04T07:45:00+00:00

Are Haskell IDE plugins now good enough that you don't need explicit type annotations?

More than three years ago, I published a small article series to document that I'd changed my mind on various small practices. Belatedly, here comes a fourth article, which, frankly, is a cousin rather than a sibling. Still, it fits the overall theme well enough to become another instalment in the series.

Here, I consider using fewer Haskell type annotations, following a practice that I've always followed in F#.

To be honest, though, it's not that I've already applied the following practice for a long time, and only now write about it. It's rather that I feel the need to write this article to kick an old habit and start a new.

Inertia #

As I write in the dedication in Code That Fits in Your Head,

"To my parents:

"My mother, Ulla Seemann, to whom I owe my attention to detail.

"My father, Leif Seemann, from whom I inherited my contrarian streak."

Code That Fits in Your Head, dedication

One should always be careful simplifying one's personality to a simple, easy-to-understand model, but a major point here is that I have two traits that pull in almost the opposite direction.

Despite much work, I only make slow progress. My desire to make things neat and proper almost cancel out my tendency to go against the norms. I tend to automatically toe whatever line that exists until the cognitive dissonance becomes so great that I can no longer ignore it.

I then write an article for the blog to clarify my thoughts.

You may read what comes next and ask, what took you so long?!

I can only refer to the above. I may look calm on the surface, but underneath I'm paddling like the dickens. Despite much work, though, only limited progress is visible.

Nudge #

Haskell is a statically typed language with the most powerful type system I know my way around. The types carry so much information that one can often infer a function's contract from the type alone. This is also fortunate, since many Haskell libraries tend to have, shall we say, minimal documentation. Even so, I've often found myself able to figure out how to use an unfamiliar Haskell API by examining the various types that a library exports.

In fact, the type system is so powerful that it drives a specialized search engine. If you need a function with the type (String -> IO Int) -> [String] -> IO [Int] you can search for it. Hoogle will list all functions that match that type, including functions that are more abstract than your specialized need. You don't even have to imagine what the name might be.

Since the type system is so powerful, it's a major means of communication. Thus, it makes sense that GHC regularly issues a warning if a function lacks a type annotation.

While the compiler enables you to control which warnings are turned on, the missing-signatures warning is included in the popular all flag that most people, I take it, use. I do, at least.

If you forget to declare the type of a function, the compiler will complain:

src\SecurityManager.hs:15:1: warning: [GHC-38417] [-Wmissing-signatures]
    Top-level binding with no type signature:
      createUser :: (Monad m, Text.Printf.PrintfArg b,
                     Text.Printf.PrintfArg (t a), Foldable t, Eq (t a)) =>
                    (String -> m ()) -> m (t a) -> (t a -> b) -> m ()
   |
15 | createUser writeLine readLine encrypt = do
   | ^^^^^^^^^^

This is a strong nudge that you're supposed to give each function a type declaration, so I've been doing that for years. Neat and proper.

Of course, if you treat warnings as errors, as I recommend, the nudge becomes a law.

Learning from F# #

While I try to adopt the style and idioms of any language I work in, it's always annoyed me that I had to add a type annotation to a Haskell function. After all, the compiler can usually infer the type. Frankly, adding a type signature feels like redundant ceremony. It's like having to declare a function in a header file before being able to implement it in another file.

This particularly bothers me because I've long since abandoned type annotations in F#. As far as I can tell, most of the F# community has, too.

When you implement an F# function, you just write the implementation and let the compiler infer the type. (Code example from Zone of Ceremony.)

let inline consume quantity =
    let go (acc, xs) x =
        if quantity <= acc
        then (acc, Seq.append xs (Seq.singleton x))
        else (acc + x, xs)
    Seq.fold go (LanguagePrimitives.GenericZero, Seq.empty) >> snd

Since F# often has to interact with .NET code written in C#, you regularly have to add some type annotations to help the compiler along:

let average (timeSpans : NonEmpty<TimeSpan>) =
    [ timeSpans.Head ] @ List.ofSeq timeSpans.Tail
    |> List.averageBy (_.Ticks >> double)
    |> int64
    |> TimeSpan.FromTicks

Even so, I follow the rule of minimal annotations: Only add the type information required to compile, and let the compiler infer the rest. For example, the above average function has the inferred type NonEmpty<TimeSpan> -> TimeSpan. While I had to specify the input type in order to be able to use the Ticks property, I didn't have to specify the return type. So I didn't.

My impression from reading other people's F# code is that this is a common, albeit not universal, approach to type annotation.

This minimizes ceremony, since you only need to declare and maintain the types that the compiler can't infer. There's no reason to repeat the work that the compiler can already do, and in practice, if you do, it just gets in the way.

Motivation for explicit type definitions #

When I extol the merits of static types, proponents of dynamically typed languages often argue that the types are in the way. Granted, this is a discussion that I still struggle with, but based on my understanding of the argument, it seems entirely reasonable. After all, if you have to spend time declaring the type of each and every parameter, as well as a function's return type, it does seem to be in the way. This is only exacerbated if you later change your mind.

Programming is, to a large extend, an explorative activity. You start with one notion of how your code should be structured, but as you progress, you learn. You'll often have to go back and change existing code. This, as far as I can tell, is much easier in, say, Python or Clojure than in C# or Java.

If, however, one extrapolates from the experience with Java or C# to all statically typed languages, that would be a logical fallacy. My point with Zone of Ceremony was exactly that there's a group of languages 'to the right' of high-ceremony languages with low levels of ceremony. Even though they're statically typed.

I have to admit, however, that in that article I cheated a little in order to drive home a point. While you can write Haskell code in a low-ceremony style, the tooling (in the form of the all warning set, at least) encourages a high-ceremony style. Add those type definitions, even thought they're redundant.

It's not that I don't understand some of the underlying motivation behind that rule. Daniel Wagner enumerated several reasons in a 2013 Stack Overflow answer. Some of the reasons still apply, but on the other hand, the world has also moved on in the intervening decade.

To be honest, the Haskell IDE situation has always been precarious. One day, it works really well; the next day, I struggle with it. Over the years, though, things have improved.

There was a time when an explicit type definition was a indisputable help, because you couldn't rely on tools to light up and tell you what the inferred type was.

Today, on the other hand, the Haskell extension for Visual Studio Code automatically displays the inferred type above a function implementation:

To be clear, the top line that shows the type definition is not part of the source code. It's just shown by Visual Studio Code as a code lens (I think it's called), and it automatically changes if I edit the code in such a way that the type changes.

If you can rely on such automatic type information, it seems that an explicit type declaration is less useful. It's at least one less reason to add type annotations to the source code.

Ceremony example #

In order to explain what I mean by the types being in the way, I'll give an example. Consider the code example from the article Legacy Security Manager in Haskell. In it, I described how every time I made a change to the createUser action, I had to effectively remove and re-add the type declaration.

It doesn't have to be like that. If instead I'd started without type annotations, I could have moved forward without being slowed down by having to edit type definitions. Take the first edit, breaking the dependency on the console, as an example. Without type annotations, the createUser action would look exactly as before, just without the type declaration. Its type would still be IO ().

After the first edit, the first lines of the action now look like this:

createUser writeLine readLine = do
  () <- writeLine "Enter a username"
  -- ...

Even without a type definition, the action still has a type. The compiler infers it to be (Monad m, Eq a, IsChar a) => (String -> m ()) -> m [a] -> m (), which is certainly a bit of a mouthful, but exactly what I had explicitly added in the other article.

The code doesn't compile until I also change the main method to pass the new parameters:

main = createUser putStrLn getLine

You'd have to make a similar edit in, say, Python, although there'd be no compiler to remind you. My point isn't that this is better than a dynamically typed language, but rather that it's on par. The types aren't in the way.

We see the similar lack of required ceremony when the createUser action finally pulls in the comparePasswords and validatePassword functions:

createUser writeLine readLine encrypt = do
  () <- writeLine "Enter a username"
  username <- readLine
  writeLine "Enter your full name"
  fullName <- readLine
  writeLine "Enter your password"
  password <- readLine
  writeLine "Re-enter your password"
  confirmPassword <- readLine
 
  writeLine $ either
    id
    (printf "Saving Details for User (%s, %s, %s)" username fullName . encrypt)
    (validatePassword =<< comparePasswords password confirmPassword)

Again, there's no type annotation, and while the type actually does change to

(Monad m, PrintfArg b, PrintfArg (t a), Foldable t, Eq (t a)) =>
(String -> m ()) -> m (t a) -> (t a -> b) -> m ()

it impacts none of the existing code. Again, the types aren't in the way, and no ceremony is required.

Compare that inferred type signature with the explicit final type annotation in the previous article. The inferred type is much more abstract and permissive than the explicit declaration, although I also grant that Daniel Wagner had a point that you can make explicit type definitions more reader-friendly.

Flies in the ointment #

Do the inferred types communicate intent? That's debatable. For example, it's not immediately clear that the above t a allows String.

Another thing that annoys me is that I had to add that unit binding on the first line:

createUser writeLine readLine encrypt = do
  () <- writeLine "Enter a username"
  -- ...

The reason for that is that if I don't do that (that is, if I just write writeLine "Xyz" all the way), the compiler infers the type of writeLine to be String -> m b2, rather than just String -> m (). In effect, I want b2 ~ (), but because the compiler thinks that b2 may be anything, it issues an unused-do-bind warning.

The idiomatic way to resolve that situation is to add a type definition, but that's the situation I'm trying to avoid. Thus, my desire to do without annotations pushes me to write unnatural implementation code. This reminds me of the notion of test-induced damage. This is at best a disagreeable compromise.

It also annoys me that implementation details leak out to the inferred type, witnessed by the PrintfArg type constraint. What happens if I change the implementation to use list concatenation?

createUser writeLine readLine encrypt = do
  () <- writeLine "Enter a username"
  username <- readLine
  writeLine "Enter your full name"
  fullName <- readLine
  writeLine "Enter your password"
  password <- readLine
  writeLine "Re-enter your password"
  confirmPassword <- readLine
 
  let createMsg pwd =
        "Saving Details for User (" ++ username ++", " ++ fullName ++ ", " ++ pwd ++")"
  writeLine $ either
    id
    (createMsg . encrypt)
    (validatePassword =<< comparePasswords password confirmPassword)

If I do that, the type also changes:

Monad m => (String -> m ()) -> m [Char] -> ([Char] -> [Char]) -> m ()

While we get rid of the PrintfArg type constraint, the type becomes otherwise more concrete, now operating on String values (keeping in mind that String is a type synonym for [Char]).

The code still compiles, and all tests still pass, because the abstraction I've had in mind all along is essentially this last type.

The writeLine action should take a String and have some side effect, but return no data. The type String -> m () nicely models that, striking a fine balance between being sufficiently concrete to capture intent, but still abstract enough to be testable.

The readLine action should provide input String values, and again m String nicely models that concern.

Finally, encrypt is indeed a naked String endomorphism: String -> String.

With my decades of experience with object-oriented design, it still strikes me as odd that implementation details can make a type more abstract, but once you think it over, it may be okay.

More liberal abstractions #

The inferred types are consistently more liberal than the abstraction I have in mind, which is

Monad m => (String -> m ()) -> m String -> (String -> String) -> m ()

In all cases, the inferred types include that type as a subset.

I hope that I've created the above diagram so that it makes sense, but the point I'm trying to get across is that the two type definitions in the lower middle are equivalent, and are the most specific types. That's the intended abstraction. Thinking of types as sets, all the other inferred types are supersets of that type, in various ways. Even though implementation details leak out in the shape of PrintfArg and IsChar, these are effectually larger sets.

This takes some getting used to: The implementation details are more liberal than the abstraction. This seems to be at odds with the Dependency Inversion Principle (DIP), which suggests that abstractions shouldn't depend on implementation details. I'm not yet sure what to make of this, but I suspect that this is more of problem of overlapping linguistic semantics than software design. What I mean is that I have a feeling that 'implementation detail' have more than one meaning. At least, in the perspective of the DIP, an implementation detail limits your options. For example, depending on a particular database technology is more constraining than depending on some abstract notion of what the persistence mechanism might be. Contrast this with an implementation detail such as the PrintfArg type constraint. It doesn't narrow your options; on the contrary, it makes the implementation more liberal.

Still, while an implementation should be liberal in what it accepts, it's probably not a good idea to publish such a capability to the wider world. After all, if you do, someone will eventually rely on it.

For internal use only #

Going through all these considerations, I think I'll revise my position as the following.

I'll forgo type annotations as long as I explore a problem space. For internal application use, this may effectively mean forever, in the sense that how you compose an application from smaller building blocks is likely to be in permanent flux. Here I have in mind your average web asset or other public-facing service that's in constant development. You keep adding new features, or changing domain logic as the overall business evolves.

As I've also recently discussed, Haskell is a great scripting language, and I think that here, too, I'll dial down the type definitions.

If I ever do another Advent of Code in Haskell, I think I'll also eschew explicit type annotations.

On the other hand, I can see that once an API stabilizes, you may want to lock it down. This may also apply to internal abstractions if you're working in a team and you explicitly want to communicate what a contract is.

If the code is a reusable library, I think that explicit type definitions are still required. Both for the reasons outlined by Daniel Wagner, and also to avoid being the victim of Hyrum's law.

That's why I phrase this pendulum swing as a new default. I'll begin programming without type definitions, but add them as needed. The point is rather that there may be parts of a code base where they're never needed, and then it's okay to keep going without them.

You can use a language pragma to opt out of the missing-signatures compiler warning on a module-by-module basis:

{-# OPTIONS_GHC -Wno-missing-signatures #-}

This will enable me to rely on type inference in parts of the code base, while keeping the build clean of compiler warnings.

Conclusion #

I've always appreciated the F# compiler's ability to infer types and just let type changes automatically ripple through the code base. For that reason, the Haskell norm of explicitly adding a (redundant) type annotation has always vexed me.

It often takes me a long time to reach seemingly obvious conclusions, such as: Don't always add type definitions to Haskell functions. Let the type inference engine do its job.

The reason it takes me so long to take such a small step is that I want to follow 'best practice'; I want to write idiomatic code. When the standard compiler-warning set complains about missing type definitions, it takes me significant deliberation to discard such advice. I could imagine other programmers being in the same situation, which is one reason I wrote this article.

The point isn't that type definitions are a universally bad idea. They aren't. Rather, the point is only that it's also okay to do without them in parts of a code base. Perhaps only temporarily, but in some cases maybe permanently.

The missing-signatures warning shouldn't, I now believe, be considered an absolute law, but rather a contextual rule.

This blog is totally free, but if you like it, please consider supporting it.

Functor compositions

2024-10-28T06:58:00+00:00

A functor nested within another functor forms a functor. With examples in C# and another language.

This article is part of a series of articles about functor relationships. In this one you'll learn about a universal composition of functors. In short, if you have one functor nested within another functor, then this composition itself gives rise to a functor.

Together with other articles in this series, this result can help you answer questions such as: Does this data structure form a functor?

Since functors tend to be quite common, and since they're useful enough that many programming languages have special support or syntax for them, the ability to recognize a potential functor can be useful. Given a type like Foo<T> (C# syntax) or Bar<T1, T2>, being able to recognize it as a functor can come in handy. One scenario is if you yourself have just defined this data type. Recognizing that it's a functor strongly suggests that you should give it a Select method in C#, a map function in F#, and so on.

Not all generic types give rise to a (covariant) functor. Some are rather contravariant functors, and some are invariant.

If, on the other hand, you have a data type where one functor is nested within another functor, then the data type itself gives rise to a functor. You'll see some examples in this article.

Abstract shape #

Before we look at some examples found in other code, it helps if we know what we're looking for. Imagine that you have two functors F and G, and you're now considering a data structure that contains a value where G is nested inside of F.

public sealed class GInF<T>
{
    private readonly F<G<T>> ginf;
 
    public GInF(F<G<T>> ginf)
    {
        this.ginf = ginf;
    }
 
    // Methods go here...

The GInF<T> class has a single class field. The type of this field is an F container, but 'inside' F there's a G functor.

This kind of data structure gives rise to a functor. Knowing that, you can give it a Select method:

public GInF<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new GInF<TResult>(ginf.Select(g => g.Select(selector)));
}

The composed Select method calls Select on the F functor, passing it a lambda expression that calls Select on the G functor. That nested Select call produces an F<G<TResult>> that the composed Select method finally wraps in a new GInF<TResult> object that it returns.

I'll have more to say about how this generalizes to a nested composition of more than two functors, but first, let's consider some examples.

Priority list #

A common configuration is when the 'outer' functor is a collection, and the 'inner' functor is some other kind of container. The article An immutable priority collection shows a straightforward example. The PriorityCollection<T> class composes a single class field:

private readonly Prioritized<T>[] priorities;

The priorities field is an array (a collection) of Prioritized<T> objects. That type is a simple record type:

public sealed record Prioritized<T>(T Item, byte Priority);

If we squint a little and consider only the parameter list, we may realize that this is fundamentally an 'embellished' tuple: (T Item, byte Priority). A pair forms a bifunctor, but in the Haskell Prelude a tuple is also a Functor instance over its rightmost element. In other words, if we'd swapped the Prioritized<T> constructor parameters, it might have naturally looked like something we could fmap:

ghci> fmap (elem 'r') (55, "foo")
(55,False)

Here we have a tuple of an integer and a string. Imagine that the number 55 is the priority that we give to the label "foo". This little ad-hoc example demonstrates how to map that tuple to another tuple with a priority, but now it instead holds a Boolean value indicating whether or not the string contained the character 'r' (which it didn't).

You can easily swap the elements:

ghci> import Data.Tuple
ghci> swap (55, "foo")
("foo",55)

This looks just like the Prioritized<T> parameter list. This also implies that if you originally have the parameter list in that order, you could swap it, map it, and swap it again:

ghci> swap $ fmap (elem 'r') $ swap ("foo", 55)
(False,55)

My point is only that Prioritized<T> is isomorphic to a known functor. In reality you rarely need to analyze things that thoroughly to come to that realization, but the bottom line is that you can give Prioritized<T> a lawful Select method:

public sealed record Prioritized<T>(T Item, byte Priority)
{
    public Prioritized<TResult> Select<TResult>(Func<T, TResult> selector)
    {
        return new(selector(Item), Priority);
    }
}

Hardly surprising, but since this article postulates that a functor of a functor is a functor, and since we already know that collections give rise to a functor, we should deduce that we can give PriorityCollection<T> a Select method. And we can:

public PriorityCollection<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new PriorityCollection<TResult>(
        priorities.Select(p => p.Select(selector)).ToArray());
}

Notice how much this implementation looks like the above GInF<T> 'shape' implementation.

Tree #

An example only marginally more complicated than the above is shown in A Tree functor. The Tree<T> class shown in that article contains two constituents:

private readonly IReadOnlyCollection<Tree<T>> children;
 
public T Item { get; }

Just like PriorityCollection<T> there's a collection, as well as a 'naked' T value. The main difference is that here, the collection is of the same type as the object itself: Tree<T>.

You've seen a similar example in the previous article, which also had a recursive data structure. If you assume, however, that Tree<T> gives rise to a functor, then so does the nested composition of putting it in a collection. This means, from the 'theorem' put forth in this article, that IReadOnlyCollection<Tree<T>> composes as a functor. Finally you have a product of a T (which is isomorphic to the Identity functor) and that composed functor. From Functor products it follows that that's a functor too, which explains why Tree<T> forms a functor. The article shows the Select implementation.

Binary tree Zipper #

In both previous articles you've seen pieces of the puzzle explaining why the binary tree Zipper gives rise to functor. There's one missing piece, however, that we can now finally address.

Recall that BinaryTreeZipper<T> composes these two objects:

public BinaryTree<T> Tree { get; }
public IEnumerable<Crumb<T>> Breadcrumbs { get; }

We've already established that both BinaryTree<T> and Crumb<T> form functors. In this article you've learned that a functor in a functor is a functor, which applies to IEnumerable<Crumb<T>>. Both of the above read-only properties are functors, then, which means that the entire class is a product of functors. The Select method follows:

public BinaryTreeZipper<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new BinaryTreeZipper<TResult>(
        Tree.Select(selector),
        Breadcrumbs.Select(c => c.Select(selector)));
}

Notice that this Select implementation calls Select on the 'outer' Breadcrumbs by calling Select on each Crumb<T>. This is similar to the previous examples in this article.

Other nested containers #

There are plenty of other examples of functors that contains other functor values. Asynchronous programming supplies its own family of examples.

The way that C# and many other languages model asynchronous or I/O-bound actions is to wrap them in a Task container. If the value inside the Task<T> container is itself a functor, you can make that a functor, too. Examples include Task<IEnumerable<T>>, Task<Maybe<T>> (or its close cousin Task<T?>; notice the question mark), Task<Result<T1, T2>>, etc. You'll run into such types every time you have an I/O-bound or concurrent operation that returns IEnumerable<T>, Maybe<T> etc. as an asynchronous result.

While you can make such nested task functors a functor in its own right, you rarely need that in languages with native async and await features, since those languages nudge you in other directions.

You can, however, run into other issues with task-based programming, but you'll see examples and solutions in a future article.

You'll run into other examples of nested containers with many property-based testing libraries. They typically define Test Data Generators, often called Gen<T>. For .NET, both FsCheck, Hedgehog, and CsCheck does this. For Haskell, QuickCheck, too, defines Gen a.

You often need to generate random collections, in which case you'd work with Gen<IEnumerable<T>> or a similar collection type. If you need random Maybe values, you'll work with Gen<Maybe<T>>, and so on.

On the other hand, sometimes you need to work with a collection of generators, such as seq<Gen<'a>>.

These are all examples of functors within functors. It's not a given that you must treat such a combination as a functor in its own right. To be honest, typically, you don't. On the other hand, if you find yourself writing Select within Select, or map within map, depending on your language, it might make your code more succinct and readable if you give that combination a specialized functor affordance.

Higher arities #

Like the previous two articles, the 'theorem' presented here generalizes to more than two functors. If you have a third H functor, then F<G<H<T>>> also gives rise to a functor. You can easily prove this by simple induction. We may first consider the base case. With a single functor (n = 1) any functor (say, F) is trivially a functor.

In the induction step (n > 1), you then assume that the n - 1 'stack' of functors already gives rise to a functor, and then proceed to prove that the configuration where all those nested functors are wrapped by yet another functor also forms a functor. Since the 'inner stack' of functors forms a functor (by assumption), you only need to prove that a configuration of the outer functor, and that 'inner stack', gives rise to a functor. You've seen how this works in this article, but I admit that a few examples constitute no proof. I'll leave you with only a sketch of this step, but you may consider using equational reasoning as demonstrated by Bartosz Milewski and then prove the functor laws for such a composition.

The Haskell Data.Functor.Compose module defines a general-purpose data type to compose functors. You may, for example, compose a tuple inside a Maybe inside a list:

thriceNested :: Compose [] (Compose Maybe ((,) Integer)) String
thriceNested = Compose [Compose (Just (42, "foo")), Compose Nothing, Compose (Just (89, "ba"))]

You can easily fmap that data structure, for example by evaluating whether the number of characters in each string is an odd number (if it's there at all):

ghci> fmap (odd . length) thriceNested
Compose [Compose (Just (42,True)),Compose Nothing,Compose (Just (89,False))]

The first element now has True as the second tuple element, since "foo" has an odd number of characters (3). The next element is Nothing, because Nothing maps to Nothing. The third element has False in the rightmost tuple element, since "ba" doesn't have an odd number of characters (it has 2).

Relations to monads #

A nested 'stack' of functors may remind you of the way that I prefer to teach monads: A monad is a functor your can flatten. In short, the definition is the ability to 'flatten' F<F<T>> to F<T>. A function that can do that is often called join or Flatten.

So far in this article, we've been looking at stacks of different functors, abstractly denoted F<G<T>>. There's no rule, however, that says that F and G may not be the same. If F = G then F<G<T>> is really F<F<T>>. This starts to look like the antecedent of the monad definition.

While the starting point may be the same, these notions are not equivalent. Yes, F<F<T>> may form a monad (if you can flatten it), but it does, universally, give rise to a functor. On the other hand, we can hardly talk about flattening F<G<T>>, because that would imply that you'd have to somehow 'throw away' either F or G. There may be specific functors (e.g. Identity) for which this is possible, but there's no universal law to that effect.

Not all 'stacks' of functors are monads. All monads, on the other hand, are functors.

Conclusion #

A data structure that configures one type of functor inside of another functor itself forms a functor. The examples shown in this article are mostly constrained to two functors, but if you have a 'stack' of three, four, or more functors, that arrangement still gives rise to a functor.

This is useful to know, particularly if you're working in a language with only partial support for functors. Mainstream languages aren't going to automatically turn such stacks into functors, in the way that Haskell's Compose container almost does. Thus, knowing when you can safely give your generic types a Select method or map function may come in handy.

To be honest, though, this result is hardly the most important 'theorem' concerning stacks of functors. In reality, you often run into situations where you do have a stack of functors, but they're in the wrong order. You may have a collection of asynchronous tasks, but you really need an asynchronous task that contains a collection of values. The next article addresses that problem.

Next: Traversals.

This blog is totally free, but if you like it, please consider supporting it.

Legacy Security Manager in Haskell

2024-10-21T06:14:00+00:00

A translation of the kata, and my first attempt at it.

In early 2013 Richard Dalton published an article about legacy code katas. The idea is to present a piece of 'legacy code' that you have to somehow refactor or improve. Of course, in order to make the exercise manageable, it's necessary to reduce it to some essence of what we might regard as legacy code. It'll only be one aspect of true legacy code. For the legacy Security Manager exercise, the main problem is that the code is difficult to unit test.

The original kata presents the 'legacy code' in C#, which may exclude programmers who aren't familiar with that language and platform. Since I find the exercise useful, I've previous published a port to Python. In this article, I'll port the exercise to Haskell, as well as walk through one attempt at achieving the goals of the kata.

The legacy code #

The original C# code is a static procedure that uses the Console API to ask a user a few simple questions, do some basic input validation, and print a message to the standard output stream. That's easy enough to port to Haskell:

module SecurityManager (createUser) where
 
import Text.Printf (printf)
 
createUser :: IO ()
createUser = do
  putStrLn "Enter a username"
  username <- getLine
  putStrLn "Enter your full name"
  fullName <- getLine
  putStrLn "Enter your password"
  password <- getLine
  putStrLn "Re-enter your password"
  confirmPassword <- getLine
 
  if password /= confirmPassword
  then
    putStrLn "The passwords don't match"
  else
    if length password < 8
    then
      putStrLn "Password must be at least 8 characters in length"
    else do
      -- Encrypt the password (just reverse it, should be secure)
      let array = reverse password
      putStrLn $
        printf "Saving Details for User (%s, %s, %s)" username fullName array

Notice how the Haskell code seems to suffer slightly from the Arrow code smell, which is a problem that the C# code actually doesn't exhibit. The reason is that when using Haskell in an 'imperative style' (which you can, after a fashion, with do notation), you can't 'exit early' from a an if check. The problem is that you can't have if-then without else.

Haskell has other language features that enable you to get rid of Arrow code, but in the spirit of the exercise, this would take us too far away from the original C# code. Making the code prettier should be a task for the refactoring exercise, rather than the starting point.

I've published the code to GitHub, if you want a leg up.

Combined with Richard Dalton's original article, that's all you need to try your hand at the exercise. In the rest of this article, I'll go through my own attempt at the exercise. That said, while this was my first attempt at the Haskell version of it, I've done it multiple times in C#, and once in Python. In other words, this isn't my first rodeo.

Break the dependency on the Console #

As warned, the rest of the article is a walkthrough of the exercise, so if you'd like to try it yourself, stop reading now. On the other hand, if you want to read on, but follow along in the GitHub repository, I've pushed the rest of the code to a branch called first-pass.

The first part of the exercise is to break the dependency on the console. In a language like Haskell where functions are first-class citizens, this part is trivial. I removed the type declaration, moved putStrLn and getLine to parameters and renamed them. Finally, I asked the compiler what the new type is, and added the new type signature.

import Text.Printf (printf, IsChar)
 
createUser :: (Monad m, Eq a, IsChar a) => (String -> m ()) -> m [a] -> m ()
createUser writeLine readLine = do
  writeLine "Enter a username"
  username <- readLine
  writeLine "Enter your full name"
  fullName <- readLine
  writeLine "Enter your password"
  password <- readLine
  writeLine "Re-enter your password"
  confirmPassword <- readLine
 
  if password /= confirmPassword
  then
    writeLine "The passwords don't match"
  else
    if length password < 8
    then
      writeLine "Password must be at least 8 characters in length"
    else do
      -- Encrypt the password (just reverse it, should be secure)
      let array = reverse password
      writeLine $
        printf "Saving Details for User (%s, %s, %s)" username fullName array

I also changed the main action of the program to pass putStrLn and getLine as arguments:

import SecurityManager (createUser)
 
main :: IO ()
main = createUser putStrLn getLine

Manual testing indicates that I didn't break any functionality.

Get the password comparison feature under test #

The next task is to get the password comparison feature under test. Over a small series of Git commits, I added these inlined, parametrized HUnit tests:

"Matching passwords" ~: do
  pw <- ["password", "12345678", "abcdefgh"]
  let actual = comparePasswords pw pw
  return $ Right pw ~=? actual
,
"Non-matching passwords" ~: do
  (pw1, pw2) <-
    [
      ("password", "PASSWORD"),
      ("12345678", "12345677"),
      ("abcdefgh", "bacdefgh"),
      ("aaa", "bbb")
    ]
  let actual = comparePasswords pw1 pw2
  return $ Left "The passwords don't match" ~=? actual

The resulting implementation is this comparePasswords function:

comparePasswords :: String -> String -> Either String String
comparePasswords pw1 pw2 =
  if pw1 == pw2
  then Right pw1
  else Left "The passwords don't match"

You'll notice that I chose to implement it as an Either-valued function. While I consider validation a solved problem, the usual solution involves some applicative validation container. In this exercise, validation is already short-circuiting, which means that we can use the standard monadic composition that Either affords.

At this point in the exercise, I just left the comparePasswords function there, without trying to use it within createUser. The reason for that is that Either-based composition is sufficiently different from if-then-else code that I wanted to get the entire system under test before I attempted that.

Get the password validation feature under test #

The third task of the exercise is to get the password validation feature under test. That's similar to the previous task. Once more, I'll show the tests first, and then the function driven by those tests, but I want to point out that both code artefacts came iteratively into existence through the usual red-green-refactor cycle.

"Validate short password" ~: do
  pw <- ["", "1", "12", "abc", "1234", "gtrex", "123456", "1234567"]
  let actual = validatePassword pw
  return $ Left "Password must be at least 8 characters in length" ~=? actual
,
"Validate long password" ~: do
  pw <- ["12345678", "123456789", "abcdefghij", "elevenchars"]
  let actual = validatePassword pw
  return $ Right pw ~=? actual

The resulting function is hardly surprising.

validatePassword :: String -> Either String String
validatePassword pw =
  if length pw < 8
  then Left "Password must be at least 8 characters in length"
  else Right pw

As in the previous step, I chose to postpone using this function from within createUser until I had a set of characterization tests. That may not be entirely in the spirit of the four subtasks of the exercise, but on the other hand, I intended to do more than just those four activities. The code here is actually simple enough that I could easily refactor without full test coverage, but recalling that this is a legacy code exercise, I find it warranted to pretend that it's complicated.

To be fair to the exercise, there'd also be a valuable exercise in attempting to extract each feature piecemeal, because it's not alway possible to add complete characterization test coverage to a piece of gnarly legacy code. Be that as it may, I've already done that kind of exercise in C# a few times, and I had a different agenda for the Haskell exercise. In short, I was curious about what sort of inferred type createUser would have, once I'd gone through all four subtasks. I'll return to that topic in a moment. First, I want to address the fourth subtask.

Allow different encryption algorithms to be used #

The final part of the exercise is to add a feature to allow different encryption algorithms to be used. Once again, when you're working in a language where functions are first-class citizens, and higher-order functions are idiomatic, one solution is easily at hand:

createUser :: (Monad m, Foldable t, Eq (t a), PrintfArg (t a), PrintfArg b)
           => (String -> m ()) -> m (t a) -> (t a -> b) -> m ()
createUser writeLine readLine encrypt = do
  writeLine "Enter a username"
  username <- readLine
  writeLine "Enter your full name"
  fullName <- readLine
  writeLine "Enter your password"
  password <- readLine
  writeLine "Re-enter your password"
  confirmPassword <- readLine
 
  if password /= confirmPassword
  then
    writeLine "The passwords don't match"
  else
    if length password < 8
    then
      writeLine "Password must be at least 8 characters in length"
    else do
      let array = encrypt password
      writeLine $
        printf "Saving Details for User (%s, %s, %s)" username fullName array

The only change I've made is to promote encrypt to a parameter. This, of course, ripples through the code that calls the action, but currently, that's only the main action, where I had to add reverse as a third argument:

main :: IO ()
main = createUser putStrLn getLine reverse

Before I made the change, I removed the type annotation from createUser, because adding a parameter causes the type to change. Keeping the type annotation would have caused a compilation error. Eschewing type annotations makes it easier to make changes. Once I'd made the change, I added the new annotation, inferred by the Haskell Visual Studio Code extension.

I was curious what kind of abstraction would arise. Would it be testable in some way?

Testability #

Consider the inferred type of createUser above. It's quite abstract, and I was curious if it was flexible enough to allow testability without adding test-induced damage. In short, in object-oriented programming, you often need to add Dependency Injection to make code testable, and the valid criticism is that this makes code more complicated than it would otherwise have been. I consider such reproval justified, although I disagree with the conclusion. It's not the desire for testability that causes the damage, but rather that object-oriented design is at odds with testability.

That's my conjecture, anyway, so I'm always curious when working with other paradigms like functional programming. Is idiomatic code already testable, or do you need to 'do damage to it' in order to make it testable?

As a Haskell action goes, I would consider its type fairly idiomatic. The code, too, is straightforward, although perhaps rather naive. It looks like beginner Haskell, and as we'll see later, we can rewrite it to be more elegant.

Before I started the exercise, I wondered whether it'd be necessary to use free monads to model pure command-line interactions. Since createUser returns m (), where m is any Monad instance, using a free monad would be possible, but turns out to be overkill. After having thought about it a bit, I recalled that in many languages and platforms, you can redirect standard in and standard out for testing purposes. The way you do that is typically by replacing each with some kind of text stream. Based on that knowledge, I thought I could use the State monad for characterization testing, with a list of strings for each text stream.

In other words, the code is already testable as it is. No test-induced damage here.

Characterization tests #

To use the State monad, I started by importing Control.Monad.Trans.State.Lazy into my test code. This enabled me to write the first characterization test:

"Happy path" ~: flip evalState
    (["just.inhale", "Justin Hale", "12345678", "12345678"], []) $ do
  let writeLine x = modify (second (++ [x]))
  let readLine = state (\(i, o) -> (head i, (tail i, o)))
  let encrypt = reverse
 
  createUser writeLine readLine encrypt
 
  actual <- gets snd
  let expected = [
        "Enter a username",
        "Enter your full name",
        "Enter your password",
        "Re-enter your password",
        "Saving Details for User (just.inhale, Justin Hale, 87654321)"]
  return $ expected ~=? actual

I consulted my earlier code from An example of state-based testing in Haskell instead of reinventing the wheel, so if you want a more detailed walkthrough, you may want to consult that article as well as this one.

The type of the state that the test makes use of is ([String], [String]). As the lambda expression suggests by naming the elements i and o, the two string lists are used for respectively input and output. The test starts with an 'input stream' populated by 'user input' values, corresponding to each of the four answers a user might give to the questions asked.

The readLine function works by pulling the head off the input list i, while on the other hand not touching the output list o. Its type is State ([a], b) a, compatible with createUser, which requires its readLine parameter to have the type m (t a), where m is a Monad instance, and t a Foldable instance. The effective type turns out to be t a ~ [Char] = String, so that readLine effectively has the type State ([String], b) String. Since State ([String], b) is a Monad instance, it fits the m type argument of the requirement.

The same kind of reasoning applies to writeLine, which appends the input value to the 'output stream', which is the second list in the I/O tuple.

The test runs the createUser action and then checks that the output list contains the expected values.

A similar test verifies the behaviour when the passwords don't match:

"Mismatched passwords" ~: flip evalState
    (["i.lean.right", "Ilene Wright", "password", "Password"], []) $ do
  let writeLine x = modify (second (++ [x]))
  let readLine = state (\(i, o) -> (head i, (tail i, o)))
  let encrypt = reverse
 
  createUser writeLine readLine encrypt
 
  actual <- gets snd
  let expected = [
        "Enter a username",
        "Enter your full name",
        "Enter your password",
        "Re-enter your password",
        "The passwords don't match"]
  return $ expected ~=? actual

You can see the third and final characterization test in the GitHub repository.

Refactored action #

With full test coverage I could proceed to refactor the createUser action, pulling in the two functions I'd test-driven into existence earlier:

createUser :: (Monad m, PrintfArg a)
           => (String -> m ()) -> m String -> (String -> a) -> m ()
createUser writeLine readLine encrypt = do
  writeLine "Enter a username"
  username <- readLine
  writeLine "Enter your full name"
  fullName <- readLine
  writeLine "Enter your password"
  password <- readLine
  writeLine "Re-enter your password"
  confirmPassword <- readLine
 
  writeLine $ either
    id
    (printf "Saving Details for User (%s, %s, %s)" username fullName . encrypt)
    (validatePassword =<< comparePasswords password confirmPassword)

Because createUser now calls comparePasswords and validatePassword, the type of the overall composition is also more concrete. That's really just an artefact of my (misguided?) decision to give each of the two helper functions types that are more concrete than necessary.

As you can see, I left the initial call-and-response sequence intact, since I didn't feel that it needed improvement.

Conclusion #

I ported the Legacy Security Manager kata to Haskell because I thought it'd be easy enough to port the code itself, and I also found the exercise compelling enough in its own right.

The most interesting point, I think, is that the createUser action remains testable without making any other concession to testability than turning it into a higher-order function. For pure functions, we would expect this to be the case, since pure functions are intrinsically testable, but for impure actions like createUser, this isn't a given. Interacting exclusively with the command-line API is, however, sufficiently simple that we can get by with the State monad. No free monad is needed, and so test-induced damage is kept at a minimum.

This blog is totally free, but if you like it, please consider supporting it.

Functor sums

2024-10-14T18:26:00+00:00

A choice of two or more functors gives rise to a functor. An article for object-oriented programmers.

This article is part of a series of articles about functor relationships. In this one you'll learn about a universal composition of functors. In short, if you have a sum type of functors, that data structure itself gives rise to a functor.

Together with other articles in this series, this result can help you answer questions such as: Does this data structure form a functor?

Not all generic types give rise to a (covariant) functor. Some are rather contravariant functors, and some are invariant.

If, on the other hand, you have a data type which is a sum of two or more (covariant) functors with the same type parameter, then the data type itself gives rise to a functor. You'll see some examples in this article.

Abstract shape in F# #

Before we look at some examples found in other code, it helps if we know what we're looking for. You'll see a C# example in a minute, but since sum types require so much ceremony in C#, we'll make a brief detour around F#.

Imagine that you have two lawful functors, F and G. Also imagine that you have a data structure that holds either an F<'a> value or a G<'a> value:

type FOrG<'a> = FOrGF of F<'a> | FOrGG of G<'a>

The name of the type is FOrG. In the FOrGF case, it holds an F<'a> value, and in the FOrGG case it holds a G<'a> value.

The point of this article is that since both F and G are (lawful) functors, then FOrG also gives rise to a functor. The composed map function can pattern-match on each case and call the respective map function that belongs to each of the two functors.

let map f forg =
    match forg with
    | FOrGF fa -> FOrGF (F.map f fa)
    | FOrGG ga -> FOrGG (G.map f ga)

For clarity I've named the values fa indicating f of a and ga indicating g of a.

Notice that it's an essential requirement that the individual functors (here F and G) are parametrized by the same type parameter (here 'a). If your data structure contains F<'a> and G<'b>, the 'theorem' doesn't apply.

Abstract shape in C# #

The same kind of abstract shape requires much more boilerplate in C#. When defining a sum type in a language that doesn't support them, we may instead either turn to the Visitor design pattern or alternatively use Church encoding. While the two are isomorphic, Church encoding is a bit simpler while the Visitor pattern seems more object-oriented. In this example I've chosen the simplicity of Church encoding.

Like in the above F# code, I've named the data structure the same, but it's now a class:

public sealed class FOrG<T>

Two constructors enable you to initialize it with either an F<T> or a G<T> value.

public FOrG(F<T> f)

public FOrG(G<T> g)

Notice that F<T> and G<T> share the same type parameter T. If a class had, instead, composed either F<T1> or G<T2>, the 'theorem' doesn't apply.

Finally, a Match method completes the Church encoding.

public TResult Match<TResult>(
    Func<F<T>, TResult> whenF,
    Func<G<T>, TResult> whenG)

Regardless of exactly what F and G are, you can add a Select method to FOrG<T> like this:

public FOrG<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return Match(
        whenF: f => new FOrG<TResult>(f.Select(selector)),
        whenG: g => new FOrG<TResult>(g.Select(selector)));
}

Since we assume that F and G are functors, which in C# idiomatically have a Select method, we pass the selector to their respective Select methods. f.Select returns a new F value, while g.Select returns a new G value, but there's a constructor for each case, so the composed Select method repackages those return values in new FOrG<TResult> objects.

I'll have more to say about how this generalizes to a sum of more than two alternatives, but first, let's consider some examples.

Open or closed endpoints #

The simplest example that I can think of is that of range endpoints. A range may be open, closed, or a mix thereof. Some mathematical notations use (1, 6] to indicate the range between 1 and 6, where 1 is excluded from the range, but 6 is included. An alternative notation is ]1, 6].

A given endpoint (1 and 6, above) is either open or closed, which implies a sum type. In F# I defined it like this:

type Endpoint<'a> = Open of 'a | Closed of 'a

If you're at all familiar with F#, this is clearly a discriminated union, which is just what the F# documentation calls sum types.

The article Range as a functor goes through examples in both Haskell, F#, and C#, demonstrating, among other points, how an endpoint sum type forms a functor.

Binary tree #

The next example we'll consider is the binary tree from A Binary Tree Zipper in C#. In the original Haskell Zippers article, the data type is defined like this:

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

Even if you're not familiar with Haskell syntax, the vertical bar (|) indicates a choice between the left-hand side and the right-hand side. Many programming languages use the | character for Boolean disjunction (or), so the syntax should be intuitive. In this definition, a binary tree is either empty or a node with a value and two subtrees. What interests us here is that it's a sum type.

One way this manifests in C# is in the choice of two alternative constructors:

public BinaryTree() : this(Empty.Instance)
{
}
 
public BinaryTree(T value, BinaryTree<T> left, BinaryTree<T> right)
    : this(new Node(value, left.root, right.root))
{
}

BinaryTree<T> clearly has a generic type parameter. Does the class give rise to a functor?

It does if it's composed from a sum of two functors. Is that the case?

On the 'left' side, it seems that we have nothing. In the Haskell code, it's called Empty. In the C# code, this case is represented by the parameterless constructor (also known as the default constructor). There's no T there, so that doesn't look much like a functor.

All is, however, not lost. We may view this lack of data as a particular value ('nothing') wrapped in the Const functor. In Haskell and F# a value without data is called unit and written (). In C# or Java you may think of it as void, although unit is a value that you can pass around, which isn't the case for void.

In Haskell, we could instead represent Empty as Const (), which is a bona-fide Functor instance that you can fmap:

ghci> emptyNode = Const ()
ghci> fmap (+1) emptyNode
Const ()

This examples pretends to 'increment' a number that isn't there. Not that you'd need to do this. I'm only showing you this to make the argument that the empty node forms a functor.

The 'right' side of the sum type is most succinctly summarized by the Haskell code:

Node a (Tree a) (Tree a)

It's a 'naked' generic value and two generic trees. In C# it's the parameter list

(T value, BinaryTree<T> left, BinaryTree<T> right)

Does that make a functor? Yes, it's a triple of a 'naked' generic value and two recursive subtrees, all sharing the same T. Just like in the previous article we can view a 'naked' generic value as equivalent to the Identity functor, so that parameter is a functor. The other ones are recursive types: They are of the same type as the type we're trying to evaluate, BinaryTree<T>. If we assume that that forms a functor, that triple is a product type of functors. From the previous article, we know that that gives rise to a functor.

This means that in C#, for example, you can add the idiomatic Select method:

public BinaryTree<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return Aggregate(
        whenEmpty: () => new BinaryTree<TResult>(),
        whenNode: (value, left, right) =>
            new BinaryTree<TResult>(selector(value), left, right));
}

In languages that support pattern-matching on sum types (such as F#), you'd have to match on each case and explicitly deal with the recursive mapping. Notice, however, that here I've used the Aggregate method to implement Select. The Aggregate method is the BinaryTree<T> class' catamorphism, and it already handles the recursion for us. In other words, left and right are already BinaryTree<TResult> objects.

What remains is only to tell Aggregate what to do when the tree is empty, and how to transform the 'naked' node value. The Select implementation handles the former by returning a new empty tree, and the latter by invoking selector(value).

Not only does the binary tree form a functor, but it turns out that the Zipper does as well, because the breadcrumbs also give rise to a functor.

Breadcrumbs #

The original Haskell Zippers article defines a breadcrumb for the binary tree Zipper like this:

data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) deriving (Show)

That's another sum type with generics on the left as well as the right. In C# the two options may be best illustrated by these two creation methods:

public static Crumb<T> Left<T>(T value, BinaryTree<T> right)
{
    return Crumb<T>.Left(value, right);
}
 
public static Crumb<T> Right<T>(T value, BinaryTree<T> left)
{
    return Crumb<T>.Right(value, left);
}

Notice that the Left and Right choices have the same structure: A 'naked' generic T value, and a BinaryTree<T> object. Only the names differ. This suggests that we only need to think about one of them, and then we can reuse our conclusion for the other.

As we've already done once, we consider a T value equivalent with Identity<T>, which is a functor. We've also, just above, established that BinaryTree<T> forms a functor. We have a product (argument list, or tuple) of functors, so that combination forms a functor.

Since this is true for both alternatives, this sum type, too, gives rise to a functor. This enables you to implement a Select method:

public Crumb<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return Match(
        (v, r) => Crumb.Left(selector(v), r.Select(selector)),
        (v, l) => Crumb.Right(selector(v), l.Select(selector)));
}

By now the pattern should be familiar. Call selector(v) directly on the 'naked' values, and pass selector to any other functors' Select method.

That's almost all the building blocks we have to declare BinaryTreeZipper<T> a functor as well, but we need one last theorem before we can do that. We'll conclude this work in the next article.

Higher arities #

Although we finally saw a 'real' triple product, all the sum types have involved binary choices between a 'left side' and a 'right side'. As was the case with functor products, the result generalizes to higher arities. A sum type with any number of cases forms a functor if all the cases give rise to a functor.

We can, again, use canonicalized forms to argue the case. (See Thinking with Types for a clear explanation of canonicalization of types.) A two-way choice is isomorphic to Either, and a three-way choice is isomorphic to Either a (Either b c). Just like it's possible to build triples, quadruples, etc. by nesting pairs, we can construct n-ary choices by nesting Eithers. It's the same kind of inductive reasoning.

This is relevant because just as Haskell's base library provides Data.Functor.Product for composing two (and thereby any number of) functors, it also provides Data.Functor.Sum for composing functor sums.

The Sum type defines two case constructors: InL and InR, but it's isomorphic with Either:

canonizeSum :: Sum f g a -> Either (f a) (g a)
canonizeSum (InL x) = Left x
canonizeSum (InR y) = Right y
 
summarizeEither :: Either (f a) (g a) -> Sum f g a
summarizeEither (Left x) = InL x
summarizeEither (Right y) = InR y

The point is that we can compose not only a choice of two, but of any number of functors, to a single functor type. A simple example is this choice between Maybe, list, or Tree:

maybeOrListOrTree :: Sum (Sum Maybe []) Tree String
maybeOrListOrTree = InL (InL (Just "foo"))

If we rather wanted to embed a list in that type, we can do that as well:

maybeOrListOrTree' :: Sum (Sum Maybe []) Tree String
maybeOrListOrTree' = InL (InR ["bar", "baz"])

Both values have the same type, and since it's a Functor instance, you can fmap over it:

ghci> fmap (elem 'r') maybeOrListOrTree
InL (InL (Just False))
ghci> fmap (elem 'r') maybeOrListOrTree'
InL (InR [True,False])

These queries examine each String to determine whether or not they contain the letter 'r', which only "bar" does.

The point, anyway, is that sum types of any arity form a functor if all the cases do.

Conclusion #

In the previous article, you learned that a functor product gives rise to a functor. In this article, you learned that a functor sum does, too. If a data structure contains a choice of two or more functors, then that data type itself forms a functor.

As the previous article argues, this is useful to know, particularly if you're working in a language with only partial support for functors. Mainstream languages aren't going to automatically turn such sums into functors, in the way that Haskell's Sum container almost does. Thus, knowing when you can safely give your generic types a Select method or map function may come in handy.

There's one more rule like this one.

Next: Functor compositions.

This blog is totally free, but if you like it, please consider supporting it.

The Const functor

2024-10-07T18:37:00+00:00

Package a constant value, but make it look like a functor. An article for object-oriented programmers.

This article is an instalment in an article series about functors. In previous articles, you've learned about useful functors such as Maybe and Either. You've also seen at least one less-than useful functor: The Identity functor. In this article, you'll learn about another (practically) useless functor called Const. You can skip this article if you want.

Like Identity, the Const functor may not be that useful, but it nonetheless exists. You'll probably not need it for actual programming tasks, but knowing that it exists, like Identity, can be a useful as an analysis tool. It may help you quickly evaluate whether a particular data structure affords various compositions. For example, it may enable you to quickly identify whether, say, a constant type and a list may compose to a functor.

This article starts with C#, then proceeds over F# to finally discuss Haskell's built-in Const functor. You can just skip the languages you don't care about.

C# Const class #

While C# supports records, and you can implement Const as one, I here present it as a full-fledged class. For readers who may not be that familiar with modern C#, a normal class may be more recognizable.

public sealed class Const<T1, T2>
{
    public T1 Value { get; }
 
    public Const(T1 value)
    {
        Value = value;
    }
 
    public Const<T1, TResult> Select<TResult>(Func<T2, TResult> selector)
    {
        return new Const<T1, TResult>(Value);
    }
 
    public override bool Equals(object obj)
    {
        return obj is Const<T1, T2> @const &&
               EqualityComparer<T1>.Default.Equals(Value, @const.Value);
    }
 
    public override int GetHashCode()
    {
        return -1584136870 + EqualityComparer<T1>.Default.GetHashCode(Value);
    }
}

The point of the Const functor is to make a constant value look like a functor; that is, a container that you can map from one type to another. The difference from the Identity functor is that Const doesn't allow you to map the constant. Rather, it cheats and pretends having a mappable type that, however, has no value associated with it; a phantom type.

In Const<T1, T2>, the T2 type parameter is the 'pretend' type. While the class contains a T1 value, it contains no T2 value. The Select method, on the other hand, maps T2 to TResult. The operation is close to being a no-op, but still not quite. While it doesn't do anything particularly practical, it does change the type of the returned value.

Here's a simple example of using the Select method:

Const<string, double> c = new Const<string, int>("foo").Select(i => Math.Sqrt(i));

The new c value also contains "foo". Only its type has changed.

If you find this peculiar, think of it as similar to mapping an empty list, or an empty Maybe value. In those cases, too, no values change; only the type changes. The difference between empty Maybe objects or empty lists, and the Const functor is that Const isn't empty. There is a value; it's just not the value being mapped.

Functor laws #

Although the Const functor doesn't really do anything, it still obeys the functor laws. To illustrate it (but not to prove it), here's an FsCheck property that exercises the first functor law:

[Property(QuietOnSuccess = true)]
public void ConstObeysFirstFunctorLaw(int i)
{
    var left = new Const<int, string>(i);
    var right = new Const<int, string>(i).Select(x => x);
 
    Assert.Equal(left, right);
}

If you think it over for a minute, this makes sense. The test creates a Const<int, string> that contains the integer i, and then proceeds to map the string that isn't there to 'itself'. Clearly, this doesn't change the i value contained in the Const<int, string> container.

In the same spirit, a property demonstrates the second functor law:

[Property(QuietOnSuccess = true)]
public void ConstObeysSecondFunctorLaw(
    Func<string, byte> f,
    Func<int, string> g,
    short s)
{
    Const<short, byte> left = new Const<short, int>(s).Select(g).Select(f);
    Const<short, byte> right = new Const<short, int>(s).Select(x => f(g(x)));
 
    Assert.Equal(left, right);
}

Again, the same kind of almost-no-op takes place. The g function first changes the int type to string, and then f changes the string type to byte, but no value ever changes; only the second type parameter. Thus, left and right remain equal, since they both contain the same value s.

F# Const #

In F# we may idiomatically express Const as a single-case union:

type Const<'v, 'a> = Const of 'v

Here I've chosen to name the first type parameter 'v (for value) in order to keep the 'functor type parameter' name 'a. This enables me to meaningfully annotate the functor mapping function with the type 'a -> 'b:

module Const =
    let get (Const x) = x
    let map (f : 'a -> 'b) (Const x : Const<'v, 'a>) : Const<'v, 'b> = Const x

Usually, you don't need to annotate F# functions like map, but in this case I added explicit types in order to make it a recognizable functor map.

I could also have defined map like this:

// 'a -> Const<'b,'c> -> Const<'b,'d>
let map f (Const x) = Const x

This still works, but is less recognizable as a functor map, since f may be any 'a. Notice that if type inference is left to its own devices, it names the input type Const<'b,'c> and the return type Const<'b,'d>. This also means that if you want to supply f as a mapping function, this is legal, because we may consider 'a ~ 'c -> 'd. It's still a functor map, but a less familiar representation.

Similar to the above C# code, two FsCheck properties demonstrate that the Const type obeys the functor laws.

[<Property(QuietOnSuccess = true)>]
let ``Const obeys first functor law`` (i : int) =
    let  left = Const i
    let right = Const i |> Const.map id
 
    left =! right
 
[<Property(QuietOnSuccess = true)>]
let ``Const obeys second functor law`` (f : string -> byte) (g : int -> string) (s : int16) =
    let  left = Const s |> Const.map g |> Const.map f
    let right = Const s |> Const.map (g >> f)
 
    left =! right

The assertions use Unquote's =! operator, which I usually read as should equal or must equal.

Haskell Const #

The Haskell base library already comes with a Const newtype.

You can easily create a new Const value:

ghci> Const "foo"
Const "foo"

If you inquire about its type, GHCi will tell you in a rather verbose way that the first type parameter is String, but the second may be any type b:

ghci> :t Const "foo"
Const "foo" :: forall {k} {b :: k}. Const String b

You can also map by 'incrementing' its non-existent second value:

ghci> (+1) <$> Const "foo"
Const "foo"
ghci> :t (+1) <$> Const "foo"
(+1) <$> Const "foo" :: Num b => Const String b

While the value remains Const "foo", the type of b is now constrained to a Num instance, which follows from the use of the + operator.

Functor law proofs #

If you look at the source code for the Functor instance, it looks much like its F# equivalent:

instance Functor (Const m) where
    fmap _ (Const v) = Const v

We can use equational reasoning with the notation that Bartosz Milewski uses to prove that both functor laws hold, starting with the first:

  fmap id (Const x)
= { definition of fmap }
  Const x

Clearly, there's not much to that part. What about the second functor law?

  fmap (g . f) (Const x)
= { definition of fmap }
  Const x
= { definition of fmap }
  fmap g (Const x)
= { definition of fmap }
  fmap g (fmap f (Const x))
= { definition of composition }
  (fmap g . fmap f) (Const x)

While that proof takes a few more steps, most are as trivial as the first proof.

Conclusion #

The Const functor is hardly a programming construct you'll use in your day-to-day work, but the fact that it exists can be used to generalize some results that involve functors. Now, whenever you have a result that involves a functor, you know that it also generalizes to constant values, just like the Identity functor teaches us that 'naked' type parameters can be thought of as functors.

To give a few examples, we may already know that Tree<T> (C# syntax) is a functor, but a 'naked' generic type parameter T also gives rise to a functor (Identity), as does a non-generic type (such as int or MyCustomClass).

Thus, if you have a function that operates on any functor, it may also, conceivably, operate on data structures that have non-generic types. This may for example be interesting when we begin to consider how functors compose.

Next: The State functor.

This blog is totally free, but if you like it, please consider supporting it.

Das verflixte Hunde-Spiel

2024-10-03T17:41:00+00:00

A puzzle kata, and a possible solution.

When I was a boy I had a nine-piece puzzle that I'd been gifted by the Swizz branch of my family. It's called Das verflixte Hunde-Spiel, which means something like the confounded dog game in English. And while a puzzle with nine pieces doesn't sound like much, it is, in fact, incredibly difficult.

It's just a specific incarnation of a kind of game that you've almost certainly encountered, too.

There are nine tiles, each with two dog heads and two dog ends. A dog may be coloured in one of four different patterns. The object of the game is to lay out the nine tiles in a 3x3 square so that all dog halves line up.

Game details #

The game is from 1979. Two of the tiles are identical, and, according to the information on the back of the box, two possible solutions exist. Described from top clockwise, the tiles are the following:

Brown head, grey head, umber tail, spotted tail
Brown head, spotted head, brown tail, umber tail
Brown head, spotted head, grey tail, umber tail
Brown head, spotted head, grey tail, umber tail
Brown head, umber head, spotted tail, grey tail
Grey head, brown head, spotted tail, umber tail
Grey head, spotted head, brown tail, umber tail
Grey head, umber head, brown tail, spotted tail
Grey head, umber head, grey tail, spotted tail

I've taken the liberty of using a shorthand for the patterns. The grey dogs are actually also spotted, but since there's only one grey pattern, the grey label is unambiguous. The dogs I've named umber are actually rather burnt umber, but that's too verbose for my tastes, so I just named them umber. Finally, the label spotted indicates dogs that are actually burnt umber with brown blotches.

Notice that there are two tiles with a brown head, a spotted head, a grey tail, and an umber tail.

The object of the game is to lay down the tiles in a 3x3 square so that all dogs fit. For further reference, I've numbered each position from one to nine like this:

What makes the game hard? There are nine cards, so if you start with the upper left corner, you have nine choices. If you just randomly put down the tiles, you now have eight left for the top middle position, and so on. Standard combinatorics indicate that there are at least 9! = 362,880 permutations.

That's not the whole story, however, since you can rotate each tile in four different ways. You can rotate the first tile four ways, the second tile four ways, etc. for a total of 4⁹ = 262,144 ways. Multiply these two numbers together, and you get 4⁹9! = 95,126,814,720 combinations. No wonder this puzzle is hard if there's only two solutions.

When analysed this way, however, there are actually 16 solutions, but that still makes it incredibly unlikely to arrive at a solution by chance. I'll get back to why there are 16 solutions later. For now, you should have enough information to try your hand with this game, if you'd like.

I found that the game made for an interesting kata: Write a program that finds all possible solutions to the puzzle.

If you'd like to try your hand at this exercise, I suggest that you pause reading here.

In the rest of the article, I'll outline my first attempt. Spoiler alert: I'll also show one of the solutions.

Types #

When you program in Haskell, it's natural to start by defining some types.

data Half = Head | Tail deriving (Show, Eq)

data Pattern = Brown | Grey | Spotted | Umber deriving (Show, Eq)

data Tile = Tile {
  top :: (Pattern, Half),
  right :: (Pattern, Half),
  bottom :: (Pattern, Half),
  left :: (Pattern, Half) }
  deriving (Show, Eq)

Each tile describes what you find on its top, right side, bottom, and left side.

We're also going to need a function to evaluate whether two halves match:

matches :: (Pattern, Half) -> (Pattern, Half) -> Bool
matches (p1, h1) (p2, h2) = p1 == p2 && h1 /= h2

This function demands that the patterns match, but that the halves are opposites.

You can use the Tile type and its constituents to define the nine tiles of the game:

tiles :: [Tile]
tiles =
  [
    Tile (Brown, Head) (Grey, Head) (Umber, Tail) (Spotted, Tail),
    Tile (Brown, Head) (Spotted, Head) (Brown, Tail) (Umber, Tail),
    Tile (Brown, Head) (Spotted, Head) (Grey, Tail) (Umber, Tail),
    Tile (Brown, Head) (Spotted, Head) (Grey, Tail) (Umber, Tail),
    Tile (Brown, Head) (Umber, Head) (Spotted, Tail) (Grey, Tail),
    Tile (Grey, Head) (Brown, Head) (Spotted, Tail) (Umber, Tail),
    Tile (Grey, Head) (Spotted, Head) (Brown, Tail) (Umber, Tail),
    Tile (Grey, Head) (Umber, Head) (Brown, Tail) (Spotted, Tail),
    Tile (Grey, Head) (Umber, Head) (Grey, Tail) (Spotted, Tail)
  ]

Because I'm the neatnik that I am, I've sorted the tiles in lexicographic order, but the solution below doesn't rely on that.

Brute force doesn't work #

Before I started, I cast around the internet to see if there was an appropriate algorithm for the problem. While I found a few answers on Stack Overflow, none of them gave me indication that any sophisticated algorithm was available. (Even so, there may be, and I just didn't find it.)

It seems clear, however, that you can implement some kind of recursive search-tree algorithm that cuts a branch off as soon as it realizes that it doesn't work. I'll get back to that later, so let's leave that for now.

Since I'd planned on writing the code in Haskell, I decided to first try something that might look like brute force. Because Haskell is lazily evaluated, you can sometimes get away with techniques that look wasteful when you're used to strict/eager evaluation. In this case, it turned out to not work, but it's often quicker to just make the attempt than trying to analyze the problem.

As already outlined, I first attempted a purely brute-force solution, betting that Haskell's lazy evaluation would be enough to skip over the unnecessary calculations:

allRotationsOf9 = replicateM 9 [0..3]

allRotations :: [Tile] -> [[Tile]]
allRotations ts = fmap (\rs -> (\(r, t) -> rotations t !! r) <$> zip rs ts) allRotationsOf9

allConfigurations :: [[Tile]]
allConfigurations = permutations tiles >>= allRotations

solutions = filter isSolution allConfigurations

My idea with the allConfigurations value was that it's supposed to enumerate all 95 billion combinations. Whether it actually does that, I was never able to verify, because if I try to run that code, my poor laptop runs for a couple of hours before it eventually runs out of memory. In other words, the GHCi process crashes.

I haven't shown isSolution or rotations, because I consider the implementations irrelevant. This attempt doesn't work anyway.

Now that I look at it, it's quite clear why this isn't a good strategy. There's little to be gained from lazy evaluation when the final attempt just attempts to filter a list. Even with lazy evaluation, the code still has to run through all 95 billion combinations.

Things might have been different if I just had to find one solution. With a little luck, it might be that the first solution appears after, say, a hundred million iterations, and lazy evaluation would then had meant that the remaining combinations would never run. Not so here, but hindsight is 20-20.

Search tree #

Back to the search tree idea. It goes like this: Start from the top left position and pick a random tile and rotation. Now pick an arbitrary tile that fits and place it to the right of it, and so on. As far as I can tell, you can always place the first four cards, but from there, you can easily encounter a combination that allows no further tiles. Here's an example:

None of the remaining five tiles fit in the fifth position. This means that we don't have to do any permutations that involve these four tiles in that combination. While the algorithm has to search through all five remaining tiles and rotations to discover that none fit in position 5, once it knows that, it doesn't have to go through the remaining four positions. That's 4⁴4! = 6,144 combinations that it can skip every time it discovers an impossible beginning. That doesn't sound like that much, but if we assume that this happens more often than not, it's still an improvement by orders of magnitude.

We may think of this algorithm as constructing a search tree, but immediately pruning all branches that aren't viable, as close to the root as possible.

Matches #

Before we get to the algorithm proper we need a few simple helper functions. One kind of function is a predicate that determines if a particular tile can occupy a given position. Since we may place any tile in any rotation in the first position, we don't need to write a predicate for that, but if we wanted to generalize, const True would do.

Whether or not we can place a given tile in the second position depends exclusively on the tile in the first position:

tile2Matches :: Tile -> Tile -> Bool
tile2Matches t1 t2 = right t1 `matches` left t2

If the right dog part of the first tile matches the left part of the second tile, the return value is True; otherwise, it's False. Note that I'm using infix notation for matches. I could also have written the function as

tile2Matches :: Tile -> Tile -> Bool
tile2Matches t1 t2 = matches (right t1) (left t2)

but it doesn't read as well.

In any case, the corresponding matching functions for the third and forth tile look similar:

tile3Matches :: Tile -> Tile -> Bool
tile3Matches t2 t3 = right t2 `matches` left t3

tile4Matches :: Tile -> Tile -> Bool
tile4Matches t1 t4 = bottom t1 `matches` top t4

Notice that tile4Matches compares the fourth tile with the first tile rather than the third tile, because position 4 is directly beneath position 1, rather than to the right of position 3 (cf. the grid above). For that reason it also compares the bottom of tile 1 to the top of the fourth tile.

The matcher for the fifth tile is different:

tile5Matches :: Tile -> Tile -> Tile -> Bool
tile5Matches t2 t4 t5 = bottom t2 `matches` top t5 && right t4 `matches` left t5

This is the first predicate that depends on two, rather than one, previous tiles. In position 5 we need to examine both the tile in position 2 and the one in position 4.

The same is true for position 6:

tile6Matches :: Tile -> Tile -> Tile -> Bool
tile6Matches t3 t5 t6 = bottom t3 `matches` top t6 && right t5 `matches` left t6

but then the matcher for position 7 looks like the predicate for position 4:

tile7Matches :: Tile -> Tile -> Bool
tile7Matches t4 t7 = bottom t4 `matches` top t7

This is, of course, because the tile in position 7 only has to consider the tile in position 4. Finally, not surprising, the two remaining predicates look like something we've already seen:

tile8Matches :: Tile -> Tile -> Tile -> Bool
tile8Matches t5 t7 t8 = bottom t5 `matches` top t8 && right t7 `matches` left t8

tile9Matches :: Tile -> Tile -> Tile -> Bool
tile9Matches t6 t8 t9 = bottom t6 `matches` top t9 && right t8 `matches` left t9

You may suggest that it'd be possible to reduce the number of predicates. After all, there's effectively only three different predicates: One that only looks at the tile to the left, one that only looks at the tile above, and one that looks both to the left and above.

Indeed, I could have boiled it down to just three functions:

matchesHorizontally :: Tile -> Tile -> Bool
matchesHorizontally x y = right x `matches` left y

matchesVertically :: Tile -> Tile -> Bool
matchesVertically x y = bottom x `matches` top y

matchesBoth :: Tile -> Tile -> Tile -> Bool
matchesBoth x y z = matchesVertically x z && matchesHorizontally y z

but I now run the risk of calling the wrong predicate from my implementation of the algorithm. As you'll see, I'll call each predicate by name at each appropriate step, but if I had only these three functions, there's a risk that I might mistakenly use matchesHorizontally when I should have used matchesVertically, or vice versa. Reducing eight one-liners to three one-liners doesn't really seem to warrant the risk.

Rotations #

In addition to examining whether a given tile fits in a given position, we also need to be able to rotate any tile:

rotateClockwise :: Tile -> Tile
rotateClockwise (Tile t r b l) = Tile l t r b

rotateCounterClockwise :: Tile -> Tile
rotateCounterClockwise (Tile t r b l) = Tile r b l t

upend :: Tile -> Tile
upend (Tile t r b l) = Tile b l t r

What is really needed, it turns out, is to enumerate all four rotations of a tile:

rotations :: Tile -> [Tile]
rotations t = [t, rotateClockwise t, upend t, rotateCounterClockwise t]

Since this, like everything else here, is a pure function, I experimented with defining a 'memoized tile' type that embedded all four rotations upon creation, so that the algorithm doesn't need to call the rotations function millions of times, but I couldn't measure any discernable performance improvement from it. There's no reason to make things more complicated than they need to be, so I didn't keep that change. (Since I do, however, use Git tactically i did, of course, stash the experiment.)

Permutations #

While I couldn't make things work by enumerating all 95 billion combinations, enumerating all 362,880 permutations of non-rotated tiles is well within the realm of the possible:

allPermutations :: [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
allPermutations =
  (\[t1, t2, t3, t4, t5, t6, t7, t8, t9] -> (t1, t2, t3, t4, t5, t6, t7, t8, t9))
  <$> permutations tiles

Doing this in GHCi on my old laptop takes 300 milliseconds, which is good enough compared to what comes next.

This list value uses permutations to enumerate all the permutations. You may already have noticed that it converts the result into a nine-tuple. The reason for that is that this enables the algorithm to pattern-match into specific positions without having to resort to the index operator, which is both partial and requires iteration of the list to reach the indexed element. Granted, the list is only nine elements long, and often the algorithm will only need to index to the fourth or fifth element. On the other hand, it's going to do it a lot. Perhaps it's a premature optimization, but if it is, it's at least one that makes the code more, rather than less, readable.

Algorithm #

I found it easiest to begin at the 'bottom' of what is effectively a recursive algorithm, even though I didn't implement it that way. At the 'bottom', I imagine that I'm almost done: That I've found eight tiles that match, and now I only need to examine if I can rotate the final tile so that it matches:

solve9th ::  (a, b, c, d, e, Tile, g, Tile, Tile)
         -> [(a, b, c, d, e, Tile, g, Tile, Tile)]
solve9th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile9Matches t6 t8) $ rotations t9
  return (t1, t2, t3, t4, t5, t6, t7, t8, match)

Recalling that Haskell functions compose from right to left, the function starts by enumerating the four rotations of the ninth and final tile t9. It then filters those four rotations by the tile9Matches predicate.

The match value is a rotation of t9 that matches t6 and t8. Whenever solve9th finds such a match, it returns the entire nine-tuple, because the assumption is that the eight first tiles are already valid.

Notice that the function uses do notation in the list monad, so it's quite possible that the first filter expression produces no match. In that case, the second line of code never runs, and instead, the function returns the empty list.

How do we find a tuple where the first eight elements are valid? Well, if we have seven valid tiles, we may consider the eighth and subsequently call solve9th:

solve8th ::  (a, b, c, d, Tile, Tile, Tile, Tile, Tile)
         -> [(a, b, c, d, Tile, Tile, Tile, Tile, Tile)]
solve8th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile8Matches t5 t7) $ rotations t8
  solve9th (t1, t2, t3, t4, t5, t6, t7, match, t9)

This function looks a lot like solve9th, but it instead enumerates the four rotations of the eighth tile t8 and filters with the tile8Matches predicate. Due to the do notation, it'll only call solve9th if it finds a match.

Once more, this function assumes that the first seven tiles are already in a legal constellation. How do we find seven valid tiles? The same way we find eight: By assuming that we have six valid tiles, and then finding the seventh, and so on:

solve7th ::  (a, b, c, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(a, b, c, Tile, Tile, Tile, Tile, Tile, Tile)]
solve7th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile7Matches t4) $ rotations t7
  solve8th (t1, t2, t3, t4, t5, t6, match, t8, t9)

solve6th ::  (a, b, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(a, b, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve6th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile6Matches t3 t5) $ rotations t6
  solve7th (t1, t2, t3, t4, t5, match, t7, t8, t9)

solve5th ::  (a, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(a, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve5th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile5Matches t2 t4) $ rotations t5
  solve6th (t1, t2, t3, t4, match, t6, t7, t8, t9)

solve4th ::  (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve4th (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile4Matches t1) $ rotations t4
  solve5th (t1, t2, t3, match, t5, t6, t7, t8, t9)

solve3rd ::  (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve3rd (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile3Matches t2) $ rotations t3
  solve4th (t1, t2, match, t4, t5, t6, t7, t8, t9)

solve2nd ::  (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve2nd (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- filter (tile2Matches t1) $ rotations t2
  solve3rd (t1, match, t3, t4, t5, t6, t7, t8, t9)

You'll observe that solve7th down to solve2nd are very similar. The only things that really vary are the predicates, and the positions of the tile being examined, as well as its neighbours. Clearly I can generalize this code, but I'm not sure it's worth it. I wrote a few of these in the order I've presented them here, because it helped me think the problem through, and to be honest, once I had two or three of them, GitHub Copilot picked up on the pattern and wrote the remaining functions for me.

Granted, typing isn't a programming bottleneck, so we should rather ask if this kind of duplication looks like a maintenance problem. Given that this is a one-time exercise, I'll just leave it be and move on.

Particularly, if you're struggling to understand how this implements the 'truncated search tree', keep in mind that e..g solve5th is likely to produce no valid match, in which case it'll never call solve6th. The same may happen in solve6th, etc.

The 'top' function is a bit different because it doesn't need to filter anything:

solve1st ::  (Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)
         -> [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solve1st (t1, t2, t3, t4, t5, t6, t7, t8, t9) = do
  match <- rotations t1
  solve2nd (match, t2, t3, t4, t5, t6, t7, t8, t9)

In the first position, any tile in any rotation is legal, so solve1st only enumerates all four rotations of t1 and calls solve2nd for each.

The final step is to compose allPermutations with solve1st:

solutions :: [(Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile, Tile)]
solutions = allPermutations >>= solve1st

Running this in GHCi on my 4½-year old laptop produces all 16 solutions in approximately 22 seconds.

Evaluation #

Is that good performance? Well, it turns out that it's possible to substantially improve on the situation. As I've mentioned a couple of times, so far I've been running the program from GHCi, the Haskell REPL. Most of the 22 seconds are spent interpreting or compiling the code.

If I compile the code with some optimizations turned on, the executable runs in approximately 300 ms. That seems quite decent, if I may say so.

I can think of a few tweaks to the code that might conceivably improve things even more, but when I test, there's no discernable difference. Thus, I'll keep the code as shown here.

Here's one of the solutions:

The information on the box claims that there's two solutions. Why does the code shown here produce 16 solutions?

There's a good explanation for that. Recall that two of the tiles are identical. In the above solution picture, it's tile 1 and 3, although they're rotated 90° in relation to each other. This implies that you could take tile 1, rotate it counter-clockwise and put it in position 3, while simultaneously taking tile 3, rotating it clockwise, and putting it in position 1. Visually, you can't tell the difference, so they don't count as two distinct solutions. The algorithm, however, doesn't make that distinction, so it enumerates what is effectively the same solution twice.

Not surprising, it turns out that all 16 solutions are doublets in that way. We can confirm that by evaluating length $ nub solutions, which returns 8.

Eight solutions are, however, still four times more than two. Can you figure out what's going on?

The algorithm also enumerates four rotations of each solution. Once we take this into account, there's only two visually distinct solutions left. One of them is shown above. I also have a picture of the other one, but I'm not going to totally spoil things for you.

Conclusion #

When I was eight, I might have had the time and the patience to actually lay the puzzle. Despite the incredibly bad odds, I vaguely remember finally solving it. There must be some more holistic processing going on in the brain, if even a kid can solve the puzzle, because it seems inconceivable that it should be done as described here.

Today, I don't care for that kind of puzzle in analog form, but I did, on the other hand, find it an interesting programming exercise.

The code could be smaller, but I like it as it is. While a bit on the verbose side, I think that it communicates well what's going on.

I was pleasantly surprised that I managed to get execution time down to 300 ms. I'd honestly not expected that when I started.

Comments

Andreas Källberg #

Thanks for a nice blog post! I found the challange interesting, so I have written my own version of the code that both tries to be faster and also remove the redundant solutions, so it only generates two solutions in total. The code is available here. It executes in roughly 8 milliseconds both in ghci and compiled (and takes a second to compile and run using runghc) on my laptop.

In order to improve the performance, I start with a blank grid and one-by-one add tiles until it is no longer possible to do so, and then bactrack, kind of like how you would do it by hand. As a tiny bonus, that I haven't actually measured if it makes any practical difference, I also selected the order of filling in the grid so that they can constrain each other as much as possible, by filling 2-by-2 squares as early as possible. I have however calculated the number of boards explored in each of the two variations. With a spiral order, 6852 boards are explored, while with a linear order, 9332 boards are explored.

In order to eliminate rotational symmetry, I start by filling the center square and fixing its rotation, rather than trying all rotations for it, since we could view any initial rotation of the center square as equivalent to rotating the whole board. In order to eliminate the identical solutions from the two identical tiles, I changed the encoding to use a number next to the tile to say how many copies are left of it, so when we choose a tile, there is only a single way to choose each tile, even if there are multiple copies of it. Both of these would also in theory make the code slightly faster if the time wasn't already dominated by general IO and other unrelated things.

I also added various pretty printing and tracing utilites to the code, so you can see exactly how it executes and which partial solutions it explores.

2024-10-16 00:32 UTC

Mark Seemann #

Thank you for writing. I did try filling the two-by-two square first, as you suggest, but in isolation it makes no discernable difference.

I haven't tried your two other optimizations. The one to eliminate rotations should, I guess, reduce the search space to a fourth of mine, unless I'm mistaken. That would reduce my 300 ms to approximately 75 ms.

I can't easily guess how much time the other optimization shaves off, but it could be the one that makes the bigger difference.

2024-10-19 08:21 UTC

This blog is totally free, but if you like it, please consider supporting it.

FSZipper in C#

2024-09-23T06:13:00+00:00

Another functional model of a file system, with code examples in C#.

This article is part of a series about Zippers. In this one, I port the FSZipper data structure from the Learn You a Haskell for Great Good! article Zippers.

A word of warning: I'm assuming that you're familiar with the contents of that article, so I'll skip the pedagogical explanations; I can hardly do it better that it's done there. Additionally, I'll make heavy use of certain standard constructs to port Haskell code, most notably Church encoding to model sum types in languages that don't natively have them. Such as C#. In some cases, I'll implement the Church encoding using the data structure's catamorphism. Since the cyclomatic complexity of the resulting code is quite low, you may be able to follow what's going on even if you don't know what Church encoding or catamorphisms are, but if you want to understand the background and motivation for that style of programming, you can consult the cited resources.

The code shown in this article is available on GitHub.

File system item initialization and structure #

If you haven't already noticed, Haskell (and other statically typed functional programming languages like F#) makes heavy use of sum types, and the FSZipper example is no exception. It starts with a one-liner to define a file system item, which may be either a file or a folder. In C# we must instead use a class:

public sealed class FSItem

Contrary to the two previous examples, the FSItem class has no generic type parameter. This is because I'm following the Haskell example code as closely as possible, but as I've previously shown, you can model a file hierarchy with a general-purpose rose tree.

Staying consistent with the two previous articles, I'll use Church encoding to model a sum type, and as discussed in the previous article I use a private implementation for that.

private readonly IFSItem imp;
 
private FSItem(IFSItem imp)
{
    this.imp = imp;
}
 
public static FSItem CreateFile(string name, string data)
{
    return new(new File(name, data));
}
 
public static FSItem CreateFolder(string name, IReadOnlyCollection<FSItem> items)
{
    return new(new Folder(name, items));
}

Two static creation methods enable client developers to create a single FSItem object, or an entire tree, like the example from the Haskell code, here ported to C#:

private static readonly FSItem myDisk =
    FSItem.CreateFolder("root",
    [
        FSItem.CreateFile("goat_yelling_like_man.wmv", "baaaaaa"),
        FSItem.CreateFile("pope_time.avi", "god bless"),
        FSItem.CreateFolder("pics",
        [
            FSItem.CreateFile("ape_throwing_up.jpg", "bleargh"),
            FSItem.CreateFile("watermelon_smash.gif", "smash!!"),
            FSItem.CreateFile("skull_man(scary).bmp", "Yikes!")
        ]),
        FSItem.CreateFile("dijon_poupon.doc", "best mustard"),
        FSItem.CreateFolder("programs",
        [
            FSItem.CreateFile("fartwizard.exe", "10gotofart"),
            FSItem.CreateFile("owl_bandit.dmg", "mov eax, h00t"),
            FSItem.CreateFile("not_a_virus.exe", "really not a virus"),
            FSItem.CreateFolder("source code",
            [
                FSItem.CreateFile("best_hs_prog.hs", "main = print (fix error)"),
                FSItem.CreateFile("random.hs", "main = print 4")
            ])
        ])
    ]);

Since the imp class field is just a private implementation detail, a client developer needs a way to query an FSItem object about its contents.

File system item catamorphism #

Just like the previous article, I'll start with the catamorphism. This is essentially the rose tree catamorphism, just less generic, since FSItem doesn't have a generic type parameter.

public TResult Aggregate<TResult>(
    Func<string, string, TResult> whenFile,
    Func<string, IReadOnlyCollection<TResult>, TResult> whenFolder)
{
    return imp.Aggregate(whenFile, whenFolder);
}

The Aggregate method delegates to its internal implementation class field, which is defined as the private nested interface IFSItem:

private interface IFSItem
{
    TResult Aggregate<TResult>(
        Func<string, string, TResult> whenFile,
        Func<string, IReadOnlyCollection<TResult>, TResult> whenFolder);
}

As discussed in the previous article, the interface is hidden away because it's only a vehicle for polymorphism. It's not intended for client developers to be used (although that would be benign) or implemented (which could break encapsulation). There are only, and should ever only be, two implementations. The one that represents a file is the simplest:

private sealed record File(string Name, string Data) : IFSItem
{
    public TResult Aggregate<TResult>(
        Func<string, string, TResult> whenFile,
        Func<string, IReadOnlyCollection<TResult>, TResult> whenFolder)
    {
        return whenFile(Name, Data);
    }
}

The File record's Aggregate method unconditionally calls the supplied whenFile function argument with the Name and Data that was originally supplied via its constructor.

The Folder implementation is a bit trickier, mostly due to its recursive nature, but also because I wanted it to have structural equality.

private sealed class Folder : IFSItem
{
    private readonly string name;
    private readonly IReadOnlyCollection<FSItem> items;
 
    public Folder(string Name, IReadOnlyCollection<FSItem> Items)
    {
        name = Name;
        items = Items;
    }
 
    public TResult Aggregate<TResult>(
        Func<string, string, TResult> whenFile,
        Func<string, IReadOnlyCollection<TResult>, TResult> whenFolder)
    {
        return whenFolder(
            name,
            items.Select(i => i.Aggregate(whenFile, whenFolder)).ToList());
    }
 
    public override bool Equals(object? obj)
    {
        return obj is Folder folder &&
               name == folder.name &&
               items.SequenceEqual(folder.items);
    }
 
    public override int GetHashCode()
    {
        return HashCode.Combine(name, items);
    }
}

It, too, unconditionally calls one of the two functions passed to its Aggregate method, but this time whenFolder. It does that, however, by first recursively calling Aggregate within a Select expression. It needs to do that because the whenFolder function expects the subtree to have been already converted to values of the TResult return type. This is a common pattern with catamorphisms, and takes a bit of time getting used to. You can see similar examples in the articles Tree catamorphism, Rose tree catamorphism, Full binary tree catamorphism, as well as the previous one in this series.

I also had to make Folder a class rather than a record, because I wanted the type to have structural equality, and you can't override Equals on records (and if the base class library has any collection type with structural equality, I'm not aware of it).

File system item Church encoding #

True to the structure of the previous article, the catamorphism doesn't look quite like a Church encoding, but it's possible to define the latter from the former.

public TResult Match<TResult>(
    Func<string, string, TResult> whenFile,
    Func<string, IReadOnlyCollection<FSItem>, TResult> whenFolder)
{
    return Aggregate(
        whenFile: (name, data) =>
            (item: CreateFile(name, data), result: whenFile(name, data)),
        whenFolder: (name, pairs) =>
        {
            var items = pairs.Select(i => i.item).ToList();
            return (CreateFolder(name, items), whenFolder(name, items));
        }).result;
}

The trick is the same as in the previous article: Build up an intermediate tuple that contains both the current item as well as the result being accumulated. Once the Aggregate method returns, the Match method returns only the result part of the resulting tuple.

I implemented the whenFolder expression as a code block, because both tuple elements needed the items collection. You can inline the Select expression, but that would cause it to run twice. That's probably a premature optimization, but it also made the code a bit shorter, and, one may hope, a bit more readable.

Fily system breadcrumb #

Finally, things seem to be becoming a little easier. The port of FSCrumb is straightforward.

public sealed class FSCrumb
{
    public FSCrumb(
        string name,
        IReadOnlyCollection<FSItem> left,
        IReadOnlyCollection<FSItem> right)
    {
        Name = name;
        Left = left;
        Right = right;
    }
 
    public string Name { get; }
    public IReadOnlyCollection<FSItem> Left { get; }
    public IReadOnlyCollection<FSItem> Right { get; }
 
    public override bool Equals(object? obj)
    {
        return obj is FSCrumb crumb &&
               Name == crumb.Name &&
               Left.SequenceEqual(crumb.Left) &&
               Right.SequenceEqual(crumb.Right);
    }
 
    public override int GetHashCode()
    {
        return HashCode.Combine(Name, Left, Right);
    }
}

The only reason this isn't a record is, once again, that I want to override Equals so that the type can have structural equality. Visual Studio wants me to convert to a primary constructor. That would simplify the code a bit, but actually not that much.

(I'm still somewhat conservative in my choice of new C# language features. Not that I have anything against primary constructors which, after all, F# has had forever. The reason I'm holding back is for didactic reasons. Not every reader is on the latest language version, and some readers may be using another programming language entirely. On the other hand, primary constructors seem natural and intuitive, so I may start using them here on the blog as well. I don't think that they're going to be much of a barrier to understanding.)

Now that we have both the data type we want to zip, as well as the breadcrumb type we need, we can proceed to add the Zipper.

File system Zipper #

The FSZipper C# class fills the position of the eponymous Haskell type alias. Data structure and initialization is straightforward.

public sealed class FSZipper
{
    private FSZipper(FSItem fSItem, IReadOnlyCollection<FSCrumb> breadcrumbs)
    {
        FSItem = fSItem;
        Breadcrumbs = breadcrumbs;
    }
 
    public FSZipper(FSItem fSItem) : this(fSItem, [])
    {
    }
 
    public FSItem FSItem { get; }
    public IReadOnlyCollection<FSCrumb> Breadcrumbs { get; }
 
    // Methods follow here...

True to the style I've already established, I've made the master constructor private in order to highlight that the Breadcrumbs are the responsibility of the FSZipper class itself. It's not something client code need worry about.

Going down #

The Haskell Zippers article introduces fsUp before fsTo, but if we want to see some example code, we need to navigate to somewhere before we can navigate up. Thus, I'll instead start with the function that navigates to a child node.

public FSZipper? GoTo(string name)
{
    return FSItem.Match(
        (_, _) => null,
        (folderName, items) =>
        {
            FSItem? item = null;
            var ls = new List<FSItem>();
            var rs = new List<FSItem>();
            foreach (var i in items)
            {
                if (item is null && i.IsNamed(name))
                    item = i;
                else if (item is null)
                    ls.Add(i);
                else
                    rs.Add(i);
            }
 
            if (item is null)
                return null;
 
            return new FSZipper(
                item,
                Breadcrumbs.Prepend(new FSCrumb(folderName, ls, rs)).ToList());
        });
}

This is by far the most complicated navigation we've seen so far, and I've even taken the liberty of writing an imperative implementation. It's not that I don't know how I could implement it in a purely functional fashion, but I've chosen this implementation for a couple of reasons. The first of which is that, frankly, it was easier this way.

This stems from the second reason: That the .NET base class library, as far as I know, offers no functionality like Haskell's break function. I could have written such a function myself, but felt that it was too much of a digression, even for me. Maybe I'll do that another day. It might make for a nice little exercise.

The third reason is that C# doesn't afford pattern matching on sequences, in the shape of destructuring the head and the tail of a list. (Not that I know of, anyway, but that language changes rapidly at the moment, and it does have some pattern-matching features now.) This means that I have to check item for null anyway.

In any case, while the implementation is imperative, an external caller can't tell. The GoTo method is still referentially transparent. Which means that it fits in your head.

You may have noticed that the implementation calls IsNamed, which is also new.

public bool IsNamed(string name)
{
    return Match((n, _) => n == name, (n, _) => n == name);
}

This is an instance method I added to FSItem.

In summary, the GoTo method enables client code to navigate down in the file hierarchy, as this unit test demonstrates:

[Fact]
public void GoToSkullMan()
{
    var sut = new FSZipper(myDisk);
 
    var actual = sut.GoTo("pics")?.GoTo("skull_man(scary).bmp");
 
    Assert.NotNull(actual);
    Assert.Equal(
        FSItem.CreateFile("skull_man(scary).bmp", "Yikes!"),
        actual.FSItem);
}

The example is elementary. First go to the pics folder, and from there to the skull_man(scary).bmp.

Going up #

Going back up the hierarchy isn't as complicated.

public FSZipper? GoUp()
{
    if (Breadcrumbs.Count == 0)
        return null;
 
    var head = Breadcrumbs.First();
    var tail = Breadcrumbs.Skip(1);
 
    return new FSZipper(
        FSItem.CreateFolder(head.Name, [.. head.Left, FSItem, .. head.Right]),
        tail.ToList());
}

If the Breadcrumbs collection is empty, we're already at the root, in which case we can't go further up. In that case, the GoUp method returns null, as does the GoTo method if it can't find an item with the desired name. This possibility is explicitly indicated by the FSZipper? return type; notice the question mark, which indicates that the value may be null. If you're working in a context or language where that feature isn't available, you may instead consider taking advantage of the Maybe monad (which is also what you'd idiomatically do in Haskell).

If Breadcrumbs is not empty, it means that there's a place to go up to. It also implies that the previous operation navigated down, and the only way that's possible is if the previous node was a folder. Thus, the GoUp method knows that it needs to reconstitute a folder, and from the head breadcrumb, it knows that folder's name, and what was originally to the Left and Right of the Zipper's FSItem property.

This unit test demonstrates how client code may use the GoUp method:

[Fact]
public void GoUpFromSkullMan()
{
    var sut = new FSZipper(myDisk);
    // This is the same as the GoToSkullMan test
    var newFocus = sut.GoTo("pics")?.GoTo("skull_man(scary).bmp");
 
    var actual = newFocus?.GoUp()?.GoTo("watermelon_smash.gif");
 
    Assert.NotNull(actual);
    Assert.Equal(
        FSItem.CreateFile("watermelon_smash.gif", "smash!!"),
        actual.FSItem);
}

This test first repeats the navigation also performed by the other test, then uses GoUp to go one level up, which finally enables it to navigate to the watermelon_smash.gif file.

Renaming a file or folder #

A Zipper enables you to navigate a data structure, but you can also use it to modify the element in focus. One option is to rename a file or folder.

public FSZipper Rename(string newName)
{
    return new FSZipper(
        FSItem.Match(
            (_, dat) => FSItem.CreateFile(newName, dat),
            (_, items) => FSItem.CreateFolder(newName, items)),
        Breadcrumbs);
}

The Rename method 'pattern-matches' on the 'current' FSItem and in both cases creates a new file or folder with the new name. Since it doesn't need the old name for anything, it uses the wildcard pattern to ignore that value. This operation is always possible, so the return type is FSZipper, without a question mark, indicating that the method never returns null.

The following unit test replicates the Haskell article's example by renaming the pics folder to cspi.

[Fact]
public void RenamePics()
{
    var sut = new FSZipper(myDisk);
 
    var actual = sut.GoTo("pics")?.Rename("cspi").GoUp();
 
    Assert.NotNull(actual);
    Assert.Empty(actual.Breadcrumbs);
    Assert.Equal(
        FSItem.CreateFolder("root",
        [
            FSItem.CreateFile("goat_yelling_like_man.wmv", "baaaaaa"),
            FSItem.CreateFile("pope_time.avi", "god bless"),
            FSItem.CreateFolder("cspi",
            [
                FSItem.CreateFile("ape_throwing_up.jpg", "bleargh"),
                FSItem.CreateFile("watermelon_smash.gif", "smash!!"),
                FSItem.CreateFile("skull_man(scary).bmp", "Yikes!")
            ]),
            FSItem.CreateFile("dijon_poupon.doc", "best mustard"),
            FSItem.CreateFolder("programs",
            [
                FSItem.CreateFile("fartwizard.exe", "10gotofart"),
                FSItem.CreateFile("owl_bandit.dmg", "mov eax, h00t"),
                FSItem.CreateFile("not_a_virus.exe", "really not a virus"),
                FSItem.CreateFolder("source code",
                [
                    FSItem.CreateFile("best_hs_prog.hs", "main = print (fix error)"),
                    FSItem.CreateFile("random.hs", "main = print 4")
                ])
            ])
        ]),
        actual.FSItem);
}

Since the test uses GoUp after Rename, the actual value contains the entire tree, while the Breadcrumbs collection is empty.

Adding a new file #

Finally, we can add a new file to a folder.

public FSZipper? Add(FSItem item)
{
    return FSItem.Match<FSZipper?>(
        whenFile: (_, _) => null,
        whenFolder: (name, items) => new FSZipper(
            FSItem.CreateFolder(name, items.Prepend(item).ToList()),
            Breadcrumbs));
}

This operation may fail, since we can't add a file to a file. This is, again, clearly indicated by the return type, which allows null.

This implementation adds the file to the start of the folder, but it would also be possible to add it at the end. I would consider that slightly more idiomatic in C#, but here I've followed the Haskell example code, which conses the new item to the beginning of the list. As is idiomatic in Haskell.

The following unit test reproduces the Haskell article's example.

[Fact]
public void AddPic()
{
    var sut = new FSZipper(myDisk);
 
    var actual = sut.GoTo("pics")?.Add(FSItem.CreateFile("heh.jpg", "lol"))?.GoUp();
 
    Assert.NotNull(actual);
    Assert.Equal(
        FSItem.CreateFolder("root",
        [
            FSItem.CreateFile("goat_yelling_like_man.wmv", "baaaaaa"),
            FSItem.CreateFile("pope_time.avi", "god bless"),
            FSItem.CreateFolder("pics",
            [
                FSItem.CreateFile("heh.jpg", "lol"),
                FSItem.CreateFile("ape_throwing_up.jpg", "bleargh"),
                FSItem.CreateFile("watermelon_smash.gif", "smash!!"),
                FSItem.CreateFile("skull_man(scary).bmp", "Yikes!")
            ]),
            FSItem.CreateFile("dijon_poupon.doc", "best mustard"),
            FSItem.CreateFolder("programs",
            [
                FSItem.CreateFile("fartwizard.exe", "10gotofart"),
                FSItem.CreateFile("owl_bandit.dmg", "mov eax, h00t"),
                FSItem.CreateFile("not_a_virus.exe", "really not a virus"),
                FSItem.CreateFolder("source code",
                [
                    FSItem.CreateFile("best_hs_prog.hs", "main = print (fix error)"),
                    FSItem.CreateFile("random.hs", "main = print 4")
                ])
            ])
        ]),
        actual.FSItem);
    Assert.Empty(actual.Breadcrumbs);
}

This example also follows the edit with a GoUp call, with the effect that the Zipper is once more focused on the entire tree. The assertion verifies that the new heh.jpg file is the first file in the pics folder.

Conclusion #

The code for FSZipper is actually a bit simpler than for the binary tree. This, I think, is mostly attributable to the FSZipper having fewer constituent sum types. While sum types are trivial, and extraordinarily useful in languages that natively support them, they require a lot of boilerplate in a language like C#.

Do you need something like FSZipper in C#? Probably not. As I've already discussed, this article series mostly exists as a programming exercise.

This blog is totally free, but if you like it, please consider supporting it.

Functor products

2024-09-16T06:08:00+00:00

A tuple or class of functors is also a functor. An article for object-oriented developers.

This article is part of a series of articles about functor relationships. In this one you'll learn about a universal composition of functors. In short, if you have a product type of functors, that data structure itself gives rise to a functor.

Together with other articles in this series, this result can help you answer questions such as: Does this data structure form a functor?

Since functors tend to be quite common, and since they're useful enough that many programming languages have special support or syntax for them, the ability to recognize a potential functor can be useful. Given a type like Foo<T> (C# syntax) or Bar<T1, T2>, being able to recognize it as a functor can come in handy. One scenario is if you yourself have just defined such a data type. Recognizing that it's a functor strongly suggests that you should give it a Select method in C#, a map function in F#, and so on.

Not all generic types give rise to a (covariant) functor. Some are rather contravariant functors, and some are invariant.

If, on the other hand, you have a data type which is a product of two or more (covariant) functors with the same type parameter, then the data type itself gives rise to a functor. You'll see some examples in this article.

Abstract shape #

Before we look at some examples found in other code, it helps if we know what we're looking for. Most (if not all?) languages support product types. In canonical form, they're just tuples of values, but in an object-oriented language like C#, such types are typically classes.

Imagine that you have two functors F and G, and you're now considering a data structure that contains a value of both types.

public sealed class FAndG<T>
{
    public FAndG(F<T> f, G<T> g)
    {
        F = f;
        G = g;
    }
 
    public F<T> F { get; }
    public G<T> G { get; }
 
    // Methods go here...

The name of the type is FAndG<T> because it contains both an F<T> object and a G<T> object.

Notice that it's an essential requirement that the individual functors (here F and G) are parametrized by the same type parameter (here T). If your data structure contains F<T1> and G<T2>, the following 'theorem' doesn't apply.

The point of this article is that such an FAndG<T> data structure forms a functor. The Select implementation is quite unsurprising:

public FAndG<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new FAndG<TResult>(F.Select(selector), G.Select(selector));
}

Since we've assumed that both F and G already are functors, they must come with some projection function. In C# it's idiomatically called Select, while in F# it'd typically be called map:

// ('a -> 'b) -> FAndG<'a> -> FAndG<'b>
let map f fandg = { F = F.map f fandg.F; G = G.map f fandg.G }

assuming a record type like

type FAndG<'a> = { F : F<'a>; G : G<'a> }

In both the C# Select example and the F# map function, the composed functor passes the function argument (selector or f) to both F and G and uses it to map both constituents. It then composes a new product from these individual results.

I'll have more to say about how this generalizes to a product of more than two functors, but first, let's consider some examples.

List Zipper #

One of the simplest example I can think of is a List Zipper, which in Haskell is nothing but a type alias of a tuple of lists:

type ListZipper a = ([a],[a])

In the article A List Zipper in C# you saw how the ListZipper<T> class composes two IEnumerable<T> objects.

private readonly IEnumerable<T> values;
public IEnumerable<T> Breadcrumbs { get; }
 
private ListZipper(IEnumerable<T> values, IEnumerable<T> breadcrumbs)
{
    this.values = values;
    Breadcrumbs = breadcrumbs;
}

Since we already know that sequences like IEnumerable<T> form functors, we now know that so must ListZipper<T>. And indeed, the Select implementation looks similar to the above 'shape outline'.

public ListZipper<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new ListZipper<TResult>(values.Select(selector), Breadcrumbs.Select(selector));
}

It passes the selector function to the Select method of both values and Breadcrumbs, and composes the results into a new ListZipper<TResult>.

While this example is straightforward, it may not be the most compelling, because ListZipper<T> composes two identical functors: IEnumerable<T>. The knowledge that functors compose is more general than that.

Non-empty collection #

Next after the above List Zipper, the simplest example I can think of is a non-empty list. On this blog I originally introduced it in the article Semigroups accumulate, but here I'll use the variant from NonEmpty catamorphism. It composes a single value of the type T with an IReadOnlyCollection<T>.

public NonEmptyCollection(T head, params T[] tail)
{
    if (head == null)
        throw new ArgumentNullException(nameof(head));
 
    this.Head = head;
    this.Tail = tail;
}
 
public T Head { get; }
 
public IReadOnlyCollection<T> Tail { get; }

The Tail, being an IReadOnlyCollection<T>, easily forms a functor, since it's a kind of list. But what about Head, which is a 'naked' T value? Does that form a functor? If so, which one?

Indeed, a 'naked' T value is isomorphic to the Identity functor. This situation is an example of how knowing about the Identity functor is useful, even if you never actually write code that uses it. Once you realize that T is equivalent with a functor, you've now established that NonEmptyCollection<T> composes two functors. Therefore, it must itself form a functor, and you realize that you can give it a Select method.

public NonEmptyCollection<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new NonEmptyCollection<TResult>(selector(Head), Tail.Select(selector).ToArray());
}

Notice that even though we understand that T is equivalent to the Identity functor, there's no reason to actually wrap Head in an Identity<T> container just to call Select on it and unwrap the result. Rather, the above Select implementation directly invokes selector with Head. It is, after all, a function that takes a T value as input and returns a TResult object as output.

Ranges #

It's hard to come up with an example that's both somewhat compelling and realistic, and at the same time prototypically pure. Stripped of all 'noise' functor products are just tuples, but that hardly makes for a compelling example. On the other hand, most other examples I can think of combine results about functors where they compose in more than one way. Not only as products, but also as sums of functors, as well as nested compositions. You'll be able to read about these in future articles, but for the next examples, you'll have to accept some claims about functors at face value.

In Range as a functor you saw how both Endpoint<T> and Range<T> are functors. The article shows functor implementations for each, in both C#, F#, and Haskell. For now we'll ignore the deeper underlying reason why Endpoint<T> forms a functor, and instead focus on Range<T>.

In Haskell I never defined an explicit Range type, but rather just treated ranges as tuples. As stated repeatedly already, tuples are the essential products, so if you accept that Endpoint gives rise to a functor, then a 'range tuple' does, too.

In F# Range is defined like this:

type Range<'a> = { LowerBound : Endpoint<'a>; UpperBound : Endpoint<'a> }

Such a record type is also easily identified as a product type. In a sense, we can think of a record type as a 'tuple with metadata', where the metadata contains names of elements.

In C# Range<T> is a class with two Endpoint<T> fields.

private readonly Endpoint<T> min;
private readonly Endpoint<T> max;
 
public Range(Endpoint<T> min, Endpoint<T> max)
{
    this.min = min;
    this.max = max;
}

In a sense, you can think of such an immutable class as equivalent to a record type, only requiring substantial ceremony. The point is that because a range is a product of two functors, it itself gives rise to a functor. You can see all the implementations in Range as a functor.

Binary tree Zipper #

In A Binary Tree Zipper in C# you saw that the BinaryTreeZipper<T> class has two class fields:

public BinaryTree<T> Tree { get; }
public IEnumerable<Crumb<T>> Breadcrumbs { get; }

Both have the same generic type parameter T, so the question is whether BinaryTreeZipper<T> may form a functor? We now know that the answer is affirmative if BinaryTree<T> and IEnumerable<Crumb<T>> are both functors.

For now, believe me when I claim that this is the case. This means that you can add a Select method to the class:

public BinaryTreeZipper<TResult> Select<TResult>(Func<T, TResult> selector)
{
    return new BinaryTreeZipper<TResult>(
        Tree.Select(selector),
        Breadcrumbs.Select(c => c.Select(selector)));
}

By now, this should hardly be surprising: Call Select on each constituent functor and create a proper return value from the results.

Higher arities #

All examples have involved products of only two functors, but the result generalizes to higher arities. To gain an understanding of why, consider that it's always possible to rewrite tuples of higher arities as nested pairs. As an example, a triple like (42, "foo", True) can be rewritten as (42, ("foo", True)) without loss of information. The latter representation is a pair (a two-tuple) where the first element is 42, but the second element is another pair. These two representations are isomorphic, meaning that we can go back and forth without losing data.

By induction you can generalize this result to any arity. The point is that the only data type you need to describe a product is a pair.

Haskell's base library defines a specialized container called Product for this very purpose: If you have two Functor instances, you can Pair them up, and they become a single Functor.

Let's start with a Pair of Maybe and a list:

ghci> Pair (Just "foo") ["bar", "baz", "qux"]
Pair (Just "foo") ["bar","baz","qux"]

This is a single 'object', if you will, that composes those two Functor instances. This means that you can map over it:

ghci> elem 'b' <$> Pair (Just "foo") ["bar", "baz", "qux"]
Pair (Just False) [True,True,False]

Here I've used the infix <$> operator as an alternative to fmap. By composing with elem 'b', I'm asking every value inside the container whether or not it contains the character b. The Maybe value doesn't, while the first two list elements do.

If you want to compose three, rather than two, Functor instances, you just nest the Pairs, just like you can nest tuples:

ghci> elem 'b' <$> Pair (Identity "quux") (Pair (Just "foo") ["bar", "baz", "qux"])
Pair (Identity False) (Pair (Just False) [True,True,False])

This example now introduces the Identity container as a third Functor instance. I could have used any other Functor instance instead of Identity, but some of them are more awkward to create or display. For example, the Reader or State functors have no Show instances in Haskell, meaning that GHCi doesn't know how to print them as values. Other Functor instances didn't work as well for the example, since they tend to be more awkward to create. As an example, any non-trivial Tree requires substantial editor space to express.

Conclusion #

A product of functors may itself be made a functor. The examples shown in this article are all constrained to two functors, but if you have a product of three, four, or more functors, that product still gives rise to a functor.

This is useful to know, particularly if you're working in a language with only partial support for functors. Mainstream languages aren't going to automatically turn such products into functors, in the way that Haskell's Product container almost does. Thus, knowing when you can safely give your generic types a Select method or map function may come in handy.

There are more rules like this one. The next article examines another.

Next: Functor sums.

This blog is totally free, but if you like it, please consider supporting it.

A Binary Tree Zipper in C#

2024-09-09T06:09:00+00:00

A port of another Haskell example, still just because.

This article is part of a series about Zippers. In this one, I port the Zipper data structure from the Learn You a Haskell for Great Good! article also called Zippers.

The code shown in this article is available on GitHub.

Binary tree initialization and structure #

In the Haskell code, the binary Tree type is a recursive sum type, defined on a single line of code. C#, on the other hand, has no built-in language construct that supports sum types, so a more elaborate solution is required. At least two options are available to us. One is to model a sum type as a Visitor. Another is to use Church encoding. In this article, I'll do the latter.

I find the type name (Tree) used in the Zippers article a bit too vague, and since I consider explicit better than implicit, I'll use a more precise class name:

public sealed class BinaryTree<T>

Even so, there are different kinds of binary trees. In a previous article I've shown a catamorphism for a full binary tree. This variation is not as strict, since it allows a node to have zero, one, or two children. Or, strictly speaking, a node always has exactly two children, but both, or one of them, may be empty. BinaryTree<T> uses Church encoding to distinguish between the two, but we'll return to that in a moment.

First, we'll examine how the class allows initialization:

private readonly IBinaryTree root;
 
private BinaryTree(IBinaryTree root)
{
    this.root = root;
}
 
public BinaryTree() : this(Empty.Instance)
{
}
 
public BinaryTree(T value, BinaryTree<T> left, BinaryTree<T> right)
    : this(new Node(value, left.root, right.root))
{
}

The class uses a private root object to implement behaviour, and constructor chaining for initialization. The master constructor is private, since the IBinaryTree interface is private. The parameterless constructor implicitly indicates an empty node, whereas the other public constructor indicates a node with a value and two children. Yes, I know that I just wrote that explicit is better than implicit, but it turns out that with the target-typed new operator feature in C#, constructing trees in code becomes easier with this design choice:

BinaryTree<int> sut = new(
    42,
    new(),
    new(2, new(), new()));

As the variable name suggests, I've taken this code example from a unit test.

Private interface #

The class delegates method calls to the root field, which is an instance of the private, nested IBinaryTree interface:

private interface IBinaryTree
{
    TResult Aggregate<TResult>(
        Func<TResult> whenEmpty,
        Func<T, TResult, TResult, TResult> whenNode);
}

Why is IBinaryTree a private interface? Why does that interface even exist?

To be frank, I could have chosen another implementation strategy. Since there's only two mutually exclusive alternatives (node or empty), I could also have indicated which is which with a Boolean flag. You can see an example of that implementation tactic in the Table class in the sample code that accompanies Code That Fits in Your Head.

Using a Boolean flag, however, only works when there are exactly two choices. If you have three or more, things because more complicated. You could try to use an enum, but in most languages, these tend to be nothing but glorified integers, and are typically not type-safe. If you define a three-way enum, there's no guarantee that a value of that type takes only one of these three values, and a good compiler will typically insist that you check for any other value as well. The C# compiler certainly does.

Church encoding offers a better alternative, but since it makes use of polymorphism, the most idiomatic choice in C# is either an interface or a base class. Since I favour interfaces over base classes, that's what I've chosen here, but for the purposes of this little digression, it makes no difference: The following argument applies to base classes as well.

An interface (or base class) suggests to users of an API that they can implement it in order to extend behaviour. That's an impression I don't wish to give client developers. The purpose of the interface is exclusively to enable double dispatch to work. There's only two implementations of the IBinaryTree interface, and under no circumstances should there be more.

The interface is an implementation detail, which is why both it, and its implementations, are private.

Binary tree catamorphism #

The IBinaryTree interface defines a catamorphism for the BinaryTree<T> class. Since we may often view a catamorphism as a sort of 'generalized fold', and since these kinds of operations in C# are typically called Aggregate, that's what I've called the method.

An aggregate function affords a way to traverse a data structure and collect information into a single value, here of type TResult. The return type may, however, be a complex type, including another BinaryTree<T>. You'll see examples of complex return values later in this article.

As already discussed, there are exactly two implementations of IBinaryTree. The one representing an empty node is the simplest:

private sealed class Empty : IBinaryTree
{
    public readonly static Empty Instance = new();
 
    private Empty()
    {
    }
 
    public TResult Aggregate<TResult>(
        Func<TResult> whenEmpty,
        Func<T, TResult, TResult, TResult> whenNode)
    {
        return whenEmpty();
    }
}

The Aggregate implementation unconditionally calls the supplied whenEmpty function, which returns some TResult value unknown to the Empty class.

Although not strictly necessary, I've made the class a Singleton. Since I like to take advantage of structural equality to write better tests, it was either that, or overriding Equals and GetHashCode.

The other implementation gets around that problem by being a record:

private sealed record Node(T Value, IBinaryTree Left, IBinaryTree Right) : IBinaryTree
{
    public TResult Aggregate<TResult>(
        Func<TResult> whenEmpty,
        Func<T, TResult, TResult, TResult> whenNode)
    {
        return whenNode(
            Value,
            Left.Aggregate(whenEmpty, whenNode),
            Right.Aggregate(whenEmpty, whenNode));
    }
}

It, too, unconditionally calls one of the two functions passed to its Aggregate method, but this time whenNode. It does that, however, by first recursively calling Aggregate on both Left and Right. It needs to do that because the whenNode function expects the subtrees to have been already converted to values of the TResult return type. This is a common pattern with catamorphisms, and takes a bit of time getting used to. You can see similar examples in the articles Tree catamorphism, Rose tree catamorphism, and Full binary tree catamorphism.

The BinaryTree<T> class defines a public Aggregate method that delegates to its root field:

public TResult Aggregate<TResult>(
    Func<TResult> whenEmpty,
    Func<T, TResult, TResult, TResult> whenNode)
{
    return root.Aggregate(whenEmpty, whenNode);
}

The astute reader may now remark that the Aggregate method doesn't look like a Church encoding.

Binary tree Church encoding #

A Church encoding will typically have a Match method that enables client code to match on all the alternative cases in the sum type, without those confusing already-converted TResult values. It turns out that you can implement the desired Match method with the Aggregate method.

One of the advantages of doing meaningless coding exercises like this one is that you can pursue various ideas that interest you. One idea that interests me is the potential universality of catamorphisms. I conjecture that a catamorphism is an algebraic data type's universal API, and that you can implement all other methods or functions with it. I admit that I haven't done much research in the form of perusing existing literature, but at least it seems to be the case conspicuously often.

As it is here.

public TResult Match<TResult>(
    Func<TResult> whenEmpty,
    Func<T, BinaryTree<T>, BinaryTree<T>, TResult> whenNode)
{
    return root
        .Aggregate(
            () => (tree: new BinaryTree<T>(), result: whenEmpty()),
            (x, l, r) => (
                new BinaryTree<T>(x, l.tree, r.tree),
                whenNode(x, l.tree, r.tree)))
        .result;
}

Now, I readily admit that it took me a couple of hours tossing and turning in my bed before this solution came to me. I don't find it intuitive at all, but it works.

The Aggregate method requires that the whenNode function's left and right values are of the same TResult type as the return type. How do we consolidate that requirement with the Match method's variation, where its whenNode function requires the left and right values to be BinaryTree<T> values, but the return type still TResult?

The way out of this conundrum, it turns out, is to combine both in a tuple. Thus, when Match calls Aggregate, the implied TResult type is not the TResult visible in the Match method declaration. Rather, it's inferred to be of the type (BinaryTree<T>, TResult). That is, a tuple where the first element is a BinaryTree<T> value, and the second element is a TResult value. The C# compiler's type inference engine then figures out that (BinaryTree<T>, TResult) must also be the return type of the Aggregate method call.

That's not what Match should return, but the second tuple element contains a value of the correct type, so it returns that. Since I've given the tuple elements names, the Match implementation accomplishes that by returning the result tuple field.

Breadcrumbs #

That's just the tree that we want to zip. So far, we can only move from root to branches, but not the other way. Before we can define a Zipper for the tree, we need a data structure to store breadcrumbs (the navigation log, if you will).

In Haskell it's just another one-liner, but in C# this requires another full-fledged class:

public sealed class Crumb<T>

It's another sum type, so once more, I make the constructor private and use a private class field for the implementation:

private readonly ICrumb imp;
 
private Crumb(ICrumb imp)
{
    this.imp = imp;
}
 
internal static Crumb<T> Left(T value, BinaryTree<T> right)
{
    return new(new LeftCrumb(value, right));
}
 
internal static Crumb<T> Right(T value, BinaryTree<T> left)
{
    return new(new RightCrumb(value, left));
}

To stay consistent throughout the code base, I also use Church encoding to distinguish between a Left and Right breadcrumb, and the technique is similar. First, define a private interface:

private interface ICrumb
{
    TResult Match<TResult>(
        Func<T, BinaryTree<T>, TResult> whenLeft,
        Func<T, BinaryTree<T>, TResult> whenRight);
}

Then, use private nested types to implement the interface.

private sealed record LeftCrumb(T Value, BinaryTree<T> Right) : ICrumb
{
    public TResult Match<TResult>(
        Func<T, BinaryTree<T>, TResult> whenLeft,
        Func<T, BinaryTree<T>, TResult> whenRight)
    {
        return whenLeft(Value, Right);
    }
}

The RightCrumb record is essentially just the 'mirror image' of the LeftCrumb record, and just as was the case with BinaryTree<T>, the Crumb<T> class exposes an externally accessible Match method that just delegates to the private class field:

public TResult Match<TResult>(
    Func<T, BinaryTree<T>, TResult> whenLeft,
    Func<T, BinaryTree<T>, TResult> whenRight)
{
    return imp.Match(whenLeft, whenRight);
}

Finally, all the building blocks are ready for the actual Zipper.

Zipper data structure and initialization #

In the Haskell code, the Zipper is another one-liner, and really just a type alias. In C#, once more, we're going to need a full class.

public sealed class BinaryTreeZipper<T>

The Haskell article simply calls this type alias Zipper, but I find that name too general, since there's more than one kind of Zipper. I think I understand that the article chooses that name for didactic reasons, but here I've chosen a more consistent disambiguation scheme, so I've named the class BinaryTreeZipper<T>.

The Haskell example is just a type alias for a tuple, and the C# class is similar, although with significantly more ceremony:

public BinaryTree<T> Tree { get; }
public IEnumerable<Crumb<T>> Breadcrumbs { get; }
 
private BinaryTreeZipper(
    BinaryTree<T> tree,
    IEnumerable<Crumb<T>> breadcrumbs)
{
    Tree = tree;
    Breadcrumbs = breadcrumbs;
}
 
public BinaryTreeZipper(BinaryTree<T> tree) : this(tree, [])
{
}

I've here chosen to add an extra bit of encapsulation by making the master constructor private. This prevents client code from creating an arbitrary object with breadcrumbs without having navigated through the tree. To be honest, I don't think it violates any contract even if we allow this, but it at least highlights that the Breadcrumbs role is to keep a log of what previously happened to the object.

Navigation #

We can now reproduce the navigation functions from the Haskell article.

public BinaryTreeZipper<T>? GoLeft()
{
    return Tree.Match<BinaryTreeZipper<T>?>(
        whenEmpty: () => null,
        whenNode: (x, l, r) => new BinaryTreeZipper<T>(
            l,
            Breadcrumbs.Prepend(Crumb.Left(x, r))));
}

Going left 'pattern-matches' on the Tree and, if not empty, constructs a new BinaryTreeZipper object with the left tree, and a Left breadcrumb that stores the 'current' node value and the right subtree. If the 'current' node is empty, on the other hand, the method returns null. This possibility is explicitly indicated by the BinaryTreeZipper<T>? return type; notice the question mark, which indicates that the value may be null. If you're working in a context or language where that feature isn't available, you may instead consider taking advantage of the Maybe monad (which is also what you'd idiomatically do in Haskell).

The GoRight method is similar to GoLeft.

We may also attempt to navigate up in the tree, undoing our last downward move:

public BinaryTreeZipper<T>? GoUp()
{
    if (!Breadcrumbs.Any())
        return null;
    var head = Breadcrumbs.First();
 
    var tail = Breadcrumbs.Skip(1);
    return head.Match(
        whenLeft: (x, r) => new BinaryTreeZipper<T>(
            new BinaryTree<T>(x, Tree, r),
            tail),
        whenRight: (x, l) => new BinaryTreeZipper<T>(
            new BinaryTree<T>(x, l, Tree),
            tail));
}

This is another operation that may fail. If we're already at the root of the tree, there are no Breadcrumbs, in which case the only option is to return a value indicating that the operation failed; here, null, but in other languages perhaps None or Nothing.

If, on the other hand, there's at least one breadcrumb, the GoUp method uses the most recent one (head) to construct a new BinaryTreeZipper<T> object that reconstitutes the opposite (sibling) subtree and the parent node. It does that by 'pattern-matching' on the head breadcrumb, which enables it to distinguish a left breadcrumb from a right breadcrumb.

Finally, we may keep trying to GoUp until we reach the root:

public BinaryTreeZipper<T> TopMost()
{
    return GoUp()?.TopMost() ?? this;
}

You'll see an example of that a little later.

Modifications #

Continuing the port of the Haskell code, we can Modify the current node with a function:

public BinaryTreeZipper<T> Modify(Func<T, T> f)
{
    return new BinaryTreeZipper<T>(
        Tree.Match(
            whenEmpty: () => new BinaryTree<T>(),
            whenNode: (x, l, r) => new BinaryTree<T>(f(x), l, r)),
        Breadcrumbs);
}

This operation always succeeds, since it chooses to ignore the change if the tree is empty. Thus, there's no question mark on the return type, indicating that the method never returns null.

Finally, we may replace a node with a new subtree:

public BinaryTreeZipper<T> Attach(BinaryTree<T> tree)
{
    return new BinaryTreeZipper<T>(tree, Breadcrumbs);
}

The following unit test demonstrates a combination of several of the methods shown above:

[Fact]
public void AttachAndGoTopMost()
{
    var sut = new BinaryTreeZipper<char>(freeTree);

    var farLeft = sut.GoLeft()?.GoLeft()?.GoLeft()?.GoLeft();
    var actual = farLeft?.Attach(new('Z', new(), new())).TopMost();
 
    Assert.NotNull(actual);
    Assert.Equal(
        new('P',
            new('O',
                new('L',
                    new('N',
                        new('Z', new(), new()),
                        new()),
                    new('T', new(), new())),
                new('Y',
                    new('S', new(), new()),
                    new('A', new(), new()))),
            new('L',
                new('W',
                    new('C', new(), new()),
                    new('R', new(), new())),
                new('A',
                    new('A', new(), new()),
                    new('C', new(), new())))),
        actual.Tree);
    Assert.Empty(actual.Breadcrumbs);
}

The test starts with freeTree (not shown) and first navigates to the leftmost empty node. Here it uses Attach to add a new 'singleton' subtree with the value 'Z'. Finally, it uses TopMost to return to the root node.

In the Assert phase, the test verifies that the actual object contains the expected values.

Conclusion #

The Tree Zipper shown here is a port of the example given in the Haskell Zippers article. As I've already discussed in the introduction article, this data structure doesn't make much sense in C#, where you can easily implement a navigable tree with two-way links. Even if this requires state mutation, you can package such a data structure in a proper object with good encapsulation, so that operations don't leave any dangling pointers or the like.

As far as I can tell, the code shown in this article isn't useful in production code, but I hope that, at least, you still learned something from it. I always learn a new thing or two from doing programming exercises and writing about them, and this was no exception.

In the next article, I continue with the final of the Haskell article's three examples.

Next: FSZipper in C#.

This blog is totally free, but if you like it, please consider supporting it.

Keeping cross-cutting concerns out of application code

2024-09-02T06:19:00+00:00

Don't inject third-party dependencies. Use Decorators.

I recently came across a Stack Overflow question that reminded me of a topic I've been meaning to write about for a long time: Cross-cutting concerns.

When it comes to the usual suspects, logging, fault tolerance, caching, the best solution is usually to apply the Decorator pattern.

I often see code that uses Dependency Injection (DI) to inject, say, a logging interface into application code. You can see an example of that in Repeatable execution, as well as a suggestion for a better design. Not surprisingly, the better design involves logging Decorators.

The Stack Overflow question isn't about logging, but rather about fault tolerance; Circuit Breaker, retry policies, timeouts, etc.

Injected concern #

The question does a good job of presenting a minimal, reproducible example. At the outset, the code looks like this:

public class MyApi
{
    private readonly ResiliencePipeline pipeline;
    private readonly IOrganizationService service;
 
    public MyApi(ResiliencePipelineProvider<string> provider, IOrganizationService service)
    {
        this.pipeline = provider.GetPipeline("retry-pipeline");
        this.service = service;
    }
 
    public List<string> GetSomething(QueryByAttribute query)
    {
        var result = this.pipeline.Execute(() => service.RetrieveMultiple(query));
        return result.Entities.Cast<string>().ToList();
    }
}

The Stack Overflow question asks how to test this implementation, but I'd rather take the example as an opportunity to discuss design alternatives. Not surprisingly, it turns out that with a more decoupled design, testing becomes easier, too.

Before we proceed, a few words about this example code. I assume that this isn't Andy Cooke's actual production code. Rather, I interpret it as a reduced example that highlights the actual question. This is important because you might ask: Why bother testing two lines of code?

Indeed, as presented, the GetSomething method is so simple that you may consider not testing it. Thus, I interpret the second line of code as a stand-in for more complicated production code. Hold on to that thought, because once I'm done, that's all that's going to be left, and you may then think that it's so simple that it really doesn't warrant all this hoo-ha.

Coupling #

As shown, the MyApi class is coupled to Polly, because ResiliencePipeline is defined by that library. To be clear, all I've heard is that Polly is a fine library. I've used it for a few projects myself, but I also admit that I haven't that much experience with it. I'd probably use it again the next time I need a Circuit Breaker or similar, so the following discussion isn't a denouncement of Polly. Rather, it applies to all third-party dependencies, or perhaps even dependencies that are part of your language's base library.

Coupling is a major cause of spaghetti code and code rot in general. To write sustainable code, you should be cognizant of coupling. The most decoupled code is code that you can easily delete.

This doesn't mean that you shouldn't use high-quality third-party libraries like Polly. Among myriads of software engineering heuristics, we know that we should be aware of the not-invented-here syndrome.

When it comes to classic cross-cutting concerns, the Decorator pattern is usually a better design than injecting the concern into application code. The above example clearly looks innocuous, but imagine injecting both a ResiliencePipeline, a logger, and perhaps a caching service, and your real application code eventually disappears in 'infrastructure code'.

It's not that we don't want to have these third-party dependencies, but rather that we want to move them somewhere else.

Resilient Decorator #

The concern in the above example is the desire to make the IOrganizationService dependency more resilient. The MyApi class only becomes more resilient as a transitive effect. The first refactoring step, then, is to introduce a resilient Decorator.

public sealed class ResilientOrganizationService(
    ResiliencePipeline pipeline,
    IOrganizationService inner) : IOrganizationService
{
    public QueryResult RetrieveMultiple(QueryByAttribute query)
    {
        return pipeline.Execute(() => inner.RetrieveMultiple(query));
    }
}

As Decorators must, this class composes another IOrganizationService while also implementing that interface itself. It does so by being an Adapter over the Polly API.

I've applied Nikola Malovic's 4th law of DI:

"Every constructor of a class being resolved should not have any implementation other then accepting a set of its own dependencies."

Inversion Of Control, Single Responsibility Principle and Nikola’s laws of dependency injection, Nikola Malovic, 2009

Instead of injecting a ResiliencePipelineProvider<string> only to call GetPipeline on it, it just receives a ResiliencePipeline and saves the object for use in the RetrieveMultiple method. It does that via a primary constructor, which is a recent C# language addition. It's just syntactic sugar for Constructor Injection, and as usual F# developers should feel right at home.

Simplifying MyApi #

Now that you have a resilient version of IOrganizationService you don't need to have any Polly code in MyApi. Remove it and simplify:

public class MyApi
{
    private readonly IOrganizationService service;
 
    public MyApi(IOrganizationService service)
    {
        this.service = service;
    }
 
    public List<string> GetSomething(QueryByAttribute query)
    {
        var result = service.RetrieveMultiple(query);
        return result.Entities.Cast<string>().ToList();
    }
}

As promised, there's almost nothing left of it now, but I'll remind you that I consider the second line of GetSomething as a stand-in for something more complicated that you might need to test. As it is now, though, testing it is trivial:

[Theory]
[InlineData("foo", "bar", "baz")]
[InlineData("qux", "quux", "corge")]
[InlineData("grault", "garply", "waldo")]
public void GetSomething(params string[] expected)
{
    var service = new Mock<IOrganizationService>();
    service
        .Setup(s => s.RetrieveMultiple(new QueryByAttribute()))
        .Returns(new QueryResult(expected));
    var sut = new MyApi(service.Object);
 
    var actual = sut.GetSomething(new QueryByAttribute());
 
    Assert.Equal(expected, actual);
}

The larger point, however, is that not only have you now managed to keep third-party dependencies out of your application code, you've also simplified it and made it easier to test.

Composition #

You can still create a resilient MyApi object in your Composition Root:

var service = new ResilientOrganizationService(pipeline, inner);
var myApi = new MyApi(service);

Decomposing the problem in this way, you decouple your application code from third-party dependencies. You can define ResilientOrganizationService in the application's Composition Root, which also keeps the Polly dependency there. Even so, you can implement MyApi as part of your application layer.

I usually illustrate Ports and Adapters, or, if you will, Clean Architecture as concentric circles, but in this diagram I've skewed the circles to make space for the boxes. In other words, the diagram is 'not to scale'. Ideally, the outermost layer is much smaller and thinner than any of the the other layers. I've also included an inner green layer which indicates the architecture's Domain Model, but since I assume that MyApi is part of some application layer, I've left the Domain Model empty.

Reasons to decouple #

Why is it important to decouple application code from Polly? First, keep in mind that in this discussion Polly is just a stand-in for any third-party dependency. It's up to you as a software architect to decide how you'll structure your code, but third-party dependencies are one of the first things I look for. A third-party component changes with time, and often independently of your base platform. You may have to deal with breaking changes or security patches at inopportune times. The organization that maintains the component may cease to operate. This happens to commercial entities and open-source contributors alike, although for different reasons.

Second, even a top-tier library like Polly will undergo changes. If your time horizon is five to ten years, you'll be surprised how much things change. You may protest that no-one designs software systems with such a long view, but I think that if you ask the business people involved with your software, they most certainly expect your system to last a long time.

I believe that I heard on a podcast that some Microsoft teams had taken a dependency on Polly. Assuming, for the sake of argument, that this is true, while we may not wish to depend on some random open-source component, depending on Polly is safe, right? In the long run, it isn't. Five years ago, you had the same situation with Json.NET, but then Microsoft hired James Newton-King and had him make a JSON API as part of the .NET base library. While Json.NET isn't dead by any means, now you have two competing JSON libraries, and Microsoft uses their own in the frameworks and libraries that they release.

Deciding to decouple your application code from a third-party component is ultimately a question of risk management. It's up to you to make the bet. Do you pay the up-front cost of decoupling, or do you postpone it, hoping it'll never be necessary?

I usually do the former, because the cost is low, and there are other benefits as well. As I've already touched on, unit testing becomes easier.

Configuration #

Since Polly only lives in the Composition Root, you'll also need to define the ResiliencePipeline there. You can write the code that creates that pieline wherever you like, but it might be natural to make it a creation function on the ResilientOrganizationService class:

public static ResiliencePipeline CreatePipeline()
{
    return new ResiliencePipelineBuilder()
        .AddRetry(new RetryStrategyOptions
        {
            MaxRetryAttempts = 4
        })
        .AddTimeout(TimeSpan.FromSeconds(1))
        .Build();
}

That's just an example, and perhaps not what you'd like to do. Perhaps you rather want some of these values to be defined in a configuration file. Thus, this isn't what you have to do, but rather what you could do.

If you use this option, however, you could take the return value of this method and inject it into the ResilientOrganizationService constructor.

Conclusion #

Cross-cutting concerns, like caching, logging, security, or, in this case, fault tolerance, are usually best addressed with the Decorator pattern. In this article, you saw an example of using the Decorator pattern to decouple the concern of fault tolerance from the consumer of the service that you need to handle in a fault-tolerant manner.

The specific example dealt with the Polly library, but the point isn't that Polly is a particularly nasty third-party component that you need to protect yourself against. Rather, it just so happened that I came across a Stack Overflow question that used Polly, and I though it was a a nice example.

As far as I can tell, Polly is actually one of the top .NET open-source packages, so this article is not a denouncement of Polly. It's just a sketch of how to move useful dependencies around in your code base to make sure that they impact your application code as little as possible.

This blog is totally free, but if you like it, please consider supporting it.

A List Zipper in C#

2024-08-26T13:19:00+00:00

A port of a Haskell example, just because.

This article is part of a series about Zippers. In this one, I port the ListZipper data structure from the Learn You a Haskell for Great Good! article also called Zippers.

A word of warning: I'm assuming that you're familiar with the contents of that article, so I'll skip the pedagogical explanations; I can hardly do it better that it's done there.

The code shown in this article is available on GitHub.

Initialization and structure #

In the Haskell code, ListZipper is just a type alias, but C# doesn't have that, so instead, we'll have to introduce a class.

public sealed class ListZipper<T> : IEnumerable<T>

Since it implements IEnumerable<T>, it may be used like any other sequence, but it also comes with some special operations that enable client code to move forward and backward, as well as inserting and removing values.

The class has the following fields, properties, and constructors:

private readonly IEnumerable<T> values;
public IEnumerable<T> Breadcrumbs { get; }
 
private ListZipper(IEnumerable<T> values, IEnumerable<T> breadcrumbs)
{
    this.values = values;
    Breadcrumbs = breadcrumbs;
}
 
public ListZipper(IEnumerable<T> values) : this(values, [])
{
}
 
public ListZipper(params T[] values) : this(values.AsEnumerable())
{
}

It uses constructor chaining to initialize a ListZipper object with proper encapsulation. Notice that the master constructor is private. This prevents client code from initializing an object with arbitrary Breadcrumbs. Rather, the Breadcrumbs (the log, if you will) is going to be the result of various operations performed by client code, and only the ListZipper class itself can use this constructor.

You may consider the constructor that takes a single IEnumerable<T> as the 'main' public constructor, and the other one as a convenience that enables a client developer to write code like new ListZipper<string>("foo", "bar", "baz").

The class' IEnumerable<T> implementation only enumerates the values:

public IEnumerator<T> GetEnumerator()
{
    return values.GetEnumerator();
}

In other words, when enumerating a ListZipper, you only get the 'forward' values. Client code may still examine the Breadcrumbs, since this is a public property, but it should have little need for that.

(I admit that making Breadcrumbs public is a concession to testability, since it enabled me to write assertions against this property. It's a form of structural inspection, which is a technique that I use much less than I did a decade ago. Still, in this case, while you may argue that it violates information hiding, it at least doesn't allow client code to put an object in an invalid state. Had the ListZipper class been a part of a reusable library, I would probably have hidden that data, too, but since this is exercise code, I found this an acceptable compromise. Notice, too, that in the original Haskell code, the breadcrumbs are available to client code.)

Regular readers of this blog may be aware that I usually favour IReadOnlyCollection<T> over IEnumerable<T>. Here, on the other hand, I've allowed values to be any IEnumerable<T>, which includes infinite sequences. I decided to do that because Haskell lists, too, may be infinite, and as far as I can tell, ListZipper actually does work with infinite sequences. I have, at least, written a few tests with infinite sequences, and they pass. (I may still have missed an edge case or two. I can't rule that out.)

Movement #

It's not much fun just being able to initialize an object. You also want to be able to do something with it, such as moving forward:

public ListZipper<T>? GoForward()
{
    var head = values.Take(1);
    if (!head.Any())
        return null;
 
    var tail = values.Skip(1);
    return new ListZipper<T>(tail, head.Concat(Breadcrumbs));
}

You can move forward through any IEnumerable, so why make things so complicated? The benefit of this GoForward method (function, really) is that it records where it came from, which means that moving backwards becomes an option:

public ListZipper<T>? GoBack()
{
    var head = Breadcrumbs.Take(1);
    if (!head.Any())
        return null;
 
    var tail = Breadcrumbs.Skip(1);
    return new ListZipper<T>(head.Concat(values), tail);
}

This test may serve as an example of client code that makes use of those two operations:

[Fact]
public void GoBack1()
{
    var sut = new ListZipper<int>(1, 2, 3, 4);
 
    var actual = sut.GoForward()?.GoForward()?.GoForward()?.GoBack();
 
    Assert.Equal([3, 4], actual);
    Assert.Equal([2, 1], actual?.Breadcrumbs);
}

Going forward takes the first element off values and adds it to the front of Breadcrumbs. Going backwards is nearly symmetrical: It takes the first element off the Breadcrumbs and adds it back to the front of the values. Used in this way, Breadcrumbs works as a stack.

Notice that both GoForward and GoBack admit the possibility of failure. If values is empty, you can't go forward. If Breadcrumbs is empty, you can't go back. In both cases, the functions return null, which are also indicated by the ListZipper<T>? return types; notice the question mark, which indicates that the value may be null. If you're working in a context or language where that feature isn't available, you may instead consider taking advantage of the Maybe monad (which is also what you'd idiomatically do in Haskell).

To be clear, the Zippers article does discuss handling failures using Maybe, but only applies it to its binary tree example. Thus, the error handling shown here is my own addition.

Modifications #

In addition to moving back and forth in the list, we can also modify it. The following operations are also not in the Zippers article, but are rather my own contributions. Adding a new element is easy:

public ListZipper<T> Insert(T value)
{
    return new ListZipper<T>(values.Prepend(value), Breadcrumbs);
}

Notice that this operation is always possible. Even if the list is empty, we can Insert a value. In that case, it just becomes the list's first and only element.

A simple test demonstrates usage:

[Fact]
public void InsertAtFocus()
{
    var sut = new ListZipper<string>("foo", "bar");
 
    var actual = sut.GoForward()?.Insert("ploeh").GoBack();
 
    Assert.NotNull(actual);
    Assert.Equal(["foo", "ploeh", "bar"], actual);
    Assert.Empty(actual.Breadcrumbs);
}

Likewise, we may attempt to remove an element from the list:

public ListZipper<T>? Remove()
{
    if (!values.Any())
        return null;
 
    return new ListZipper<T>(values.Skip(1), Breadcrumbs);
}

Contrary to Insert, the Remove operation will fail if values is empty. Notice that this doesn't necessarily imply that the list as such is empty, but only that the focus is at the end of the list (which, of course, never happens if values is infinite):

[Fact]
public void RemoveAtEnd()
{
    var sut = new ListZipper<string>("foo", "bar").GoForward()?.GoForward();
 
    var actual = sut?.Remove();
 
    Assert.Null(actual);
    Assert.NotNull(sut);
    Assert.Empty(sut);
    Assert.Equal(["bar", "foo"], sut.Breadcrumbs);
}

In this example, the focus is at the end of the list, so there's nothing to remove. The list, however, is not empty, but all the data currently reside in the Breadcrumbs.

Finally, we can combine insertion and removal to implement a replacement operation:

public ListZipper<T>? Replace(T newValue)
{
    return Remove()?.Insert(newValue);
}

As the name implies, this operation replaces the value currently in focus with a completely different value. Here's an example:

[Fact]
public void ReplaceAtFocus()
{
    var sut = new ListZipper<string>("foo", "bar", "baz");
 
    var actual = sut.GoForward()?.Replace("qux")?.GoBack();
 
    Assert.NotNull(actual);
    Assert.Equal(["foo", "qux", "baz"], actual);
    Assert.Empty(actual.Breadcrumbs);
}

Once more, this may fail if the current focus is empty, so Replace also returns a nullable value.

Conclusion #

For a C# developer, the ListZipper<T> class looks odd. Why would you ever want to use this data structure? Why not just use List<T>?

As I hope I've made clear in the introduction article, I can't, indeed, think of a good reason.

I've gone through this exercise to hone my skills, and to prepare myself for the more intimidating exercise it is to implement a binary tree Zipper.

Next: A Binary Tree Zipper in C#.

This blog is totally free, but if you like it, please consider supporting it.

Zippers

2024-08-19T14:13:00+00:00

Some functional programming examples ported to C#, just because.

Many algorithms rely on data structures that enable the implementation to move in more than one way. A simple example is a doubly-linked list, where an algorithm can move both forward and backward from a given element. Other examples are various tree-based algorithms, such as red-black trees where certain operations trigger reorganization of the tree. Yet other data structures, such as Fibonacci heaps, combine doubly-linked lists with trees that allow navigation in more than one direction.

In an imperative programming language, you can easily implement such data structures, as long as the language allows data mutation. Here's a simple example:

var node1 = new Node<string>("foo");
var node2 = new Node<string>("bar") { Previous = node1 };
node1.Next = node2;

It's possible to double-link node1 to node2 by first creating node1. At that point, node2 still doesn't exist, so you can't yet assign node1.Next, but once you've initialized node2, you can mutate the state of node1 by changing its Next property.

When data structures are immutable (as they must be in functional programming) this is no longer possible. How may you get around that limitation?

Alternatives #

Some languages get around this problem in various ways. Haskell, because of its lazy evaluation, enables a technique called tying the knot that, frankly, makes my head hurt.

Even though I write a decent amount of Haskell code, that's not something that I make use of. Usually, it turns out, you can solve most problems by thinking about them differently. By choosing another perspective, and another data structure, you can often arrive at a good, functional solution to your problem.

One family of general-purpose data structures are called Zippers. The general idea is that the data structure has a natural 'focus' (e.g. the head of a list), but it also keeps a record of 'breadcrumbs', that is, where the caller has previously been. This enables client code to 'go back' or 'go up', if the natural direction is to 'go forward' or 'go down'. It's a bit like Event Sourcing, in that every operation leaves a log entry that can later be used to reconstruct what happened. Repeatable Execution also comes to mind, although it's not quite the same.

For an introduction to Zippers, I recommend the excellent and highly readable article Zippers. In this article series, I'm going to assume that you're familiar with the contents of that article.

C# ports #

While I may add more articles to this series in the future, as I'm writing this, I have nothing more planned than writing about how it's possible to implement the article's three Zippers in C#.

Why would you want to do this?

To be honest, for production code, I can't think of a good reason. I did it for a few reasons, most of them didactic. Additionally, writing code for exercise helps you improve. If you know enough Haskell to understand what's going on in the Zippers article, you may consider porting some of it to your favourite language, as an exercise.

It may help you grokking functional programming.

That's really it, though. There's no reason to use Zippers in a language like C#, which idiomatically makes use of mutation. If you want a doubly-linked list, you can just write code as shown in the beginning of this article.

If you're interested in an F# perspective on Zippers, Tomas Petricek has a cool article: Processing trees with F# zipper computation.

Conclusion #

Zippers constitute a family of data structures that enables you to move in multiple directions. Left and right in a list. Up or down in a tree. For an imperative programmer, that's literally just another day at the office, but in disciplined functional programming, making cyclic graphs can be surprisingly tricky.

Even in functional programming, I rarely reach for a Zipper, since I can often find a library with a higher level of abstraction that does what I need it to do. Still, learning of new ways to solve problems never seems a waste to me.

In the next three articles, I'll go through the examples from the Zipper article and show how I ported them to C#. While that article starts with a binary tree, I'll instead begin with the doubly-linked list, since it's the simplest of the three.

Next: A List Zipper in C#.

This blog is totally free, but if you like it, please consider supporting it.