> 1. divide the list into manageable sub-lists (pages)
> 2. add up the sub-lists and get sub-totals
> 3. add up the sub-totals and get the sum of the list

> vrs

> 1. 0 for an empty list
> 2. number for a list with 1 number
> 3. number + number for a list with 2 numbers
> 4. sum of the first half of list + sum of the second half of list,
>    for a list with at least 3 numbers.

>  I think those require random access, which is not available for linked
> lists.

I'm not sure that "list" always means linked list in a
functional language, they're optimized into arrays
behind the curtain, and you're not free to change
the link pointers because they're treated as static
(at least in Haskell).

The first one is very loosely defined, it doesn't
say what is manageable, it doesn't say how to
add those chunks together, or in what order. It's
easy to imagine processing it in parallel, or reading
numbers from a file in chunks, then adding them up
sequentially as you go along, or if manageable means
two at a time, it could identical to Andrew's.

The second describes an algorithm, not the data
structures needed to implement it. It's probably
too specific in parts, and very unspecific about
how to determine where to split the list in half,
or differences in performance between using it
for boxed or unboxed number types.

There's nothing overwhelmingly "functional biased"
about a recursive algorithm, but providing a
description of the desired results and then letting the
rest sort itself out probably is. That's not always a
good thing, machine code is imperative so every
bit of code is describing actions, the separation of
function from actions is artificial.

Post a reply to this message