Functional programming problem

[Dan Piponi]

I have what I think is an interesting algorithm that I'd like to
implement functionally but am having trouble doing so. Maybe someone
can give me some suggestions.

Consider an N-dimensional vector space V with basis e_1,...,e_N. Now
consider an expression that is linear in the e_i, for example
5*(e_1+3*e_2+5*(e_3+e_4)). We can represent this as a tree with 10
nodes (4 basis elements at the leaves, 3 scalar multiplications (I'm
consider the scalar to be part of the node so that every node
represents a vector value) and 3 additions). I want to evaluate these
as N-dimensional arrays. A simple algorithm to evaluate such
expressions is to implement N-dimensional vectors as arrays and
implement addition and scalar multiplication in the obvious way. If the
expression has M nodes then the algorithm runs in time O(MN).

We can get the running time down to the fastest possible, O(M+N), by
evaluating the expression in reverse. Instead of evaluating expressions
from the bottom up we work top down. Essentially we annotate each node
of the tree with a 'multiplier' value that is inherited from its
parent, except for the root that gets 1. We copy this multiplier
directly from the parent to its children, unless the parent is scalar
multiplication in which case we scale the multiplier before passing it
to the children. Eventually every basis element acquires a multiplier
and we can now sweep up basis elements. Although I've described this in
terms of annotating nodes this algorithm can be implemented
functionally without mutating the tree, and by using unboxed arrays in
Haskell I was able to achieve running time O(M+N), O(N) to initially
zero out the final array, O(M) to sweep through the tree.

Now I have a piece of code that performs additions and scalar
multiplications on vectors and so instead of using the first method I
described I instead implement operators ^+ and ^* to build a tree which
is then evaluated at the end. Unfortunately I then noticed that
although I'm essentially evaluating my trees in linear times I can
build trees in logarithmic time. By writing let a = b^+c in a^+a I am
using sharing to build trees whose node counts can grow exponentially.
In other words in time T I can build an expression that takes time
O(exp(c*T)) to evaluate.

Now I have a C++ version of the code that can exploit the sharing so
that expressions built in time T take time O(T) to evaluate.
Essentially, in the inherit stage I described above a node inherits the
sum of the multipliers from all of its parents which it can do by
storing partial sums in the tree itself. This means a node is visited
only once, even if shared many times. But after weeks of thought I
cannot figure out how to do this functionally and elegantly. The
expression let a=e_1^+e_2 in a^+a is functionally indistinguishable
from a=(e_1+e_2)+(e_1+e_2) so there is no way to implement the inherit
from all parents step. I can imagine an algorithm that builds a tree by
naming nodes with strings (say) and storing adjacency information. But
this is pretty complex compared to the C++ implementation and also
requires threading the structure representing the graph throughout the
entire computation, something that messes up the simple elegance of
being able to write expressions like e_1^+e_2.

Des anyone have any suggestions for how to get my expressions evaluated
functionally in linear time again?

[Florian Kreidler]

Dan Piponi <goog...@sigfpe.com> schrieb:

> Des anyone have any suggestions for how to get my expressions evaluated
> functionally in linear time again?

Instead of constructing a tree and then evaluating it with a function
(eval::Tree->In-Out), you could directly construct a function (In->Out).
For example

(^*),(^+)::(In->Out) -> (In->Out) -> (In->Out)
(a ^* b) arg = a arg * b arg
(a ^+ b) arg = a arg + b arg

then, instead of building a tree

myTree = let p = x ^+ y in p ^* p

you build a function

myFun arg = let p = (x ^+ y) arg in (const p ^* const p) arg
(where const out' in = out')

I don't know if that helps in your case.

[Dan Piponi]

Actually, the first draft of my code worked a little like that although
the rhs of the defintions of ^+ and ^* was a little more complex. But I
think this approach makes it makes the sharing issue even harder to
think about :-)