max(), sum(), next()
Ken Starks
straton at lampsacos.demon.co.uk
Sat Sep 6 14:37:09 CEST 2008
castironpi wrote:
> On Sep 5, 9:20 pm, "Manu Hack" <manuh... at gmail.com> wrote:
>> On Fri, Sep 5, 2008 at 1:04 PM, castironpi <castiro... at gmail.com> wrote:
>>> On Sep 5, 3:28 am, "Manu Hack" <manuh... at gmail.com> wrote:
>>>> On Thu, Sep 4, 2008 at 4:25 PM, castironpi <castiro... at gmail.com> wrote:
>>>>> On Sep 4, 2:42 pm, bearophileH... at lycos.com wrote:
>>>>>> David C. Ullrich:
>>>>>>> At least in mathematics, the sum of the elements of
>>>>>>> the empty set _is_ 0, while the maximum element of the
>>>>>>> empty set is undefined.
>>>>>> What do you think about my idea of adding that 'default' argument to
>>>>>> the max()/min() functions?
>>>>>> Bye,
>>>>>> bearophile
>>>>> For max and min, why can't you just add your argument to the set
>>>>> itself?
>>>>> The reason max([]) is undefined is that max( S ) is in S.
>>>> It makes sense.
>>>>> The reason sum([]) is 0 is that sum( [ x ] ) - x = 0.
>>>> It doesn't make sense to me. What do you set x to?
>>> For all x.
>> But then how can you conclude sum([]) = 0 from there? It's way far
>> from obvious.
>
> You can define sum([a1,a2,...,aN]) recursively as
> sum([a1,a2,...a(N-1)])+aN. Call the sum sum([a1,a2,...,aN]) "X", then
> subtract aN.
>
> sum([a1,a2,...a(N-1)])+aN=X
> sum([a1,a2,...a(N-1)])+aN-aN=X-aN
>
> For N=2, we have:
>
> sum([a1,a2])=X
> sum([a1,a2])-a2=X-a2
> sum([a1,a2])-a2-a1=X-a2-a1
>
> Since X= a1+ a2, replace X.
>
> sum([a1,a2])-a2-a1=(a1+a2)-a2-a1
>
> Or,
>
> sum([a1,a2])-a2-a1=0
>
> Apply the recursive definition:
>
> sum([a1])+a2-a2-a1=0
>
> And again:
>
> sum([])+a1+a2-a2-a1=0
>
> And we have:
>
> sum([])=0.
>
This is not necessarily so.
The flaw is that you provide a recursive definition with no start value,
which is to say it is not a recursive definition at all.
A recursive definition should be (for lists where elements
can be added, and ignoring pythonic negative indexing):
Define 'sum(L)' by
a. sum(L[0]) = L[0]
b. sum(L[0:i]) = sum(L[0:i-1]) + L[i] ... if i > 0
From this you can prove the reverse recursion
sum{L[0:k]) = sum(L[0:k+1]) - L[k+1]
__only__ if k >= 0
It says nothing about the empty list.
You could add, as part of the definition, that sum{[]) = 0, or any other
value.
A rather different approach, not quite simple recursion, would be to
start with
A. a slicing axiom, something like:
for all non-negative integers, a,b,c with a <=b <= c:
sum(L[a:c]) = sum(L[a:b]) + sum(L[b:c])
B. a singleton axiom:
for all integers a where L[a] exists:
sum(L[a:a]) = L[a]
2a. sum{
More information about the Python-list
mailing list