How to express a relation in F#

Question

I am trying to model a domain as records and discriminated unions, i.e. immutable. I noticed, that I have a m:n relationship, say authors and books. And now I'm looking for a good way of expressing it, such that:

• ideally immutable
• changing a property on a book is easy, that is, if I want to create a copy, I don't have to iterate over all the authors
• access is straightforward; ideally somehow an author has a books list

So far, i didn't find any solution fulfilling all of the criteria. What I found was:

• Each author has a list of books (I don't really need the opposite direction). This allow for easy access and is immutable, however changing a property on a book entails changing every autor
• Hold an immutable list of ref cells of books and each author has an immutable list of ref cells. This makes changing a property easy and access is easy, however this is not actually immutable, since the ref cell is not immutable.
• Hold an immutable list of books and each author has an immutable list of IDs. This is immutable and makes changes to the books easy, however the access is more difficult because you need to do a lookup and you might have a non-existing ID.

Are there any solutions that fulfil all of the above, maybe something like an immutable ref cell? And if so, what do they look like.

Answer 1

As I mentioned in the comments, if you have an immutable list of authors and map over it, you do not actually end up copying all the authors. The authors who do not change will just be pointing to the same instance (so the overhead of immutable solution is not that big).

However, it is true that if you have multiple books with the same author, there is no aliasing and so the authors will all be separate values (and you will have to map over all books).

I think a reasonable representation in this case would be to keep the authors and books separate and link them via a key (such as author name - in the example below - or some other ID):

type Author = { Name : string; Address : string }
type Book = { Title : string; Author : string }

// For efficient lookup, create a hashtable with authors 
let authors = dict [ "Tomas", { Name = "Tomas"; Address = "Cambridge" } ]
// Books are stored simply as a list
let books = [ { Title = "Real World FP"; Author = "Tomas" } ]

// To get nice access, add AuthorDetails property to the Author record
type Book with 
  member x.AuthorDetails = authors.[x.Author]

for book in books do 
  printfn "%s (%s, %s)" book.Title book.Author book.AuthorDetails.Address

This does not let you mutate the collection authors. If you were writing this in a purely functional way, you would probably have some recursive function that keeps current authors as argument and so you would not need mutation (just build a new dictionary).

But I think it is reasonable to have a ref value holding the dictionary, or even keep a mutable dictionary (but I would do that only if you do not have concurrency; in fact, in presence of concurrency, Map might be safer choice).