News for hackers. Stuff that matters.
Re:Pythonic monotonic by eesmith on Friday August 13, 2021 @07:32AM (#28167702)
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 < value
            prev = value
            return test
        return compare

    def monotonic(seq):
        for is_increasing, group in itertools.groupby(seq, compare_with_previous()):
            group = list(group)
            if not is_increasing:
                group.reverse()
            yield group
            
    print(list(monotonic([1, 2, 3, 2, 1, 4, 5, 6, 7])))
Another is to be more itertools oriented:

    import math
    import itertools
    
    # Given a pair (a, b), test if a < b
    def lt_pair(pair):
        return pair[0] < pair[1]

    def monotonic(seq):
        # iterate through a two-element window of the sequence, using -inf as the first term
        seq1, seq2 = itertools.tee(seq)
        window = zip(itertools.chain([-math.inf], seq1), seq2)

        # group by increasing or decreasing (arbitrarily assume equal means increasing)
        for is_increasing, group in itertools.groupby(window, lt_pair):
            if not is_increasing:
                # reverse the direction
                group = list(group)[::-1]
            yield [pair[1] for pair in group]
            
    print(list(monotonic([1, 2, 3, 2, 1, 4, 5, 6, 7])))
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 <= value
            else:
                # Testing for monotonic decreasing
                test = prev_value < value
            prev_value = value
            prev_test = test
            return test
        
        return compare

    def monotonic(seq):
        for is_increasing, group in itertools.groupby(seq, monotonic_comparison()):
            group = list(group)
            if not is_increasing:
                group.reverse()
            yield group
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 <= value
            else:
                test = prev_value < value

            if test == prev_test:
                group.append(value)
            else:
                if not prev_test:
                    group.reverse()
                yield group
                group = [value]
            prev_value = value
            prev_test = test

        if group:
            yield group

  >>> 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 by pierrebai on Friday August 13, 2021 @09:24AM (#28168528)
Why is [2, 1, 1] not being reversed? Since you do call reverse(), I'm not even sure what the bug is on first inspection, which is not a good sign!

Edit: I believe the bug is that the code assumes the first sequence is increasing. It seems a bug carried by all these variants that starts by declaring a -inf variable at the top.

IMO, the problem is trying to find a solution in one's head, then trying to write Pythonic code. The issue is that when someone else reads the code, one does not have the unwritten idea you had in your head.

To write simple code, you must have the least amount of idea in your head. I usually try to write the code dumbly, even if it is inefficient, then do a second pass to remove the most offending parts and maybe make the code more general.

Re:Pythonic monotonic by eesmith on Friday August 13, 2021 @09:40AM (#28168693)
Yes, the -inf approach gives the wrong answer. It's seems clever at first, but induces an invalid mental assumption.
Re:Pythonic monotonic by rirze on Friday August 13, 2021 @08:36AM (#28168116)
Great breakdown.

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

Re:Pythonic monotonic by resters on Friday August 13, 2021 @08:59AM (#28168301)
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 by lpapez on Friday August 13, 2021 @08:37AM (#28168127)
So this only works for numbers right?
Re:Pythonic monotonic by eesmith on Friday August 13, 2021 @09:10AM (#28168397)
Only some numbers.

As is, my implementation requires objects where "<" and "<=" are meaningful, and it requires that a comparison to -math.inf is also meaningful.

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 "<stdin>", line 1, in <module>
    File "monotonic.py", line 40, in monotonic_direct
    test = prev_value <= value
  TypeError: '<=' not supported between instances of 'float' and 'complex'
and second because Python doesn't support an ordering for complex numbers:

  >>> 1j < 2j
  Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
  TypeError: '<' not supported between instances of 'complex' and 'complex'
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. ;)

Re:Pythonic monotonic by contravariant on Friday August 13, 2021 @09:03AM (#28168344)
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.