Breaking "Functional Loops" and Doing Lazy Evaluation In Mathematica

Question

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:

• lazyLists package
• Streaming package (doesn't appear to be actively maintained, but a comment in 2019 by L. Shifrin reports it may get more attention); see an introductory post here

Answer 1

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.

Answer 2

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.