all Technical posts

Takeaways From Testing Recursive Types in F#

This post will delve into essential practical considerations when conducting property tests for recursive types. These crucial aspects naturally arise when you thoroughly validate such structures.

Generate the structure before generating the type

‘People think in examples’ is one of the arguments for including example-based unit tests alongside your property-based tests. In testing recursive types, it quickly becomes clear that generating a recursive domain type will become troublesome to do directly. The reason for this is that these types work with strict requirements and rules that we can’t always provide when generating the type. The DTO types, on the other hand, are usually a flat list with parent/child IDs that can easily be transferred, stored, and therefore generated more easily. The problem here though is that we want to represent our ‘example’ in a flat list. That’s why we first need to generate the structure before flattening.

Usually, a simple ‘reverse’ property is used to test the DTO-Domain conversion. However, it would be better if the recursive type could also be tested just like any other domain type. That is why I came up with this simple abstract Tree type:

Because of its abstract nature, it is easy to represent a structure rather than a type directly.

Extract structure traverse functionality

Once the abstract structure is extracted, the next problem becomes clear: traversing the tree. We will need traversing in our domain model, but also the same traverse functionality to go from our structure to a flat DTO type list. It is therefore easier and more workable to immediately extract the traverse functionality and reuse it both in implementation and test code.

Here is the temporary fold function for this abstract tree. Note that this still represents a structure, whether it be a domain or DTO type. Like all foldable functionality, let’s go from one type to another.

👀 Two things to notice about this fold function:

  1. The folder function gets in both the depth count and parent of each level in the tree. The depth is something that is required for lots of reasons and is probably one of the first limits against which the recursive domain model will validate (more on that later). Knowing the parent of each node, at each level, will help us to traverse recursive types to non-recursive types (like a flat DTO-type list).
  2. The getChildren function lets us choose where the children should be retrieved from at each branch. Because of this function, the foldable functionality is completely independent of any structure, even from our previously defined Tree type.

Know your limits, test your limits

One of the first domain validations of recursive types is probably about the maximum depth and width of the structure. We need to set clear boundaries so as not to overload the type and system, like any other user or external input. How many levels can the structure have? How many siblings can the structure have on each level? These are questions that need to be asked. After an answer is formulated, the immediate response would be to test this with ‘too deep’ and ‘too wide’ structures.

As we use an abstract structure, we can generate ‘invalid’ structures more easily. It is easier to think about a structure than to try to generate a flat list directly, and that is the reason for this whole exercise. The true benefit is represented here,  as we can easily generate tree structures with FsCheck.

Some examples of generative inputs:

👀 Note that in this exercise, the ‘too wide’ width and ‘too deep’ depth are hard-coded for simplicity: we can generate any number above the domain requirements, of course.

Conclusion

This post outlines key insights gained from creating and implementing a recursive domain model. By focusing on a structured approach rather than a flat list of parent-child relationships, extracting this structure into a specialized type can greatly aid in generating either a flat list of DTO-types or enabling the reuse of functionality for traversing your domain model.

FsCheck and F# are inherently equipped to manage recursion, making them excellent options for designing recursive types. Leveraging dedicated generative inputs allows for thorough property-based testing, enabling us to explore the boundaries of the type and even construct various custom structures as needed.

Thanks for reading.
Stijn

Subscribe to our RSS feed

Thanks, we've sent the link to your inbox

Invalid email address

Submit

Your download should start shortly!

Stay in Touch - Subscribe to Our Newsletter

Keep up to date with industry trends, events and the latest customer stories

Invalid email address

Submit

Great you’re on the list!