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

Question

我经常被告知使用 Lazy OCaml 中的模块，你可以用 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

如果您以从右到左的顺序构建链表(与普通列表一样)，则每个节点的左元素只会在该节点本身构建后构建。您需要通过使左元素变得惰性来表示这一点，这意味着“稍后将构造此值”:

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