>   To compute SUM(LIST):
>     1. Let TOTAL = 0.
>     2. Let POSITION = first node of LIST.
>     3. Let TOTAL = TOTAL + value at POSITION.
>     4. Let POSITION = next node after POSITION.
>     5. If POSITION is not the end of the list, go to step 3.
>
> And now, the Other Way:
>
>   1. If LIST is the empty list then SUM(LIST) is defined as 0.
>   2. Otherwise, SUM(LIST) is defined as the first element of LIST + 
> SUM(rest of LIST).
>
> Personally, several things strike me here.
>
> 1. The first version seems a very long and wordy way of explaining 
> something that (to a human) is actually quite simple.
>
> 2. The second version is very much shorter. (And simpler?)

You made it simpler, I can make the first one simpler too :-)

1. If LIST is not the empty list, then SUM(LIST) is defined as the result of 
adding up the value at each node of LIST

> 3. The second version looks like some kind of a riddle. Not a hard riddle, 
> but a somewhat baffling definition all the same.

And seems unnecessarily complex.  Why bother going through splitting lists 
and passing them to recursive functions, when all you really need to do is 
loop through all entries and add up the numbers?

Post a reply to this message

scott <sco### [at] laptopcom> wrote:
> You made it simpler, I can make the first one simpler too :-)

> 1. If LIST is not the empty list, then SUM(LIST) is defined as the result of 
> adding up the value at each node of LIST

  I can make it even simpler:

1. SUM(LIST) = the sum of the values of all nodes in LIST

  In some imperative languages that can be written as something along the
lines of:

sum = 0;
foreach(element in list) sum += element;

  (In some languages even the first line can be omitted if its default
behavior is that undeclared integral variables are automatically created
and initialized to 0.)

-- 
                                                          - Warp

Post a reply to this message

>> 1. If LIST is not the empty list, then SUM(LIST) is defined as the result 
>> of
>> adding up the value at each node of LIST
>
>  I can make it even simpler:
>
> 1. SUM(LIST) = the sum of the values of all nodes in LIST

What would be the point of defining sum if you already had a sum function to 
use?

Post a reply to this message

scott wrote:

>> 2. The second version is very much shorter. (And simpler?)
> 
> You made it simpler, I can make the first one simpler too :-)

I was thinking in terms of how you would literally write the source code 
in imperative and functional languages.

   var total = 0;
   var position = list.start();
   while (position != null)
   {
     total = total + position.get_value();
     position = position.get_next();
   }

Pretty much a verbatim match there.

>> 3. The second version looks like some kind of a riddle. Not a hard 
>> riddle, but a somewhat baffling definition all the same.
> 
> And seems unnecessarily complex.  Why bother going through splitting 
> lists and passing them to recursive functions, when all you really need 
> to do is loop through all entries and add up the numbers?

And of course, accessing parts of a list requires splitting them, and 
recusion isn't looping. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Warp wrote:

>   OTOH, you don't define what "rest of LIST" means.

I also don't define what "end of LIST" means either. But then, I don't 
define what a "list" is at all, so...

>> Anybody else have anything to add?
> 
>   I still like the definition of "connected" in the New Zealand go rules:
> 
> "Two stones of the same colour are connected if they are on adjacent
> intersections or if they are both connected to a third stone."
> 
>   Even most functional programmers have hard time understanding that
> correctly the first time they see it.

Makes perfect sense to me - but then, I'm a maths nerd... ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

> 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

I added a couple of lines:

function sum(list)
>   var total = 0;
>   var position = list.start();
>   while (position != null)
>   {
>     total = total + position.get_value();
>     position = position.get_next();
>   }
return total
end

> Pretty much a verbatim match there.

OK, so for your "Other Method" we have:

function sum(list)
 if( list.start() == NULL )
   return 0
 else
   return list.get_value() + sum(list.get_next())
 endif
end

> And of course, accessing parts of a list requires splitting them, and 
> recusion isn't looping. ;-)

I suspect the recursion method is slower, because calling a function has 
some overheads (storing and recalling registers and return address on stack 
etc).

Post a reply to this message

scott wrote:
> I added a couple of lines:

OK, fair enough.

> OK, so for your "Other Method" we have:
> 
> function sum(list)
> if( list.start() == NULL )
>   return 0
> else
>   return list.get_value() + sum(list.get_next())
> endif
> end

Or, alternatively,

   sum [] = 0
   sum (x:xs) = x + sum xs

as we say in Haskell. The English translation was attempting to preserve 
the structure without actually using Haskell language syntax. But either 
way, you get the idea.

The important thing is you don't say "if the list is empty then *return* 
0", you say "if the list is empty then total is *defined as* 0". That's 
the main difference. (And yes, it's a conceptual difference rather than 
an implementation difference. And that's kind of what I wanted to 
hilight - without going into a long technical debate.)

>> And of course, accessing parts of a list requires splitting them, and 
>> recusion isn't looping. ;-)
> 
> I suspect the recursion method is slower, because calling a function has 
> some overheads (storing and recalling registers and return address on 
> stack etc).

Not when the compiler can detect tail recursion and transform it into a 
normal loop structure automatically.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

> Not when the compiler can detect tail recursion and transform it into a 
> normal loop structure automatically.

So actually, you had the same thought to start with (I want to sum all the 
elements) and the end result is the same assembly code.  So the only real 
point is if you find writing out and thinking about the first solution 
easier than the second or not.  In your own words:

"3. The second version looks like some kind of a riddle. Not a hard
riddle, but a somewhat baffling definition all the same."

So why on Earth bother with the riddle in the first place?

Here's a couple of changes you can try to make to the Haskell version:

1) Modify the code so that it stores the sum up to each element in that 
element.
2) Modify the code so that it sums up nodes in a tree structure, starting 
from any child.

In the 1st version, it's very easy to implement.  For 1) you just add:

position.sumToHere = total

in the loop.

For 2), you change the position = line to:

position = position.GetParent()

All very intuitive, requiring little modification to the sum function.

Post a reply to this message

scott wrote:

> So actually, you had the same thought to start with (I want to sum all 
> the elements) and the end result is the same assembly code.  So the only 
> real point is if you find writing out and thinking about the first 
> solution easier than the second or not.  In your own words:
> 
> "3. The second version looks like some kind of a riddle. Not a hard
> riddle, but a somewhat baffling definition all the same."
> 
> So why on Earth bother with the riddle in the first place?

If all you're trying to do is sum all the elements in a list, neither 
approach has a really compelling advantage or disadvantage. I used it as 
an example of a simple task that anybody can easily understand, and used 
it to illustrate the difference in mentallity between the two approaches.

> Here's a couple of changes you can try to make to the Haskell version:
> 
> 1) Modify the code so that it stores the sum up to each element in that 
> element.

Uh, OK.

   sums xs = sums' 0 xs
     where
       sums' t [] = [t]
       sums' t (x:xs) = t : sums' (t+x) xs

Takes a list of numbers, returns a list of intermediate sums. The first 
element is always 0, the last element is always the total sum of the 
entire list.

> 2) Modify the code so that it sums up nodes in a tree structure, 
> starting from any child.

Erm... I don't really understand what you mean.

> All very intuitive, requiring little modification to the sum function.

Similarly, in Haskell I can define a single function that iterates over 
a list, and then write 1-linears that will find the sum / product / 
minimum / maximum of the list, or the logical AND / OR of a list of 
booleans, or concatenate a list of lists, or... All very intuitive and 
easy to write once you have the iteration function.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message