xsl-list
[Top] [All Lists]

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

2006-09-05 11:39:14
```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(_at_)nag(_dot_)co(_dot_)uk> 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
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

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

```
```
--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

```
 Current Thread [xsl] Two versions of sum over node list by recursion--why and how does second one work?, hanged(_dot_)man(_at_)lycos(_dot_)com Re: [xsl] Two versions of sum over node list by recursion--why and how does second one work?, David Carlisle Re: [xsl] Two versions of sum over node list by recursion--why and how does second one work?, Dimitre Novatchev <= Re: [xsl] Two versions of sum over node list by recursion--why and how does second one work?, andrew welch RE: [xsl] Two versions of sum over node list by recursion--why and how does second one work?, Michael Kay Re: [xsl] Two versions of sum over node list by recursion--why and how does second one work?, Dimitre Novatchev