Pure functional tree up algorithm

Question

Let's say I wanted to write an algorithm that works on an immutable tree data structure that has a list of leaves. He must return the new tree with the changes made to the old tree, going up from these leaves.

My problem is that there seems to be no way to make this purely functional without restoring the whole tree that checks the leaves if they are on the list, because you always need to return a complete new tree as a result of the operation and you cannot mutate an existing tree .

Is this the main problem in functional programming that can only be avoided with a more suitable algorithm, or am I missing something?

Edit: Not only do I want to avoid re-creating the entire tree, but the functional algorithm should have the same complexity in time than the mutating option.

Answer 1

The most promising so far I have seen (which, admittedly, is not very long ...) is the Zipper Data Structure : This basically saves a separate structure, the way back from node to root, and makes local changes to this separate structure.

It can make several local changes, most of which are constant time, and write them back to the tree (restoring the path to the root, which are the only nodes that need to be changed) at a time.

Zipper is the standard library in Clojure (see the Zippers - Editing Functional Tree heading).

And there is original paper from Huet with implementation in OCaml.

Disclaimer: I programmed for a long time, but a couple of times I started working only with functional programming and did not even hear about the problem of functional editing of trees until last week, so there may well be other solutions I don’t know.

However, it seems that Zipper does most of what you could wish for. If there are other alternatives in O (log n) or lower, I would like to hear them.

Answer 2

You may like to read

http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!248.entry

Answer 3

It depends on your functional programming language. For example, in Haskell, which is the Lazy functional programming language, the results are calculated at the last moment; when they are needed.

In your example, it is assumed that since your function creates a new tree, the whole tree should be processed, while in reality the function is simply passed to the next function and executed only if necessary.

A good example of lazy rating is the Haskell erastothenes sieve , which creates prime numbers by eliminating multiples of the current number in the list of numbers. Note that the list of numbers is endless. Taken from here

primes :: [Integer] primes = sieve [2..] where sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]