Effectively functional: swapping tree leaves with streams

(Thanks to Roshan for posing the task)

Given two binary trees, and a depth-first-search traversal ordering of the leaf nodes, produce two new trees with the same structures as the originals, but with the leaf nodes swapped. If there are more leaf nodes in one tree than the other, the remaining leaf nodes are copied unchanged.

So (swap-leaves ‘(1 . (2 . 3)) ‘(a . ((b . c) . d)))
=> ‘((a . (b . c)) ‘(1 . ((2 . 3) . d))


Waiving the requirement that the program be completely functional, my original thought was I could probably just modify my tree walker to do this. This treewalk procedure takes a tree and produces a stream of leaf node values. Changing it so that it returns a pair of the value, and a setter procedure that can modify the value in place, is trivial: the recursive auxiliary procedure for treewalk is given the parent node, so it can use set-car! or set-cdr! (depending on which side of the parent node this leaf node is) to update the parent:

(define treewalk
  (lambda (t)
    (if (not (pair? t))
        (stream-cons
          `(t . (lambda (v)
                  (error "Cannot modify singleton")))
          empty-stream)
        (stream-append (treewalk^ (car t) #t t)
                       (treewalk^ (cdr t) #f t)))))

(define treewalk^
  (lambda (t left? parent)
    (if (not (pair? t))
        (stream-cons `(,t . ,(if left?
                               (lambda (v)
                                 (set-car! parent v))
                               (lambda (v)
                                 (set-cdr! parent v))))
                     empty-stream)
        (stream-append (treewalk^ (car t) #t t)
                       (treewalk^ (cdr t) #f t)))))

The swapping is then just a matter of calling the setter for node1 with the value of node2, and vice-versa; this generalizes to swapping between multiple trees as well.

(define treewalk
  (lambda (t)
    (if (not (pair? t))
        (stream-cons `(t . (lambda (v)
                             (error "Cannot modify singleton")))
                     empty-stream)
        (stream-append (treewalk^ (car t) #t t)
                       (treewalk^ (cdr t) #f t)))))

(define treewalk^
  (lambda (t left? parent)
    (if (not (pair? t))
        (stream-cons `(,t . ,(if left?
                               (lambda (v)
                                 (set-car! parent v))
                               (lambda (v)
                                 (set-cdr! parent v))))
                     empty-stream)
        (stream-append (treewalk^ (car t) #t t)
                       (treewalk^ (cdr t) #f t)))))

But this modifies existing trees in place, a big no-no in functional programming land (though imperative programmers live with this every day). Is there a way to do this in, if not a fully functional way, then in a way that the side-effects are confined? (I mentioned to Roshan that this is a dual of Haskell’s monads: it behaves functionally even though it is imperative; monads gave the illusion of imperative behaviour even though they are fully functional. He pointed out that internally the state monad is optimized into imperative calls as well, so the comparison is even more interesting)

Instead of modifying existing trees in place, we want to copy the trees. But copying, naively done, would involve traversing the trees again, and that would be inefficient. The copying should be done Lazily as needed, and with streams, that means doing it while you’re walking the tree and collecting the nodes!

In short, at every internal node,
– create a new node, which has as its children the children of the original node;
– update the clone of the parent, instead of the parent, so that its car or cdr points to this new node
– the setter procedures for each leaf nodes modify these cloned nodes instead of the originals

...
(let ([copy (cons (car t) (cdr t))])
  (if left?
    (set-car! copy-parent copy)
    (set-cdr! copy-parent copy))
  (stream-append (treewalk-copy^ (car t) #t copy)
                 (treewalk-copy^ (cdr t) #f copy))
...

The main treewalk procedure now has to return the cloned tree as well, since at each subsequent stage of the walk only the direct parent is known, not the entire tree.

...
(let ([copy (cons (car t) (cdr t))])
       (if left?
           (set-car! copy-parent copy)
           (set-cdr! copy-parent copy))
  (stream-append (treewalk-copy^ (car t) #t copy)
                 (treewalk-copy^ (cdr t) #f copy))
...

Code, including stream implementation, available here

2 responses to “Effectively functional: swapping tree leaves with streams

  1. Pingback: Bible Versus and Gardens » Effectively functional: swapping tree leaves with streams …