Search a sequence for its minimum and stop as soon as the lowest possible value is found

Jussi Piitulainen jussi.piitulainen at helsinki.fi
Sat Jan 7 11:38:16 EST 2017


Rustom Mody writes:
> On a Saturday, Jussi Piitulainen wrote:

[snip]

>> You switched to a simpler operator. Would Haskell notice that
>> 
>>    def minabs(x, y): return min(x, y, key = abs)
>> 
>> has a meaningful zero? Surely it has its limits somewhere and then
>> the programmer needs to supply the information.
>
> Over ℕ multiply has 1 identity and 0 absorbent
> min has ∞ as identity and 0 as absorbent
> If you allow for ∞ they are quite the same

There is nothing like ∞ in Python ints. Floats would have one, but we
can leave empty minimum undefined instead. No worries.

> Below I am pretending that 100 = ∞

Quite silly but fortunately not really relevant.

> Here are two lazy functions:
> mul.0.y = 0  -- Lazy in y ie y not evaluated
> mul.x.y = x*y
>
> minm.0.y = 0  -- likewise lazy in y
> minm.x.y = min.x.y

Now I don't see any reason to avoid the actual function that's been the
example in this thread:

minabs.0.y = 0
minabs.x.y = x if abs.x <= abs.y else y 

And now I see where the desired behaviour comes from in Haskell. The
absorbing clause is redundant, apart from providing the specific
stopping condition explicitly.

> Now at the interpreter:
> ? foldr.minm . 100.[1,2,3,4]
> 1 : Int
> ? foldr.minm . 100.[1,2,3,4,0]
> 0 : Int
> ? foldr.minm . 100.([1,2,3,4,0]++[1...])
> 0 : Int
>
> The last expression appended [1,2,3,4,0] to the infinite list of numbers.
>
> More succinctly:
> ? foldr.minm . 100.([1,2,3,4,0]++undefined)
> 0 : Int
>
> Both these are extremal examples of what Peter is asking for — avoiding an 
> expensive computation

Ok. Thanks.


More information about the Python-list mailing list