从OCaml中的列表创建双向链表

Question

我经常被告知使用LazyOCaml中的模块,可以用惰性语言(如Haskell)完成所有操作.为了测试这个说法,我正在尝试编写一个函数,将常规列表转换为ocaml中的静态双向链表.

type 'a dlist = Dnil | Dnode of 'a dlist * 'a * 'a dlist

鉴于此类型,我可以手动创建几个静态双向链表:

let rec l1 = Dnode (Dnil,1,l2)
    and l2 = Dnode   (l1,2,l3)
    and l3 = Dnode   (l2,3,Dnil)

但我想写一个类型的函数'a list -> 'a dlist,给定任何列表在OCaml中构建一个静态双向链表.例如,[1;2;3]它应该输出相当于l1上面的东西.

在Haskell中编写该算法非常简单:

data DList a = Dnil | Dnode (DList a) a (DList a)

toDList :: [a] -> DList a
toDList l = go Dnil l
 where
  go _ [] = Dnil
  go h (x:xs) = let r = Dnode h x (go r xs) in r

但我无法弄清楚lazy在OCaml 中进行调用的地方.

Answer 1

如果按从右到左的顺序构建链接列表(与普通列表一样),则每个节点的左侧元素仅在构建该节点后构建.你需要通过使左元素变为lazy来表示这一点,这意味着"此值将在以后构造":

type 'a dlist = 
  | Dnil
  | Dnode of 'a dlist Lazy.t * 'a * 'a dlist

一旦你有了这个,使用递归定义将每个节点构造为一个惰性值,该定义将惰性(仍然未构造的)节点传递给构建下一个节点的函数调用(以便它可以访问前一个节点).它实际上比看起来更简单:

let dlist_of_list list = 
  let rec aux prev = function
    | [] -> Dnil
    | h :: t -> let rec node = lazy (Dnode (prev, h, aux node t)) in 
                Lazy.force node
  in
  aux (Lazy.lazy_from_val Dnil) list

Answer 2

您只能构建一个在编译时确定的形状的循环不可变严格数据结构.我不打算正式定义或证明这一点,但直观地说,一旦创建了数据结构,它的形状就不会改变(因为它是不可变的).所以你不能添加一个循环.如果你创建循环的任何元素,你需要同时创建循环的所有其他元素,因为你不能有任何悬空指针.

Ocaml可以做Haskell可以做的事情,但你必须让Lazy模块参与其中!与Haskell不同,除非另有说明,否则ML的数据结构是严格的.惰性数据结构具有各种类型'a Lazy.t.(在这个特定问题上,ML的输入比Haskell更精确.)延迟数据结构允许通过使用临时悬挂指针(其链接值在首次取消引用指针时自动创建)来构建循环.

type 'a lazy_dlist_value =
  | Dnil
  | Dnode of 'a lazy_dlist_value * 'a * 'a lazy_dlist_value
 and 'a lazy_dlist = 'a lazy_dlist_value Lazy.t

具有循环数据结构的另一种常见方式是使用可变节点.(事实上​​,严格编程的顽固支持者可能会将惰性数据结构视为可变数据结构的一个特例,它不会过多地破坏参照透明度.)

type 'a mutable_dlist_value =
  | Dnil
  | Dnode of 'a mutable_dlist_value * 'a * 'a mutable_dlist_value
 and 'a mutable_dlist = 'a mutable_dlist_value ref

当循环数据结构涉及至少一个可变组件,一个函数(闭包)或有时模块时,它们最有用.但是编译器没有理由强制执行 - 循环严格不可变的一阶数据结构只是偶尔有用的特殊情况.