Re: cyclic value construction ("let rec")

[Markus Mottl <mottl@miss.wu-wien.ac.at>]

> It would be interesting to know whether people have other workarounds.
> Also, a generic graph module which would implement "map", "iter" etc. in a 
> cycle-safe way (like Marshal) would perhaps be interesting in the
> 'user-contributed stdlib extension'...

You will probably always have to rely on "unsafe" things for such
purposes.  My quick hack for problems like this looks as follows:

  type 'a node = { data : 'a; next : 'a node }

  let make_circle n : 'a node =
    let module Dummy = struct
      type 'a t = { data : 'a; mutable next : 'a t } end in
    let res = { Dummy.data = n; Dummy.next = Obj.magic 0 } in
    res.Dummy.next <- res;
    Obj.magic res

  let rec iter f node = f node.data; iter f node.next

  let _ = iter (fun x -> print_int x; print_newline ()) (make_circle 42)

Type "'a node" is immutable from the outside. However, exploiting the
undocumented (good reason for this ;-) type casting features of OCaml,
one can cheat and define an identical type within a local module -
which is mutable!

Initialisation, too, relies on "unsafe" features - we simply put a
reference to a dummy value into the slot until it can be filled with the
"right" value. The return value is cast back again to the "global type"
as indicated in the type restriction in the definition of "make_circle"
- this is important, because otherwise you can crash your program (it
would have "any" type).

As far as I know, this should be safe, because the GC doesn't care
about the static types of the values - it only looks at the value tags
at runtime. Of course, the above will only work as long as the memory
layout of the "local" type agrees with the one of the "global type".

Thus, you can confine the "unsafe" part to specific functions (e.g.
"make_circle"). The iteration function "iter" does not change anything
and can therefore work on the "global" type.

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl