# Breaking "Functional Loops" and Doing Lazy Evaluation In Mathematica

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:

• "…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. Jul 22, 2020 at 2:40
• Use AnyTrue and invert the condition, which will break early, not AllTrue - as this would check all elements. Jul 22, 2020 at 2:42
• I think AnyTrue is unnecessary, since AllTrue can exit early once it sees at least one False. Jul 22, 2020 at 3:01
• I suppose you are right - it's 4am here an I must be losing it. Jul 22, 2020 at 3:08
• No worries, I've definitely been there. Jul 22, 2020 at 3:24

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.

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.

• @xzczd the question's Mathematica code was updated to note this, I've edited it. Jul 22, 2020 at 2:49
• 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? Jul 22, 2020 at 2:59
• 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. Jul 22, 2020 at 3:01
• Maybe, I'm confused, but that doesn't seem right. See my comment on the question thread. Jul 22, 2020 at 3:04
• @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. Jul 22, 2020 at 3:27