OCaml，惰性列表到惰性树

Question

我有两种类型:

type 'a llist = 
      LNil 
    | LCons of 'a * (unit -> 'a llist);;

type 'a lBT = 
      LEmpty 
    | LNode of 'a * (unit -> 'a lBT) * (unit -> 'a lBT);;

我需要编写获取惰性列表并返回惰性 BST 的函数。 我目前有两个函数，第一个(add，它获取元素和树并返回包含该元素的树)似乎没问题，但是第二个函数(它迭代列表并创建一个新树，添加列表中的所有元素)我得到错误。对我来说，它看起来不错，但我可能只是不明白一些事情。我不知道是什么。

let rec add (elem, tree) = 
    match (elem, tree) with
      (None, _) -> LEmpty
        | (x, LEmpty) -> LNode (x, (function() -> add (None, LEmpty)), (function() -> add (None, LEmpty)))
        | (x, LNode (y, l, r)) when x < y -> LNode(y, (function () -> add (x, l())), r)
        | (x, LNode (y, l, r)) -> LNode(y, l, (function () -> add (x, r())));;

let toLBST listal = 
    let rec toLBST_rec listal tree =
        match listal with
          LNil -> tree
            | LCons(x, xs) -> toLBST_rec (xs()) add(x, tree)
    in toLBST_rec (listal, LEmpty);;

我得到:

Characters 141-145:
    | LCons(x, xs) -> toLBST_rec (xs()) add(x, tree)
                                               ^^^^
Error: This expression has type 'a option * 'a option lBT -> 'a option lBT
    but an expression was expected of type 'a option lBT

我不知道我应该做什么才能让它正常工作。我尝试了一些方法，但每次都会出现一些错误。

Answer 1

以下是您在代码中犯的各种错误:

  (None, _) -> LEmpty

这是错误的，elem 没有理由成为选项类型。在 LEmpty 情况下，只需使用 LEmpty 来定义返回的惰性树的子节点。

        | LCons(x, xs) -> toLBST_rec (xs()) add(x, tree)

您忘记了 add(x, tree) 两边的括号。

in toLBST_rec (listal, LEmpty);;

您定义了 toLBST_rec 来接受两个参数，现在您只传递了一个错误类型的参数(一对列表和树，而参数只需要一个列表)。您似乎对 OCaml 中多参数(柯里化(Currying))函数的语法感到困惑。您应该在函数声明和调用中避免使用 (.. , ..) ，而是定义 let rec add elem tree = 等。