2

次のコードがあります：

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

相互にリンクされた 2 つのリンクを作成する方法は? 私は試した：

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'

しかし、それは自分の卵から孵化したニワトリのように見えます. そして私の質問は次のとおりです: (OCaml または他の言語で) 変更可能なデータを使用せずにサイクル (例: 二重リンク リスト) を含むグラフを作成する方法は?

4

1 に答える 1

2

を使用して、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でそのような処理を行うことはより可能であるようです.

于 2014-10-25T01:40:44.980 に答える