all Technical posts

Unlocking the Power of Recursive Types and Navigating Complex Hierarchies with Ease

Read about mastering the art of design, testing, and storage for seamless integration.

The need for recursive types

Functional languages are by default designed to handle recursion with ease, as they are built into the construction of functional programs. Non-functional languages are a bit trickier to design, and developers working with those languages are hesitant to use them. However, as several use cases deal with types that are ‘foldable’ such as directories, decorations, hierarchies, and telemetry, there is a need for them. Everywhere there is a parent-child relationship, the need for recursive types is real. As a developer, it is important to identify these cases and not go for the ‘easy’ way out and design a more complex system.

It is also important that once you choose recursion, you go recursive all the way. Otherwise, the benefits of designing recursive types will go to waste and every time you want to use the type, your code will be much too complex.

Designing recursive types

Recursive types can be complex at first glance, and therefore it is important that the type itself is as simple as possible. Ensure that the data at the ‘current’ level is distinctly defined for any reader, along with a clear indication of the locations of children at ‘other levels’. An example:

Including the name in the recursive property could be an idea. Other options could be ‘children’ or ‘dependent’, but do not go for something like ‘folders’, for example. Make it clear to anyone that when navigating the type, the recursive property is clear from the get go.

Testing recursive types

The immediate testing of recursive types reveals certain constraints that the design should address. Maximum depth and width, for example. The property-based tests will need to make sure that we can generate several types of structures and edge cases: a childless folder, a binary-tree folder, a very deep folder, etc. It is important that these generative structures have clear names so that the tests are easily adaptable.

FsCheck has an example in their documentation that explains how recursive types can be generated.

An extra note on this is that testing also brings the problem of defect localization to mind. If each level has more than one data field, it could be troublesome to pinpoint the exact problem when handling generative trees. Therefore, it could be important to think about visualization. Normally, a simple function that takes the unique value of each item is enough to show complex trees. An example:

Storing recursive types

If your storage system doesn’t support hierarchical data structures, storing a specific type directly may not be feasible by default. But that may be a good thing because too many times the same DTO types are used for the wrong purposes. The domain can be represented as a strict type, but the actual storage entities are always different. Flattening your recursive type is key to doing this. An identifier needs to be included to link each child to a parent. Note that this identifier does not need to be present in the domain type, as the recursive type itself acts as this relationship. An example:

Conclusion

Every interaction with the type will necessitate a recursive approach: translating it into a flat structure, diagramming its relationships, and locating items within the hierarchy. This is the essence of integrating recursion into your project. While it may introduce additional complexity, avoiding it would require devising custom methods to interact with the type. Worse still, omitting recursion could lead to the proliferation of types and lists, complicating the handling of individual items.

Functional languages makes it easier to handle recursion, and so it is a logical choice to use them when designing your domain. By making your type ‘foldable’, you hide the complexity of the recursive functionality and focus on the project functionality. That’s it for now, but there’s more on this to come.

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!