layout: post
title: “Generic recursive types”
description: “Implementing a domain in three ways”
seriesId: “Recursive types and folds”
seriesOrder: 5

categories: [Folds, Patterns]

This post is the fifth in a series.

In the previous post, we spent some time understanding folds for specific domain types.

In this post, we’ll broaden our horizons and look at how to use generic recursive types.

Series contents

Here’s the contents of this series:


LinkedList: A generic recursive type

Here’s a question: if you only have algebraic types, and you can only combine them as products (tuples, records)
or sums (discriminated unions), then how can you make a list type just by using these operations?

The answer is, of course, recursion!

Let’s start with the most basic recursive type: the list.

I’m going to call my version LinkedList, but it is basically the same as the list type in F#.

So, how do you define a list in a recursive way?

Well, it’s either empty, or it consists of an element plus another list.
In other words we can define it as a choice type (“discriminated union”) like this:

  1. type LinkedList<'a> =
  2. | Empty
  3. | Cons of head:'a * tail:LinkedList<'a>

The Empty case represents an empty list. The Cons case has a tuple: the head element, and the tail, which is another list.

We can then define a particular LinkedList value like this:

  1. let linkedList = Cons (1, Cons (2, Cons(3, Empty)))

Using the native F# list type, the equivalent definition would be:

  1. let linkedList = 1 :: 2 :: 3 :: []

which is just [1; 2; 3]

cata for LinkedList

Following the rules in the first post in this series,
we can mechanically create a cata function by replacing Empty and Cons with fEmpty and fCons:

  1. module LinkedList =
  2. let rec cata fCons fEmpty list :'r=
  3. let recurse = cata fCons fEmpty
  4. match list with
  5. | Empty ->
  6. fEmpty
  7. | Cons (element,list) ->
  8. fCons element (recurse list)

Note: We will be putting all the functions associated with LinkedList<'a> in a module called LinkedList. One nice thing about using generic types is that the type name does not clash with a similar module name!

As always, the signatures of the case handling functions are parallel to the signatures of the type constructors, with LinkedList replaced by 'r.

  1. val cata :
  2. fCons:('a -> 'r -> 'r) ->
  3. fEmpty:'r ->
  4. list:LinkedList<'a>
  5. -> 'r

fold for LinkedList

We can also create a top-down iterative fold function using the rules in the earlier post.

  1. module LinkedList =
  2. let rec cata ...
  3. let rec foldWithEmpty fCons fEmpty acc list :'r=
  4. let recurse = foldWithEmpty fCons fEmpty
  5. match list with
  6. | Empty ->
  7. fEmpty acc
  8. | Cons (element,list) ->
  9. let newAcc = fCons acc element
  10. recurse newAcc list

This foldWithEmpty function is not quite the same as the standard List.fold function, because it has an extra function parameter for the empty case (fEmpty).
However, if we eliminate that parameter and just return the accumulator we get this variant:

  1. module LinkedList =
  2. let rec fold fCons acc list :'r=
  3. let recurse = fold fCons
  4. match list with
  5. | Empty ->
  6. acc
  7. | Cons (element,list) ->
  8. let newAcc = fCons acc element
  9. recurse newAcc list

If we compare the signature with the List.fold documentation we can see that they are equivalent,
with 'State replaced by 'r and 'T list replaced by LinkedList<'a>:

  1. LinkedList.fold : ('r -> 'a -> 'r ) -> 'r -> LinkedList<'a> -> 'r
  2. List.fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State

Let’s test that fold works by doing a small sum:

  1. let linkedList = Cons (1, Cons (2, Cons(3, Empty)))
  2. linkedList |> LinkedList.fold (+) 0
  3. // Result => 6

foldBack for LinkedList

Finally we can create a foldBack function, using the “function accumulator” approach described in the previous post:

  1. module LinkedList =
  2. let rec cata ...
  3. let rec fold ...
  4. let foldBack fCons list acc :'r=
  5. let fEmpty' generator =
  6. generator acc
  7. let fCons' generator element=
  8. fun innerResult ->
  9. let newResult = fCons element innerResult
  10. generator newResult
  11. let initialGenerator = id
  12. foldWithEmpty fCons' fEmpty' initialGenerator list

Again, if we compare the signature with the List.foldBack documentation, they are also equivalent,
with 'State replaced by 'r and 'T list replaced by LinkedList<'a>:

  1. LinkedList.foldBack : ('a -> 'r -> 'r ) -> LinkedList<'a> -> 'r -> 'r
  2. List.foldBack : ('T -> 'State -> 'State) -> 'T list -> 'State -> 'State

Using foldBack to convert between list types

In the first post we noted that catamorphisms could be used for converting between types of similar structure.

Let’s demonstrate that now by creating some functions that convert from LinkedList to the native list type and back again.

To convert a LinkedList to a native list all we need to do is replace Cons with :: and Empty with []:

  1. module LinkedList =
  2. let toList linkedList =
  3. let fCons head tail = head::tail
  4. let initialState = []
  5. foldBack fCons linkedList initialState

To convert the other way, we need to replace :: with Cons and [] with Empty:

  1. module LinkedList =
  2. let ofList list =
  3. let fCons head tail = Cons(head,tail)
  4. let initialState = Empty
  5. List.foldBack fCons list initialState

Simple! Let’s test toList:

  1. let linkedList = Cons (1, Cons (2, Cons(3, Empty)))
  2. linkedList |> LinkedList.toList
  3. // Result => [1; 2; 3]

and ofList:

  1. let list = [1;2;3]
  2. list |> LinkedList.ofList
  3. // Result => Cons (1,Cons (2,Cons (3,Empty)))

Both work as expected.

Using foldBack to implement other functions

I said earlier that a catamorphism function (for linear lists, foldBack) is the most basic function available for a recursive type, and in fact is the only function you need!

Let’s see for ourselves by implementing some other common functions using foldBack.

Here’s map defined in terms of foldBack:

  1. module LinkedList =
  2. /// map a function "f" over all elements
  3. let map f list =
  4. // helper function
  5. let folder head tail =
  6. Cons(f head,tail)
  7. foldBack folder list Empty

And here’s a test:

  1. let linkedList = Cons (1, Cons (2, Cons(3, Empty)))
  2. linkedList |> LinkedList.map (fun i -> i+10)
  3. // Result => Cons (11,Cons (12,Cons (13,Empty)))

Here’s filter defined in terms of foldBack:

  1. module LinkedList =
  2. /// return a new list of elements for which "pred" is true
  3. let filter pred list =
  4. // helper function
  5. let folder head tail =
  6. if pred head then
  7. Cons(head,tail)
  8. else
  9. tail
  10. foldBack folder list Empty

And here’s a test:

  1. let isOdd n = (n%2=1)
  2. let linkedList = Cons (1, Cons (2, Cons(3, Empty)))
  3. linkedList |> LinkedList.filter isOdd
  4. // Result => Cons (1,Cons (3,Empty))

Finally, here’s rev defined in terms of fold:

  1. /// reverse the elements of the list
  2. let rev list =
  3. // helper function
  4. let folder tail head =
  5. Cons(head,tail)
  6. fold folder Empty list

And here’s a test:

  1. let linkedList = Cons (1, Cons (2, Cons(3, Empty)))
  2. linkedList |> LinkedList.rev
  3. // Result => Cons (3,Cons (2,Cons (1,Empty)))

So, I hope you’re convinced!

Avoiding generator functions

I mentioned earlier that there was an alternative and (sometimes) more efficient way to implement foldBack without using generators or continuations.

As we have seen, foldBack is reverse iteration, which means that it is the same as fold applied to a reversed list!

So we could implement it like this:

  1. let foldBack_ViaRev fCons list acc :'r=
  2. let fCons' acc element =
  3. // just swap the params!
  4. fCons element acc
  5. list
  6. |> rev
  7. |> fold fCons' acc

It involves making an extra copy of the list, but on the other hand there is no longer a large set of pending continuations. It might
be worth comparing the profile of the two versions in your environment if performance is an issue.

Making the Gift domain generic

In the rest of this post, we’ll look at the Gift type and see if we can make it more generic.

As a reminder, here is the original design:

  1. type Gift =
  2. | Book of Book
  3. | Chocolate of Chocolate
  4. | Wrapped of Gift * WrappingPaperStyle
  5. | Boxed of Gift
  6. | WithACard of Gift * message:string

Three of the cases are recursive and two are non-recursive.

Now, the focus of this particular design was on modelling the domain, which is why there are so many separate cases.

But if we want to focus on reusability instead of domain modelling, then we should simplify the design to the essentials, and all these special cases now become a hindrance.

To make this ready for reuse, then, let’s collapse all the non-recursive cases into one case, say GiftContents,
and all the recursive cases into another case, say GiftDecoration, like this:

  1. // unified data for non-recursive cases
  2. type GiftContents =
  3. | Book of Book
  4. | Chocolate of Chocolate
  5. // unified data for recursive cases
  6. type GiftDecoration =
  7. | Wrapped of WrappingPaperStyle
  8. | Boxed
  9. | WithACard of string
  10. type Gift =
  11. // non-recursive case
  12. | Contents of GiftContents
  13. // recursive case
  14. | Decoration of Gift * GiftDecoration

The main Gift type has only two cases now: the non-recursive one and the recursive one.

Defining a generic Container type

Now that the type is simplified, we can “genericize” it by allowing any kind of contents and any kind of decoration.

  1. type Container<'ContentData,'DecorationData> =
  2. | Contents of 'ContentData
  3. | Decoration of 'DecorationData * Container<'ContentData,'DecorationData>

And as before, we can mechanically create a cata and fold and foldBack for it, using the standard process:

  1. module Container =
  2. let rec cata fContents fDecoration (container:Container<'ContentData,'DecorationData>) :'r =
  3. let recurse = cata fContents fDecoration
  4. match container with
  5. | Contents contentData ->
  6. fContents contentData
  7. | Decoration (decorationData,subContainer) ->
  8. fDecoration decorationData (recurse subContainer)
  9. (*
  10. val cata :
  11. // function parameters
  12. fContents:('ContentData -> 'r) ->
  13. fDecoration:('DecorationData -> 'r -> 'r) ->
  14. // input
  15. container:Container<'ContentData,'DecorationData> ->
  16. // return value
  17. 'r
  18. *)
  19. let rec fold fContents fDecoration acc (container:Container<'ContentData,'DecorationData>) :'r =
  20. let recurse = fold fContents fDecoration
  21. match container with
  22. | Contents contentData ->
  23. fContents acc contentData
  24. | Decoration (decorationData,subContainer) ->
  25. let newAcc = fDecoration acc decorationData
  26. recurse newAcc subContainer
  27. (*
  28. val fold :
  29. // function parameters
  30. fContents:('a -> 'ContentData -> 'r) ->
  31. fDecoration:('a -> 'DecorationData -> 'a) ->
  32. // accumulator
  33. acc:'a ->
  34. // input
  35. container:Container<'ContentData,'DecorationData> ->
  36. // return value
  37. 'r
  38. *)
  39. let foldBack fContents fDecoration (container:Container<'ContentData,'DecorationData>) :'r =
  40. let fContents' generator contentData =
  41. generator (fContents contentData)
  42. let fDecoration' generator decorationData =
  43. let newGenerator innerValue =
  44. let newInnerValue = fDecoration decorationData innerValue
  45. generator newInnerValue
  46. newGenerator
  47. fold fContents' fDecoration' id container
  48. (*
  49. val foldBack :
  50. // function parameters
  51. fContents:('ContentData -> 'r) ->
  52. fDecoration:('DecorationData -> 'r -> 'r) ->
  53. // input
  54. container:Container<'ContentData,'DecorationData> ->
  55. // return value
  56. 'r
  57. *)

Converting the gift domain to use the Container type

Let’s convert the gift type to this generic Container type:

  1. type Gift = Container<GiftContents,GiftDecoration>

Now we need some helper methods to construct values while hiding the “real” cases of the generic type:

  1. let fromBook book =
  2. Contents (Book book)
  3. let fromChoc choc =
  4. Contents (Chocolate choc)
  5. let wrapInPaper paperStyle innerGift =
  6. let container = Wrapped paperStyle
  7. Decoration (container, innerGift)
  8. let putInBox innerGift =
  9. let container = Boxed
  10. Decoration (container, innerGift)
  11. let withCard message innerGift =
  12. let container = WithACard message
  13. Decoration (container, innerGift)

Finally we can create some test values:

  1. let wolfHall = {title="Wolf Hall"; price=20m}
  2. let yummyChoc = {chocType=SeventyPercent; price=5m}
  3. let birthdayPresent =
  4. wolfHall
  5. |> fromBook
  6. |> wrapInPaper HappyBirthday
  7. |> withCard "Happy Birthday"
  8. let christmasPresent =
  9. yummyChoc
  10. |> fromChoc
  11. |> putInBox
  12. |> wrapInPaper HappyHolidays

The totalCost function using the Container type

The “total cost” function can be written using fold, since it doesn’t need any inner data.

Unlike the earlier implementations, we only have two function parameters, fContents and fDecoration, so each of these
will need some pattern matching to get at the “real” data.

Here’s the code:

  1. let totalCost gift =
  2. let fContents costSoFar contentData =
  3. match contentData with
  4. | Book book ->
  5. costSoFar + book.price
  6. | Chocolate choc ->
  7. costSoFar + choc.price
  8. let fDecoration costSoFar decorationInfo =
  9. match decorationInfo with
  10. | Wrapped style ->
  11. costSoFar + 0.5m
  12. | Boxed ->
  13. costSoFar + 1.0m
  14. | WithACard message ->
  15. costSoFar + 2.0m
  16. // initial accumulator
  17. let initialAcc = 0m
  18. // call the fold
  19. Container.fold fContents fDecoration initialAcc gift

And the code works as expected:

  1. birthdayPresent |> totalCost
  2. // 22.5m
  3. christmasPresent |> totalCost
  4. // 6.5m

The description function using the Container type

The “description” function needs to be written using foldBack, since it does need the inner data. As with the code above,
we need some pattern matching to get at the “real” data for each case.

  1. let description gift =
  2. let fContents contentData =
  3. match contentData with
  4. | Book book ->
  5. sprintf "'%s'" book.title
  6. | Chocolate choc ->
  7. sprintf "%A chocolate" choc.chocType
  8. let fDecoration decorationInfo innerText =
  9. match decorationInfo with
  10. | Wrapped style ->
  11. sprintf "%s wrapped in %A paper" innerText style
  12. | Boxed ->
  13. sprintf "%s in a box" innerText
  14. | WithACard message ->
  15. sprintf "%s with a card saying '%s'" innerText message
  16. // main call
  17. Container.foldBack fContents fDecoration gift

And again the code works as we want:

  1. birthdayPresent |> description
  2. // CORRECT "'Wolf Hall' wrapped in HappyBirthday paper with a card saying 'Happy Birthday'"
  3. christmasPresent |> description
  4. // CORRECT "SeventyPercent chocolate in a box wrapped in HappyHolidays paper"

A third way to implement the gift domain

That all looks quite nice, doesn’t it?

But I have to confess that I have been holding something back.

None of that code above was strictly necessary, because it turns out that there is yet another way to model a Gift,
without creating any new generic types at all!

The Gift type is basically a linear sequence of decorations, with some content as the final step. We can just model this as a pair — a Content and a list of Decoration.
Or to make it a little friendlier, a record with two fields: one for the content and one for the decorations.

  1. type Gift = {contents: GiftContents; decorations: GiftDecoration list}

That’s it! No other new types needed!

Building values using the record type

As before, let’s create some helpers to construct values using this type:

  1. let fromBook book =
  2. { contents = (Book book); decorations = [] }
  3. let fromChoc choc =
  4. { contents = (Chocolate choc); decorations = [] }
  5. let wrapInPaper paperStyle innerGift =
  6. let decoration = Wrapped paperStyle
  7. { innerGift with decorations = decoration::innerGift.decorations }
  8. let putInBox innerGift =
  9. let decoration = Boxed
  10. { innerGift with decorations = decoration::innerGift.decorations }
  11. let withCard message innerGift =
  12. let decoration = WithACard message
  13. { innerGift with decorations = decoration::innerGift.decorations }

With these helper functions, the way the values are constructed is identical to the previous version. This is why it is good to hide your raw constructors, folks!

  1. let wolfHall = {title="Wolf Hall"; price=20m}
  2. let yummyChoc = {chocType=SeventyPercent; price=5m}
  3. let birthdayPresent =
  4. wolfHall
  5. |> fromBook
  6. |> wrapInPaper HappyBirthday
  7. |> withCard "Happy Birthday"
  8. let christmasPresent =
  9. yummyChoc
  10. |> fromChoc
  11. |> putInBox
  12. |> wrapInPaper HappyHolidays

The totalCost function using the record type

The totalCost function is even easier to write now.

  1. let totalCost gift =
  2. let contentCost =
  3. match gift.contents with
  4. | Book book ->
  5. book.price
  6. | Chocolate choc ->
  7. choc.price
  8. let decorationFolder costSoFar decorationInfo =
  9. match decorationInfo with
  10. | Wrapped style ->
  11. costSoFar + 0.5m
  12. | Boxed ->
  13. costSoFar + 1.0m
  14. | WithACard message ->
  15. costSoFar + 2.0m
  16. let decorationCost =
  17. gift.decorations |> List.fold decorationFolder 0m
  18. // total cost
  19. contentCost + decorationCost

The description function using the record type

Similarly, the description function is also easy to write.

  1. let description gift =
  2. let contentDescription =
  3. match gift.contents with
  4. | Book book ->
  5. sprintf "'%s'" book.title
  6. | Chocolate choc ->
  7. sprintf "%A chocolate" choc.chocType
  8. let decorationFolder decorationInfo innerText =
  9. match decorationInfo with
  10. | Wrapped style ->
  11. sprintf "%s wrapped in %A paper" innerText style
  12. | Boxed ->
  13. sprintf "%s in a box" innerText
  14. | WithACard message ->
  15. sprintf "%s with a card saying '%s'" innerText message
  16. List.foldBack decorationFolder gift.decorations contentDescription

Abstract or concrete? Comparing the three designs

If you are confused by this plethora of designs, I don’t blame you!

But as it happens, the three different definitions are actually interchangable:

The original version

  1. type Gift =
  2. | Book of Book
  3. | Chocolate of Chocolate
  4. | Wrapped of Gift * WrappingPaperStyle
  5. | Boxed of Gift
  6. | WithACard of Gift * message:string

The generic container version

  1. type Container<'ContentData,'DecorationData> =
  2. | Contents of 'ContentData
  3. | Decoration of 'DecorationData * Container<'ContentData,'DecorationData>
  4. type GiftContents =
  5. | Book of Book
  6. | Chocolate of Chocolate
  7. type GiftDecoration =
  8. | Wrapped of WrappingPaperStyle
  9. | Boxed
  10. | WithACard of string
  11. type Gift = Container<GiftContents,GiftDecoration>

The record version

  1. type GiftContents =
  2. | Book of Book
  3. | Chocolate of Chocolate
  4. type GiftDecoration =
  5. | Wrapped of WrappingPaperStyle
  6. | Boxed
  7. | WithACard of string
  8. type Gift = {contents: GiftContents; decorations: GiftDecoration list}

If this is not obvious, it might be helpful to read my post on data type sizes. It explains how two types can be “equivalent”,
even though they appear to be completely different at first glance.

Picking a design

So which design is best? The answer is, as always, “it depends”.

For modelling and documenting a domain, I like the first design with the five explicit cases.
Being easy for other people to understand is more important to me than introducing abstraction for the sake of reusability.

If I wanted a reusable model that was applicable in many situations, I’d probably choose the second (“Container”) design. It seems to me that this type
does represent a commonly encountered situation, where the contents are one kind of thing and the wrappers are another kind of thing.
This abstraction is therefore likely to get some use.

The final “pair” model is fine, but by separating the two components, we’ve over-abstracted the design for this scenario. In other situations, this
design might be a great fit (e.g. the decorator pattern), but not here, in my opinion.

There is one further choice which gives you the best of all worlds.

As I noted above, all the designs are logically equivalent, which means there are “lossless” mappings between them.
In that case, your “public” design can be the domain-oriented one, like the first one, but behind the scenes you can map it to a more efficient and reusable “private” type.

Even the F# list implementation itself does this.
For example, some of the functions in the List module, such foldBack and sort, convert the list into an array, do the operations, and then convert it back to a list again.


Summary

In this post we looked at some ways of modelling the Gift as a generic type, and the pros and cons of each approach.

In the next post we’ll look at real-world examples of using a generic recursive type.

The source code for this post is available at this gist.