TransWikia.com

Breaking "Functional Loops" and Doing Lazy Evaluation In Mathematica

Mathematica Asked on November 17, 2021

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:

2 Answers

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.

Answered by Sjoerd Smit on November 17, 2021

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.

Answered by flinty on November 17, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP