Fast serialization of BST using a difference list

Question

Background

I'm working through Ullmans Elements of ML programming in my spare-time. End goal is to self-study Andrew Appels Modern Compiler Implementation in ML.

In Elements of ML, Ullman describes the difference list:

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 uses reverse as an example of the difference list technique. Here is a slow function that runs in O(n^2).

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

And the faster one using a difference list

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

fun reverse L = rev1(L, nil)

---

My problem

I have this Binary Search Tree (BST) data type.

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

A naive solution for collecting a list of the elements in pre-order would be

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

But Ullman points out that the @ operator is slow and suggests in exercise 6.3.5 that I implement preOrder using a difference list.

After some head scratching I came up with this function:

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

It outputs the elements in pre-order. BUT it evaluates the tree in post-order! And the code is uglier than the naive preOrder one.

> 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

---

Prior Art

I tried searching for references to difference lists in ML programming, and found John Hughes original article describing how to use difference lists for reverse.

I also found Matthew Brecknells difference list blog post with examples in Haskell. He makes a distinction between using an accumulator, like Ullmans reverse example and creating a new type for difference lists. He also presents a tree flattener. But I have a hard time understanding the Haskell code and would appreciate a similar expose but in Standard ML. abc

---

Question

• How implement a function that actually evaluate the tree in pre-order and collects the elements in pre-order? Do I have to reverse the list after my traversal? Or is there some other trick?

• How can I generalize this technique to work for in-order and post-order traversal?

• What is the idiomatic way for using a difference list for a BST algorithm?

Answer 1

Your eventual method of doing this is is the best it reasonably gets. The nice way to do this turns out to be

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

fun preOrder tree = preOrderHelper(tree, Nil)

Note that the run time of preOrderHelper(tree, list) is only a function of tree. Call r(t) the run time of preOrderHelper on tree t. Then we have r(Empty) = O(1) and r(Node(x, left, right)) = O(1) + r(left) + r(right), so clearly r(t) is linear in the size of t.

What is the derivation of this technique? Is there a more principled way of deriving it? In general, when you're turning a data structure into a list, you want to foldr onto an empty list. I don't know enough ML to say what the equivalent of typeclasses is, but in Haskell, we would approach the situation as follows:

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))

To convert a Tree a to a [a], we would call Data.Foldable.toList, which is defined in Data.Foldable as

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

Unfolding this definition gives us the equivalent of the ML definition above.

As you can see, your technique is actually a special case of a very principled way to turn data structures into lists.

In fact, in modern Haskell, we can do this totally automatically.

{-# LANGUAGE DeriveFoldable #-}

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

will give us the equivalent^(*) of the above Foldable implementation automatically, and we can then immediately use toList. I don't know what the equivalent is in ML, but I'm sure there's something analogous.

The difference between ML and Haskell is that Haskell is lazy. Haskell's laziness means that the evaluation of preOrder actually walks the tree in the pre-Order order. This is one of the reasons I prefer laziness. Laziness permits very fine-grained control over the order of evaluation without resorting to non-functional techniques.

---

^(*) (up to the arguments order, which does not count in the lazy Haskell.)

Answer 2

What you show is not what I've seen usually referred to as difference list.

That would be, in pseudocode,

-- 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)

and then

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`

so that

preOrder tree = pre tree []

where . is the functional composition operator,

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

Of course since dl [x] = (ys => [x] @ ys) = (ys => x::ys) this is equivalent to what you show, in the form of

--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 []

Operationally, this will traverse the tree right-to-left in an eager language, and left-to-right in a lazy one.

Conceptually, seen left-to-right, the resulting list has [x] and then the result of traversing left and then the result of traversing right, no matter what was the tree traversal order.

These difference lists are just partially applied @ operators, and appending is just functional composition:

   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)

the prefix xs @ ys is the prefix xs, followed by the prefix ys, followed by whatever the eventual suffix zs will be.

Thus appending these difference lists is an O(1) operation, the creation of a new lambda function which is a composition of the arguments:

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

Now we can easily see how to code the in-order or post-order traversals, as

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)

Focusing on just lists [x] and their appending @ lets us treat this uniformly -- no need to concern ourselves with :: and its arguments which have different types.

The types of both arguments of @ are the same, just as they are for + with integers and indeed . with functions. Such types paired with such operations are known as monoids, under the condition that the appending operation is associative, (a+b)+c == a+(b+c), and there is an "empty" element, e @ s == s @ e == s. This just means that the combination operation is "structural" in some way. This works with apples and oranges, but atomic nuclei -- not so much.