Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Pythonic monotonic

nedbatchelder.com

Post reply on HN
Print view View original

1–10 of 64 posts

Re: Pythonic monotonic

#2

Post by eesmith »

I like how the first one uses groupby() but I don't like the definition of "Monotonic" inside of the module, nor the name, nor returning a list instead of a generator. I also prefer functions instead of callable instances.

One alternative to use a function closure instead of a class:

    import math
    import itertools

    def compare_with_previous():
        prev = -math.inf
        def compare(value):
            nonlocal prev
            test = prev
Another is to be more itertools oriented:

    import math
    import itertools
    
    # Given a pair (a, b), test if a
NOTE! None of these solutions support monotonicity correctly for equal values!

  >>> print(list(monotonic([1, 1, 2, 3, 3, 2, 1, 1])))
  [[1], [1], [2, 3], [1, 1, 2, 3]]
  >>> list(mono_runs_simpler([1, 1, 2, 3, 3, 2, 1, 1]))
  [[1], [1], [2, 3], [1, 2, 3], [1]]
That should be (IMO):

  [[1, 1, 2, 3, 3], [2, 1, 1]]
as the term "strictly monotonic" is for the always-increasing or always-decreasing.

Handling this case is much easier in the first of these two implementations:

    import math
    import itertools

    def monotonic_comparison():
        prev_value = -math.inf
        prev_test = True
        def compare(value):
            nonlocal prev_value, prev_test
            if prev_test:
                # Testing for monotonic increasing
                test = prev_value
HOWEVER! At this point it's a lot of work structured around using groupby(). It's more readable, as Ned Batchelder points out, to just write the code directly, without groupby() or nonlocal:

    import math
    def monotonic_direct(seq):
        prev_value = -math.inf
        prev_test = True
        group = []
        for value in seq:
            if prev_test:
                test = prev_value >> print(list(monotonic_direct([1, 2, 3, 2, 1, 4, 5, 6, 7])))
  [[1, 2, 3], [1, 2], [4, 5, 6, 7]]
  >>> print(list(monotonic_direct([1, 1, 2, 3, 3, 2, 1, 1])))
  [[1, 1, 2, 3, 3], [2, 1, 1]]
(I'm using -inf as a special sentinel, instead of special-casing the [0] element but I think that's a minor point.)

EDIT: I am wrong. The initial -inf means the first term is always assumed to be in an increasing subsequence, even if it is part of a decreasing subsequence:

  >>> list(monotonic_direct([10, 9, 8]))
  [[10], [9, 8]]
As such, the original reference "Monotonic" implementation is wrong, as well as Ned's version!

  >>> list(mono_runs_simpler([10, 9, 8]))
  [[10], [9, 8]]
It should be [[10, 9, 8]].

Re: Pythonic monotonic

#3

Post by rirze »

eesmith wrote: post #2

I like how the first one uses groupby() but I don't like the definition of "Monotonic" inside of the module, nor the name, nor returning a list instead of a generator. I also prefer functions instead of callable instances. One alternative to use a function closure instead of a class: import math import itertools def compare_with_previous(): prev = -math.inf def compare(value): nonlocal prev test = prev Another is to…

Great breakdown.

I find myself running into the same limitation sometimes-- functools/itertools are only so flexible.

Re: Pythonic monotonic

#4

Post by lpapez »

eesmith wrote: post #2

I like how the first one uses groupby() but I don't like the definition of "Monotonic" inside of the module, nor the name, nor returning a list instead of a generator. I also prefer functions instead of callable instances. One alternative to use a function closure instead of a class: import math import itertools def compare_with_previous(): prev = -math.inf def compare(value): nonlocal prev test = prev Another is to…

So this only works for numbers right?

Re: Pythonic monotonic

#5

Post by mjburgess »

The first case is clearer to me than the second, by quite away.

Iter, next? Opaque testing of [-1] values?

Adjusting a few identifier names, the first actually describes what's going on.

Eg., rename `Monotonic()` to `CurrentLtLast()`

Re: Pythonic monotonic

#6

Post by resters »

eesmith wrote: post #2

I like how the first one uses groupby() but I don't like the definition of "Monotonic" inside of the module, nor the name, nor returning a list instead of a generator. I also prefer functions instead of callable instances. One alternative to use a function closure instead of a class: import math import itertools def compare_with_previous(): prev = -math.inf def compare(value): nonlocal prev test = prev Another is to…

Wow, the last example is so much more readable than all of the others... the way I think Python should be written and (generally) a nice aspect of Python culture that people will write code that way.

Re: Pythonic monotonic

#8

Post by contravariant »

lpapez wrote: post #4
eesmith wrote: post #2

I like how the first one uses groupby() but I don't like the definition of "Monotonic" inside of the module, nor the name, nor returning a list instead of a generator. I also prefer functions instead of callable instances. One alternative to use a function closure instead of a class: import math import itertools def compare_with_previous(): prev = -math.inf def compare(value): nonlocal prev test = prev Another is to…

So this only works for numbers right?

If they use math.inf then yeah probably.

You might be able to create an object that always compares as less than something, using something like:

    class Bottom:
        def __le__(self, other):
            return True

        def __lt__(self, other):
            return True
though use this with care.

Re: Pythonic monotonic

#10

Post by eesmith »

lpapez wrote: post #4
eesmith wrote: post #2

I like how the first one uses groupby() but I don't like the definition of "Monotonic" inside of the module, nor the name, nor returning a list instead of a generator. I also prefer functions instead of callable instances. One alternative to use a function closure instead of a class: import math import itertools def compare_with_previous(): prev = -math.inf def compare(value): nonlocal prev test = prev Another is to…

So this only works for numbers right?

Only some numbers.

As is, my implementation requires objects where "For example, it won't work with complex numbers, first because they cannot be compared to -math.inf:

  >>> list(monotonic_direct([1j, 2j, 4j]))
  Traceback (most recent call last):
    File "", line 1, in 
    File "monotonic.py", line 40, in monotonic_direct
    test = prev_value
and second because Python doesn't support an ordering for complex numbers:

  >>> 1j ", line 1, in 
  TypeError: '
As I mentioned, it's possible to replace the sentinel -math.inf with something that starts with seq[0]. This would allow strings and orderable objects.

This is left as an exercise for the reader. ;)

Post reply on HN