2

我的任务是编写一个函数，该函数将给定的树存储在后缀顺序（后序）‘a btree -> ‘a option list类型的元素列表中。‘a option

内部节点将由 表示None，具有值的外部节点（叶子）x将由 表示Some x。

到目前为止，叶子很容易做，但是如何把它放在一个'a option list？

type 'a btree = L of 'a | N of 'a btree * 'a btree ;;

let rec store t =
    match t with
        | L x -> Some x
        | N (a,b) -> None ???   
;;

我知道的第二个匹配案例是不正确的，但是如何解决呢？

4

2 回答 2

3

如果有人对这种改进感兴趣，可以通过线程化一个额外的累加器参数，在性能方面比 Len 的解决方案做得更好。

这个想法是从一个store : 'a btree -> 'a option list接受树并产生一个列表的函数转移到一个函数，它将树store' : 'a btree -> 'a option list -> 'a option list的元素添加到作为参数传递的现有列表中。

let rec store' t acc = match t with
  | L x -> Some x :: acc
  | N (a, b) ->
    store' a (store' b (None :: acc))

使用此定义，元素仅在最终结果列表中添加一次，而不是首先用于构建临时store a列表，然后通过运算符将第二次附加到最终结果中(@)。

参数顺序很重要，因为写tbeforeacc给出了列表中最终元素顺序的直觉： 的元素t将在中已经存在的元素之前acc。这使得N案例可以很自然地阅读：很容易看出结果将首先具有 的元素a，然后是b，然后是None，然后是acc。

最后，您当然可以定义store为store'：

let store t = store' t []

习惯上将第一个定义包装在第二个定义中（如果您不想向用户公开这个“低级”功能），并给它与外部定义相同的名称（这不冲突因为它不是递归的，所以不进入内部范围）：

let store t =
  let rec store t acc = match t with
    | L x -> Some x :: acc
    | N (a, b) ->
      store a (store b (None :: acc))
  in store t []

当然，这个定义是否比 Len 的定义“更好”取决于你的评价标准是什么。Len 的解决方案更短，更易于阅读，并且更紧密地映射了原始问题。

（您可以通过使用惰性枚举而不是严格列表来获得两全其美，但那是另一回事了。）

于 2012-05-27T11:34:41.093 回答
3

如果您查看您的第一个案例，您会发现它也不存在；它正在返回'a option，但您希望该函数返回一个'a option list.

显然你会返回一个列表，所以首先修复它：

let rec store = function
  | L x -> [Some x]
  | N (a,b) -> [None] (* ??? *)

现在让我们解决第二种情况；我们想追None加到我们的输出，但在此之前，我们需要我们的子树的节点：

let rec store = function
  | L x -> [Some x]
  | N (a,b) -> (store a) @ (store b) @ [None]

@有类型

'a list -> 'a list -> 'a list

即它将列表连接在一起。我们想加入左子树的结果列表，然后是右子树，最后是这个内部节点的结果。

于 2012-05-27T10:57:51.600 回答