10
$\begingroup$

Alright, so this is a question about the functional way to break a for/while loop. Since we're on the Mathematica SE, I'm interested in the ways a Mathematica vet would handle this, however the question is similar in spirit to this question. I am also interested in lazy evaluation in Mathematica.

For instance, consider writing an algorithm to detect whether an array is monotonic or not. How could I rewrite the algorithm below so that it

  • does not check the entire array and,
  • does not store the entire input array in memory?
n = 1000;
input = {5, 4, 3}~Join~Range[1, n];
AllTrue[Differences[input], # >= 0 &] || AllTrue[Differences[input], # <= 0 &]

In Python 3+, one way to do this is shown below. All the operations below work on an iterator level, so only the necessary elements are computed. You can test this by setting n=100000000 and compare to the algorithm above.

from itertools import chain, islice, tee

def pairwise(iterable):
  "s -> (s0,s1), (s1,s2), (s2, s3), ..."
  a, b = tee(iterable)
  return zip(a, islice(b, 1, None))

def isMonotonic(iterable):
  pw_iterable = pairwise(iterable)
  all_increasing = all(x <= y for x, y in pw_iterable)
  all_decreasing = all(x >= y for x, y in pw_iterable)
  return all_decreasing or all_increasing

n = 1000
arr = chain([5,4,3], range(1, n+1)) # obviously, non-monotonic
print(isMonotonic(arr))

I hope I've made clear my broader set of questions about computations in which a loop should be allowed to terminate early and the later elements in the list need not be computed. I would love to see how this would be done in an idiomatic Mathematica way.


@xzczd's hint to look at the lazy-computations tag helped me find this related question. TL;DR: there have been a number of attempts at implementing lazy functionality. These two appear to be the most up-to-date:

$\endgroup$
5
  • 1
    $\begingroup$ "…ideally, does not store the entire input array in memory", as to this part, you may want to check posts under the tag lazy-computations. $\endgroup$
    – xzczd
    Jul 22, 2020 at 2:40
  • 1
    $\begingroup$ Use AnyTrue and invert the condition, which will break early, not AllTrue - as this would check all elements. $\endgroup$
    – flinty
    Jul 22, 2020 at 2:42
  • 1
    $\begingroup$ I think AnyTrue is unnecessary, since AllTrue can exit early once it sees at least one False. $\endgroup$
    – dusky
    Jul 22, 2020 at 3:01
  • $\begingroup$ I suppose you are right - it's 4am here an I must be losing it. $\endgroup$
    – flinty
    Jul 22, 2020 at 3:08
  • $\begingroup$ No worries, I've definitely been there. $\endgroup$
    – dusky
    Jul 22, 2020 at 3:24

2 Answers 2

8
$\begingroup$

In my lazyLists package mentioned by the OP, you would do something like this to find out if a list is monotonic:

<< lazyLists`
n = 100000;
(* lazy representation of the example input *)
input = lazyCatenate[{{3, 4, 2}, lazyGenerator[# &, 1, 1, n, 1]}];
monotonicQ[lz_lazyList, test_] := Catch[
 FoldList[
   If[TrueQ @ test[#2, #1], #2, Throw[False, "nonmonotonic"]]&,
   lz
 ][[-1]]; (* taking the last part iterates through the lazyList *)
 True
 ,
 "nonmonotonic"
];
monotonicQ[input, Greater]

False

You can also use partitionedLazyList to generate elements in batches, which is usually faster for long arrays.

$\endgroup$
0
6
$\begingroup$

Applying DeMorgan's law to the logic simplifies things a bit:

With[{ d = Differences[input] },
 Nand[AnyTrue[d, # < 0 &], AnyTrue[d, # > 0 &]]
]

The idiomatic™ way to solve this is with SequenceCases to report the first case where an element is smaller than the previous one:

ismontoneinc[list_] := SequenceCases[list, {x_, y_} /; y < x, 1] == {}
ismontonedec[list_] := SequenceCases[list, {x_, y_} /; y > x, 1] == {}
ismonotone[list_] := ismontoneinc[list] || ismontonedec[list]
data = {1, 2, 3, 4, 1, 6}; ismonotone[data]
(* result: False - not monotone *)

data = {1, 2, 3, 4, 5, 6, 7, 8}; ismonotone[data]
(* result: True - monotone *) 

data = {5,3,2,0}; ismonotone[data]
(* result: True - monotone *) 

However, this has hopelessly bad performance with a million random integers in v12.1.1. and terrible memory usage too. Just try ismonotone[RandomReal[1, 100000]] - it clearly doesn't even break early which is very disappointing. I guess Mathematica is full of surprises.

$\endgroup$
7
  • $\begingroup$ @xzczd the question's Mathematica code was updated to note this, I've edited it. $\endgroup$
    – flinty
    Jul 22, 2020 at 2:49
  • 1
    $\begingroup$ The documentation for AllTrue says "AllTrue[list,test] and AllTrue[list,test,level] only evaluate as many test[Subscript[e, i]] as are necessary to determine the result", so I doubt the DeMorgan's laws are necessary. Can you say something about the need to load the data list into memory? Can that be avoided? $\endgroup$
    – dusky
    Jul 22, 2020 at 2:59
  • $\begingroup$ AllTrue must check all the elements in this particular case - AnyTrue only needs to find one counterexample to terminate, so yes it does help here. $\endgroup$
    – flinty
    Jul 22, 2020 at 3:01
  • $\begingroup$ Maybe, I'm confused, but that doesn't seem right. See my comment on the question thread. $\endgroup$
    – dusky
    Jul 22, 2020 at 3:04
  • 1
    $\begingroup$ @dskeletov no, your code is faster than mine , SequenceCases is much slower at scale I'm finding. It also doesn't seem to break early with large lists which must be a bug of some kind. $\endgroup$
    – flinty
    Jul 22, 2020 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.