如何使用循环引用声明不可变图？

Question

我想声明一个边缘代表连续状态的所有状态的图形.我认为我想要做的事情可能被称为"打结"(虽然不确定).它不像我预期的那样工作,我有几个问题.

首先,我想要一个具有字符串名称和连续状态列表的State类型.但是这个声明给编译器错误"......立即循环引用......":

type State = string * (State list)

这种方式有效:

type State(name:string, contigs: (State list)) = 
  let name = name
  let contigs = contigs

但这并不是要求成员命名的要求.一个元组很好.如何使这种简洁的语法有效？

其次,下面的代码试图声明应该是三个连续状态图(HI和AK是由单个节点组成的图,所有剩余状态构成最后一个图),然后是所有节点的列表.(为简洁起见,我实际上只在这里宣布了一些州):

let rec hi = State("hi", []) 
and mo = State("mo", [il ia]) 
and il = State("il", [mo]) 
and ia = State("ia", [mo])
and states = [hi,mo,il,ia]

这会产生各种错误,但包括"mo最终会被评估为它自己定义的一部分","表达式应该是'a - >'b类型,但这里有类型State".我认为'rec'和'和'关键字可以让它发挥作用.我可以定义这个自引用图吗？如果是这样,怎么样？

Answer 1

问题是您的数据结构和使用无效的列表元素分隔符(应该是分号).这有效:( 见编辑)

type State =
  | State of string * State list

let rec hi = State("hi", []) 
and mo = State("mo", [il; ia]) 
and il = State("il", [mo]) 
and ia = State("ia", [mo])
let states = [hi; mo; il; ia]

递归引用将实现为thunks(lazy).所以你可以通过更多的打字自己用mutable lazys 做同样的事情- 仅仅是因为 - 你所拥有的是惯用的.

编辑

Intellisense没有问题,但编译器说

递归值不能直接显示为递归绑定中"List`1"类型的构造.此功能已从F#语言中删除.请考虑使用记录.

你可以通过使用seq而不是来解决这个问题list.

type State =
  | State of string * State seq

let rec hi = State("hi", []) 
and mo = State("mo", seq { yield il; yield ia }) 
and il = State("il", seq { yield mo }) 
and ia = State("ia", seq { yield mo })
let states = [hi; mo; il; ia]

Answer 2

虽然丹尼尔所说的是正确的,但我会质疑它是"惯用语"的断言,因为在一般情况下,这并不能产生非常有用的数据结构来表示图形.具体来说,它只允许从它们添加新的顶点和边,但不允许在现有顶点之间添加或删除边.特别是,这基本上意味着您的图形必须在源代码中静态定义为常量,因此您无法轻松地从磁盘加载这样的图形.

图的惯用纯函数表示是用字典查找替换解引用.例如,将图表表示为有Map顶点Set的顶点到顶点的s:

> let g =
    Map["hi", set[]; "mo", set["il"; "ia"]; "il", set["mo"]; "ia", set["mo"]];;
val g : Map<string,Set<string>> =
  map
    [("hi", set []); ("ia", set ["mo"]); ("il", set ["mo"]);
     ("mo", set ["ia"; "il"])]

例如,您可以通过边缘查找可直接到达的顶点,mo如下所示:

> g.["mo"];;
val it : Set<string> = set ["ia"; "il"]

这比可变表示更容易调试,但它有明显的缺点:

1. 在一个纯粹的功能字典中查找Map比至少取消引用遍历图形的指针要慢200倍(根据这里的快速测试).

2. 垃圾收集器不再为您回收无法访问的子图.必要的解决方案是使用弱字典,但没有已知的纯函数弱字典.

因此,只有性能和泄漏不会成为问题,这才是可行的.当图表很小或是静态时,最常见的情况就是这种情况.