CODEWITHSUNDEEP
recursionf#
AymenDaoudi
AymenDaoudi

Reputation: 8299

F# : A recursive value that can reference itself

I have a record :

type node = {
               content : string;
               parent : node option;
               branch : string option;
               children : seq<node> option;
            }

Which I want to instantiate this way :

let rec treeHead = {
                       content = "Value"
                       parent = None;
                       branch = None;
                       children = tree (Some(treeHead)) rows;
                   };

Where 

let rec tree (parent:node option) (rows:seq<CsvRow>) :seq<node> option

Is a a recursive function that gets the children of a node (to construct a tree). So as you can see the object treeHead needs to call itself through the tree function.

I want to it this way to avoid using treeHead as a mutable value and change its children property after.

My question is that the treeHead is raising an error and a warning. The error says :

The value 'treeHead' will be evaluated as part of its own definition.

And the warning says :

This and other recursive references to the object(s) being defined will be checked for initialization-soundness at runtime through the use of a delayed reference. This is because you are defining one or more recursive objects, rather than recursive functions. This warning may be suppressed by using '#nowarn "40"' or '--nowarn:40'.

First, am I doing this the right way (I mean, not considering the mutable choice) ? And how should I correct this.

Upvotes: 4

Views: 1014

Answers (1)

Fyodor Soikin
Fyodor Soikin

Reputation: 80744

The thing with immutable data structures is, they're immutable. (<-- some Yoda-level stuff right there)

With a mutable data structure, you first create yourself a box, and then start putting things into the box. One of the things you put in may be a reference to the box itself. Since you already have a box, that's fine, you can take its reference.

With an immutable data structure, this doesn't work: you have to enumerate all things that go into the box before the box even exists! So the box itself can't be one of these things. That's what the compiler tells you in the error message: the value foo would be evaluated as part of its own definition. Can't do. Bad luck.

If only you could wrap the reference to the box in such a way as to not evaluate it right away, but defer the evaluation till later, till the box is fully constructed... I know! Put it in a closure!

let getMe42 x = 42

type R1 = { r1: int }
let rec x1 = { r1 = getMe42 x1 }  // Doesn't work: the definition of `x1` references `x1` itself

type R2 = { r2: unit -> int }
let rec x2 = { r2 = fun() -> getMe42 x2 } // This works: the definition of `x2` only creates a _closure_ around `x2`, but doesn't reference it right away

Ok, so if I can create a lambda, maybe I can cheat the compiler by passing the lambda to another function and calling it right away?

let getMe42 f = printfn "%O" <| f(); 42

type R = { r: int }
let rec x = { r = getMe42 (fun () -> x) }

> System.InvalidOperationException: ValueFactory attempted to access the Value property of this instance.

Damn! The Force is strong with this one. Even though the compiler can't prove that I'm being naughty during compilation, it cleverly wraps the initialization in Lazy<T>, so I get an error at runtime.

Interestingly enough, in the very limited case of just inserting a straight-up self-reference, without complex processing, it works:

type R = { r: R }
let rec x = { r = x }  // Works just fine, not even a warning.

You can even go all the way to the turtles:

type R = { r: R }
let rec x = { r = { r = { r = { r = x } } } }  // Still works!

This is a very special case, for whose existence I can see no sane rationale. It works, because F# compiles the backing field as internal, not private, which allows it to mutate the field after constructing the record. A corollary is, this will only work within the same assembly where the type is defined.

Recursive values are one of those Dark Magic features that require you to split your soul in two pieces to use. I believe the proper term is hackrux.

Don't do this. Just don't, ok? Come back to the light side, we have cookies too.

Upvotes: 6

Related Questions