[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] Two versions of sum over node list by recursion--why and how does second one work?

---

---

For Dimitre, it can also be written as a divide and conquer
sum(empty-list)=0
sum(item)=item
sum(list)=sum(even-position-items)+ sum(odd-position-items)

David

What is becoming important with this is that not in the so distant
future (I hope) an XSLT processor will calculate:

   sum(even-position-items)
and
   sum(odd-position-items)

in two different threads on two processors so that the total
calculation will be approx. twice as fast.

Parallelization is something very natural in functional programming,
while it can be very difficult to achieve with imperative programming.

--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk

On 9/5/06, David Carlisle <davidc@xxxxxxxxx> wrote:

the second is the normal recursive definition of the sum of a list: the
sum function doesn't take a parameter, the result is just returned as
the result of the function.

sum of a list is defined by

sum (empty-list) = 0
sum(list)= 1st-item + sum(rest-of-list)

see, sum() here doesn't need an explict result parameter.
technically though this means that intermediate results get saved in the
processor's function call stack and so if you have too long a list you
run out of stack space.

Such functions (for some definition of "such") can always be written in
tail recursive form where instead the intermediate results are instead
accumulated in a parameter

sum(list)=sum2(list,0)
sum2(empty-list,total)=total
sum2(list,total)=sum2(rest-of-list,1st-item+total)

For Dimitre, it can also be written as a divide and conquer
sum(empty-list)=0
sum(item)=item
sum(list)=sum(even-position-items)+sum(odd-position-items)

David

---