Recursive map reference in F#

Question

I'm trying to create a recursive map in F#.

type RecMap = Map<string, RecMap>

will not work, because of the cyclic reference to RecMap. But why is it that neither

type RecMap = Map<string, RecMap ref>

nor

type RecMap = (Map<string, RecMap>) ref

works? I thought that making the value type of the map into a RecMap ref should have done the trick.

Circumventing the problem by rewriting RecMap into a one member record type works,

type RecMap = { r : Map<string, RecMap> }

Records are reference types just like ref, but why don't refs work in recursive definitions, when records do?

Answer 1

Your initial attempts are type abbreviations, while your last attempt defines a new type. During compilation, abbreviations are erased via substitution. Since you've got a cyclic definition (even if it passes through an additional level with the inclusion of ref), substitution would never terminate.

I'd probably do this instead:

type RecMap = RecMap of Map<string, RecMap>