recursion - 使用差异列表快速序列化 BST

Question

背景

我正在处理Ullmans Elements of ML programming在我空闲的时间里。最终目标是自学Andrew Appels Modern Compiler Implementation in ML .

在《Elements of ML》中，Ullman 描述了差异列表:

There is a trick known to LISP programmers as difference lists, in which one manipulates lists more efficiently by keeping, as an extra parameter of your function, a list that represents in some way what you have already accomplished. The idea comes up in a number of different applications;

Ullman 使用reverse 作为差异列表技术的示例。这是一个运行时间复杂度为 O(n^2) 的慢速函数。

fun reverse nil = nil
  | reverse (x::xs) = reverse(xs) @ [x]

使用差异列表的速度更快

fun rev1(nil, M) = M
  | rev1(x::xs, ys) = rev1(xs, x::ys)

fun reverse L = rev1(L, nil)

---

我的问题

我有这个二叉搜索树 (BST) 数据类型。

datatype 'a btree = Empty
      | Node of 'a * 'a btree * 'a btree

收集预购元素列表的简单解决方案是

fun preOrder Empty = nil
  | preOrder (Node(x, left, right)) = [x] @ preOrder left @ preOrder right

但是 Ullman 指出 @ 运算符很慢，并建议我在练习 6.3.5 中使用差异列表实现 preOrder。

经过一番绞尽脑汁，我想出了这个函数:

fun preOrder tree = let
    fun pre (Empty, L)  = L
      | pre (Node(x, left, right), L) = let
          val L = pre(right, L)
          val L = pre(left, L)
        in
            x::L
        end
    in
       pre (tree, nil)
end

它按预定顺序输出元素。 但是它以后序方式评估树!而且代码比天真的 preOrder 代码更丑陋。

> val t = Node(5, 
    Node(3, 
       Node(1, Empty, Empty), 
       Node(4, Empty, Empty)), 
    Node(9, Empty, Empty))
> preOrder t
val it = [5,3,1,4,9] : int list

---

现有技术

我尝试在 ML 编程中搜索差异列表的引用，并发现 John Hughes original article描述如何使用差异列表进行反向。

我还发现了Matthew Brecknells difference list blog post并附有 Haskell 中的示例。他区分了使用累加器(如乌尔曼的逆向示例)和为差异列表创建新类型。他还展示了一个树木压平机。但我很难理解 Haskell 代码，并且希望在标准 ML 中进行类似的公开。 ABC

---

问题

• 如何实现一个函数来实际按前序求值树并按前序收集元素？遍历后是否必须反转列表？还是有其他的技巧？

• 如何推广此技术以适用于中序和后序遍历？

• 在 BST 算法中使用差异列表的惯用方法是什么？

Answer 1

您最终执行此操作的方法是合理的最佳方法。事实证明，做到这一点的好方法是

fun preOrderHelper (Empty, lst) = lst
  | preOrderHelper (Node(x, left, right), lst) = 
        x :: preOrderHelper(left, preOrderHelper(right, lst))

fun preOrder tree = preOrderHelper(tree, Nil)

注意 preOrderHelper(tree, list) 的运行时间只是 tree 的函数。调用r(t) preOrderHelper的运行时间在树上t 。然后我们有r(Empty) = O(1)和r(Node(x, left, right)) = O(1) + r(left) + r(right) ，如此清楚r(t)与 t 的大小呈线性关系.

这个技术的起源是什么？有没有更原则性的推导方法？一般来说，当您将数据结构转换为列表时，您需要foldr到一个空列表上。我不知道足够的 ML 来说明类型类的等价物是什么，但在 Haskell 中，我们将按如下方式处理这种情况:

data Tree a = Empty | Node a (Tree a) (Tree a)

instance Foldable Tree where
   foldr f acc t = foldrF t acc  where
      foldrF Empty acc = acc
      foldrF (Node x left right) acc = f x (foldrF left (foldrF right acc))

转换 Tree a到 [a] ，我们会调用 Data.Foldable.toList ，定义于 Data.Foldable作为

toList :: Foldable f => f a -> [a]
toList = foldr (:) []

展开这个定义给我们提供了与上面的 ML 定义等效的内容。

正如您所看到的，您的技术实际上是将数据结构转换为列表的一种非常有原则的方法的特例。

事实上，在现代 Haskell 中，我们可以完全自动地完成此操作。

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Empty | Node a (Tree a) (Tree a) deriving Foldable

将为我们提供与上述 Foldable 等效的^(*)自动执行，然后我们可以立即使用toList 。我不知道 ML 中的等价物是什么，但我确信有类似的东西。

ML 和 Haskell 之间的区别在于 Haskell 是惰性的。 Haskell 的惰性意味着 preOrder 的求值实际上是按照预购顺序遍历树的。这也是我比较喜欢懒惰的原因之一。惰性允许对求值顺序进行非常细粒度的控制，而无需诉诸非功能性技术。

---

^(*) (取决于参数顺序，这在惰性 Haskell 中不算在内。)