Lambda the Ultimate

On this binary choice between purity and impurity is too harsh - I quite agree, and it seems that much harsher when you generalise the first puzzle to allow cyclic trees. Core Haskell just doesn't seem well suited for this kind of thing, maybe a point in favour of Peter van Roy's argument for ramified language design.

The first is sort of a technical objection to the statement of the problem; Haskell doesn't have a defined space semantics and it thus becomes hard to discuss sharing except as an implementation issue. For the problem to be well-stated, you'd have to pose it in a language where the semantics defines what is shared and what is not.

Putting that aside, the second thought is that this problem can be solved without too much difficulty because the leaves are all interchangable. First you generate an "infinite" trie where each lookup slot in the trie is the cannonical representation of the tree of that shape, and the trie is constructed to preserve sharing, much like the memoization tricks one can do in Haskell. Cloning a tree involves looking up the appropriate node in the trie.

Something line this, perhaps? I think this creates maximal sharing (under a "reasonable" model of sharing), but I haven't looked into the bonus points.

data Tree = Leaf | Node Tree Tree deriving Show

data FullTrie a = T a (FullTrie (FullTrie a))

lookupTrie :: Tree -> FullTrie a -> a
lookupTrie Leaf       (T l n) = l
lookupTrie (Node a b) (T l n) = lookupTrie b . lookupTrie a $ n

cannonTrie :: FullTrie Tree
cannonTrie = mkCannonTrie id
 where
  leaf = Leaf

  mkCannonTrie :: (Tree -> a) -> FullTrie a
  mkCannonTrie f =
      T (f leaf)
        (mkCannonTrie (\l ->
           mkCannonTrie (\r ->
             f (Node (lookupTrie l cannonTrie)
                     (lookupTrie r cannonTrie)))))

cloneTree :: Tree -> Tree
cloneTree t = lookupTrie t cannonTrie

The "preserving existing sharing" requirement dips below the language level. It's like saying "do such and such in a C program which keeps all values in registers." You could do it, sure, but you have to know what's going on behind the scenes. Imagine a Haskell implementation that always copies things and doesn't pass by reference.

...I had a while back and for which I haven't yet seen a good pure functional solution.

With sharing, it's easy to construct what is observationally a tree with O(exp N) elements from only O(N) nodes stored in memory. (I hope that's reasonably correct terminology.)

So very roughly, my problem is about efficiently building vectors from expressions in basis elements, eg. 5*(e_1+3*e_2+5*(e_3+e_4)) should evaluate to (5,15,25,25). An obvious way to evaluate this is from bottom up but it turns out there's a really nice 'adjoint' way to evaluate such expressions from the top down that can exploit sharing in the tree describing the expression. In particular, I want to evaluate these vectors in time O(N) for an O(N)-node expression tree that observationally has O(exp N) nodes.

Rather than clutter LtU with the description, I'll just give a link to my original post on comp.lang.functional.

This problem came up in the context of writing automatic differentiation code. I believe that at least one published functional automatic differentiation algorithm suffers from an exponential running time because of this problem.

A nexus is a tree that contains shared nodes, nodes that have more than one incoming arc. Shared nodes are created in almost every functional program--for instance, when updating a purely functional data structure--though programmers are seldom aware of this. In fact, there are only a few algorithms that exploit sharing of nodes consciously. One example is constructing a tree in sublinear time. In this pearl we discuss an intriguing application of nexuses; we show that they serve admirably as memo structures featuring constant time access to memoized function calls. Along the way we encounter Boolean lattices and binomial trees.

If you look at it closely, functional program itself has lots of sharing using let, or in order words, the lambda abstraction.

original: (\f . f + (f + f)) (1 + 1)

essentially gives you a tree (if you view the + as a node constructor, and number as the leaf) of

unfolded: (1 + 1) + ((1 + 1) + (1 + 1))

You can easily have functions operates on the unfolded form as if it is an ordinary binary tree, while keeping its original form for data structure construction.

But again, I have been working on this for a while, AFAIK, there isn't a generic solution for all cases, unless you involve meta programming to symbolicallyy manipulate the lambdas. Template Haskell (Oleg's solution recently posted to Haskell mailinglist) only does it statically at compile time, which is limited in expressiveness.