Как создать график с циклами без изменяемых данных?

Question

У меня есть следующий код:

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 

Как создать две ссылки, связанные друг с другом? Я пробовал:

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. И мой вопрос: Как создать граф с циклами (например: двусвязный список) без изменяемых данных с использованием (в OCaml или другом языке)?

Answer 1

Вы можете создать циклически связанную структуру в OCaml, используя 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 ... 

Однако, если у вас есть такая структура, очень сложно написать функции, которые могут обрабатывать ее полезными способами. Я не думаю, что вы можете сделать такое программирование в OCaml, нетерпеливом языке. На практике вам нужно использовать изменяемые поля для ваших ссылок.

У меня нет опыта в этом, но кажется, что такая обработка возможна в Haskell, языке, не вызывающем нетерпения.