Making cyclic graphs in F#. Is mutability required?

Question

I'm trying to do a cyclic graph in F#

My node type looks something like this:

type Node = { Value : int; Edges : Node list }

My question is: Do I need to make Edges mutable in order to have cycles?

Answer 1

F# makes it possible to create immediate recursive object references with cycles, but this really only works on (fairly simple) records. So, if you try this on your definition it won't work:

let rec loop = 
  { Value = 0;
    Edges = [loop] }

However, you can still avoid mutation - one reasonable alternative is to use lazy values:

type Node = { Value : int; Edges : Lazy<Node list>}

This way, you are giving the compiler "enough time" to create a loop value before it needs to evaluate the edges (and access the loop value again):

let rec loop = 
  { Value = 0;
    Edges = lazy [loop] }

In practice, you'll probably want to call some functions to create the edges, but that should work too. You should be able to write e.g. Edges = lazy (someFancyFunction loop).

Alternatively, you could also use seq<Edges> (as sequences are lazy by default), but that would re-evaluate the edges every time, so you probably don't want to do that.