CODEWITHSUNDEEP
ocamlocamlbuild
KUN
KUN

Reputation: 537

How does the OCaml compiler deal with this code?

I read a project written in OCaml and can't figure out some source code here:

type 'a node = {mutable parent: 'a node; mutable rank: int; label: 'a}

let singleton x = 
     let rec n = {parent=n; rank=0; label=x} in
 n

This code is part of the disjoint set but I don't really understand the recurive function. I used to be a C++ programmer and can easily use a pointer to handle the parent thing.
When I run this code in the OCaml utop the result surprise me. It did generate many node.
Is this code cost much memory since it generate so many node?
How the compiler deal with this without overflow?

Upvotes: 1

Views: 93

Answers (1)

camlspotter
camlspotter

Reputation: 9040

It does NOT create many nodes but one.

Internally the value of the node is represented as a pointer, so n has a pointer which points to itself in its parent field. It is pretty like a way you create a looped data structure with pointers in C++. C++ always requires assignments to create loops but in OCaml some simple loops can be created by recursion.

In utop you see one value n is printed in many times. OCaml value printer prints values in expanded form even if there are loops inside them.

Upvotes: 3

Related Questions