 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Compare these two psuedocode snippets:
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?)
3. The second version looks like some kind of a riddle. Not a hard
riddle, but a somewhat baffling definition all the same.
I think it neatly demonstrates the fundamental difference in the mental
model between imperative and functional programming though. Even a
layman who knows nothing about programming would (I suspect) appriciate
that these two methods are pretty different. (And without having to go
into a long lecture about how computers work, how to program in any
specific language, etc.)
Anybody else have anything to add?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
How about another algorithm?
------------------------------------------------------
A NODE contains a VALUE entry, which holds a number, and the entries
CHILD0 and CHILD1, which either point to a NODE or point to nothing.
ADD(X, ROOT):
1. If ROOT points to nothing then
1. Let OUT = a new NODE.
2. Let OUT.VALUE = X.
3. Return OUT.
2. If ROOT.VALUE < X then
1. Let Y = ROOT.VALUE
2. Let T = ROOT.CHILD0.
2. Let ROOT.VALUE = X.
3. Let ROOT.CHILD0 = ADD(Y, ROOT.CHILD1).
4. Let ROOT.CHILD1 = T.
5. Return ROOT.
else
1. Let T = ROOT.CHILD0.
2. Let ROOT.CHILD0 = ADD(X, ROOT.CHILD1).
3. Let ROOT.CHILD1 = T.
4. Return ROOT.
------------------------------------------------------
Data of type HASH is either 'NODE' with a NUMBER value called VALUE and
a HASH value named CHILD0 and a HASH value named CHILD1, or 'NULL'.
ADD(X, NULL) = HASH (VALUE = X, CHILD0 = NULL, CHILD1 = NULL)
ADD(X, NODE A B) = HASH (VALUE = if X < Y then Y else X, CHILD0 = ADD(if
X < Y then X else Y, B), CHILD1 = A)
------------------------------------------------------
Notice: First program is long and thin. Second program is short and fat.
(My, my... line wrapping!)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v7 <voi### [at] dev null> wrote:
> 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).
OTOH, you don't define what "rest of LIST" means.
> 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.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Compare these two psuedocode snippets:
>
> 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?)
>
> 3. The second version looks like some kind of a riddle. Not a hard riddle,
> but a somewhat baffling definition all the same.
>
> I think it neatly demonstrates the fundamental difference in the mental
> model between imperative and functional programming though. Even a layman
> who knows nothing about programming would (I suspect) appriciate that
> these two methods are pretty different. (And without having to go into a
> long lecture about how computers work, how to program in any specific
> language, etc.)
>
> Anybody else have anything to add?
Neither of these ways is how you would do it if you weren't using a
computer.
By hand you would add up the digits in the first column making carry marks,
and get the rightmost digit of the answer and work your way left, column by
column. If there were several pages worth, you'd probably make sub-totals,
then add those up later. Those psuedocode examples are just describing
real code someone had already thought up, so it's not surprising that you
can
tell which way they were thinking. Are you describing a process or an
algorithm?
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.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tim Attwood <tim### [at] comcastnet> wrote:
> 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.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> 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
|
|
| |
| |
|
|
|
|
| |
