CODEWITHSUNDEEP
ocamlimmutabilitymutual-recursion
Valentyn Zakharenko
Valentyn Zakharenko

Reputation: 3088

How to create graph with cycles without mutable data using?

I have next code:

module MakeLink (Key : Map.OrderedType) = struct
   module Links = Map.Make (Key)

    type 'a t = 
      { links : 'a t Links.t;
        value : 'a
      }

    type key_t = Key.t

    let make value = 
      { links = Links.empty;
        value
      }

    let link linker ~to':linkable ~by:key = 
      { linker with links = 
        Links.add key linkable linker.links
      } 

   (* some functions for reading here *)
end

How to create two links linked to each other? I tried:

let join a ~with':b ~by:key = 
  let rec a' = link a ~to':b' ~by:key
      and b' = link b ~to':a' ~by:(Key.opposite key) in
  a'

But it's looking like a hen that hatched from their own egg. And my question is: How to create graph with cycles (for example: doubly-linked list) without mutable data using (in OCaml or other language)?

Upvotes: 2

Views: 215

Answers (1)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66793

You can create a cyclically linked structure in OCaml using let rec.

# type 'a g = { links: 'a g list; value: 'a };;
type 'a g = { links : 'a g list; value : 'a; }
# let rec a = { links = [b]; value = 5; }
      and b = { links = [a]; value = 6; };;
val a : int g =
  {links =
  ... many strange lines of output ...
val b : int g =
  {links =
  ... many more strange lines of output ...

However once you have such a structure, it's very difficult to write functions that can process it in useful ways. I don't think you can do this kind of programming in OCaml, an eager language. In practice you have to use mutable fields for your links.

I have no experience with this but it seems more possible to do such processing in Haskell, a non-eager language.

Upvotes: 2

Related Questions