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

Rustom Mody rustompmody at gmail.com
Sat Jan 7 10:14:58 EST 2017


On Saturday, January 7, 2017 at 1:42:47 PM UTC+5:30, Jussi Piitulainen wrote:
> Rustom Mody writes:
> 
> > On Saturday, Jussi Piitulainen wrote:
> >> Paul Rubin writes:
> >> 
> >> > Peter Otten writes:
> >> >> How would you implement stopmin()?
> >> >
> >> > Use itertools.takewhile
> >> 
> >> How? It consumes the crucial stop element:
> >> 
> >>    it = iter('what?')
> >>    list(takewhile(str.isalpha, it)) # ==> ['w', 'h', 'a', 't']
> >>    next(it, 42) # ==> 42
> >
> > I was also wondering how…
> > In a lazy language (eg haskell) with non-strict foldr (reduce but
> > rightwards) supplied non-strict operator this is trivial.
> > ie in python idiom with reduce being right_reduce
> > reduce(operator.mul, [1,2,0,4,...], 1)
> > the reduction would stop at the 0
> > Not sure how to simulate this in a strict language like python
> > Making fold(r) non-strict by using generators is ok
> > How to pass a non-strict operator?
> 
> I think it would have to be some really awkward pseudo-operator that
> throws an exception when it encounters its zero, and then reduce (or
> something outside reduce) would catch that exception. Something like
> that could be done but it would still be awkward. Don't wanna :)
> 
> 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

Below I am pretending that 100 = ∞

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 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


More information about the Python-list mailing list