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

Question

背景

我正在处理 Ullmans Elements of ML programming in my spare-time. End goal is to self-study 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

它按预定顺序输出元素。但是它以 post 顺序评估树！而且代码比天真的 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 描述了如何使用差异列表进行反向。

我还在 Haskell 中找到了带有示例的 Matthew Brecknells difference list blog post。他区分了使用累加器（如 Ullman 的反例）和为差异列表创建新类型。他还展示了一种树木压平器。但是我很难理解 Haskell 代码，并且希望在标准 ML 中有类似的公开。美国广播公司

问题

如何实现一个真正按预序评估树并按预序收集元素的函数？遍历后是否必须反转列表？还是有什么别的把戏？
我如何推广这种技术以用于中序和 post-顺序遍历？
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 的函数。在树t上调用r(t)preOrderHelper的运行次。然后我们有 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 的评估实际上是按照 pre-Order 顺序遍历树。这是我更喜欢懒惰的原因之一。懒惰允许对评估顺序进行非常细粒度的控制，而无需诉诸非功能性技术。

^(*)（直到参数顺序，不计入惰性Haskell。）

Answer 2

你展示的不是我看到的通常所说的差异列表。

那将是，在伪代码中，

-- xs is a prefix of an eventual list xs @ ys,
-- a difference between the eventual list and its suffix ys:
dl xs = (ys => xs @ ys)

然后

pre Empty = (ys => ys)  -- Empty contributes an empty prefix
pre (Node(x, left, right)) = (ys =>
    --  [x] @ pre left @ pre right @ ys  -- this pre returns lists
    (dl [x] . pre left . pre right)  ys) -- this pre returns diff-lists
                        -- Node contributes an [x], then goes 
                        -- prefix from `left`, then from `right`

所以

preOrder tree = pre tree []

其中.是函数组合运算符，

(f . g) = (x => f (g x))

当然因为dl [x] = (ys => [x] @ ys) = (ys => x::ys)这个是等同于你显示的，形式为

--pre Empty = (ys => ys)  -- Empty's resulting prefix is empty
pre'  Empty    ys =  ys  

--pre (Node(x, left, right)) = (ys =>
pre'  (Node(x, left, right))    ys = 
    --     [x] @ pre  left @ pre  right @ ys
    -- (dl [x] . pre  left . pre  right)  ys
            x::( pre' left ( pre' right   ys))

-- preOrder tree = pre' tree []

在操作上，这将在急切的语言中从右到左遍历树，在懒惰的语言中从左到右遍历树。

从概念上讲，从左到右看，结果列表有 [x]，然后是遍历的结果 left，然后是遍历的结果 right，不管是什么树的遍历顺序。

这些差异列表只是部分应用 @ 运算符，追加只是功能组合：

   dl (xs @ ys)     ==  (dl xs . dl ys)
 -- or:
   dl (xs @ ys) zs  ==  (dl xs . dl ys)  zs
                    ==   dl xs ( dl ys   zs)
                    ==      xs @   (ys @ zs)

前缀 xs @ ys 是前缀 xs，后跟前缀 ys，再后跟任何最终后缀 zs。

因此附加这些差异列表是一个 O(1) 操作，创建一个新的 lambda 函数，它是参数的组合：

append dl1 dl2 = (zs =>  dl1 ( dl2  zs))
               = (zs => (dl1 . dl2) zs )
               =        (dl1 . dl2)

现在我们可以很容易地看到如何编写中序或 post 序遍历，如

in_ Empty = (ys => ys)
in_  (Node(x, left, right)) = (ys =>
    --  in_ left @    [x] @ in_ right @ ys
       (in_ left . dl [x] . in_ right)  ys)

post Empty = (ys => ys)
post  (Node(x, left, right)) = (ys =>
    --  post left @ post right @    [x] @ ys
       (post left . post right . dl [x])  ys)

只关注列表 [x] 及其附加的 @ 让我们统一对待它——无需关心 :: 及其具有不同类型的参数。

@ 的两个参数的类型是相同的，就像 + 的整数和 . 的函数一样。与此类操作配对的此类类型称为 monoids，条件是附加操作是关联的，(a+b)+c == a+(b+c)，并且有一个“空”元素，e @ s == s @ e == s.这只是意味着组合操作在某种程度上是“结构性的”。这适用于苹果和橙子，但原子核——不是那么多。

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

Fast serialization of BST using a difference list

recursion

functional-programming

binary-search-tree

sml

difference-lists

背景

我的问题

现有技术

问题