Test whether an iterable is strictly increasing

General Usage
1

Is there a simple way to test if an iterable (not necessarily instantiated) is strictly increasing? (Cf this long topic on why issorted(itr, lt = <) does not do this). The solution has to be non-allocating.

Simplest I could come up with is a generalization of issorted to

"Test if `f(this, next)` holds for all consecutive elements of `itr`. If not, return early."
function is_pairwise(f, itr)
    y = iterate(itr)
    y === nothing && return true
    prev, state = y
    y = iterate(itr, state)
    while y !== nothing
        this, state = y
        f(prev, this) || return false
        prev = this
        y = iterate(itr, state)
    end
    return true
end

is_pairwise(<, [0.1, 0.1]) # false

IterTools.partition allows a simple implementation too.

2

Iterators.peel makes this a bit simpler (you can avoid the low-level iterate call), while avoiding the allocations of IterTools.partition:

function is_pairwise(f, itr)
    p = Iterators.peel(itr)
    isnothing(p) && return true
    prev, rest = p
    for cur in rest
        f(prev, cur) || return false
        prev = cur
    end
    return true
end
2 Likes
3

where exactly does the allocation with the use of partition happen?

all(Base.splat(<).(IterTools.partition(itr1,2,1)))

julia> @btime IterTools.partition($itr,2,1)
  1.500 ns (0 allocations: 0 bytes)
IterTools.Partition{UnitRange{Int64}, 2}(1:10, 1)

julia> itr=[i^2 for i in 1:10]
10-element Vector{Int64}:
   1
   4
   9
  16
  25
  36
  49
  64
  81
 100

julia> itr1=rand(1:10,10)
10-element Vector{Int64}:
  8
 10
  9
  2
  5
  6
 10
  7
  3
 10
julia> using IterTools

julia> @btime all(Base.splat(<).(IterTools.partition(itr1,2,1)))
  2.389 μs (44 allocations: 2.44 KiB)
false

julia> @btime all(Base.splat(<), IterTools.partition($itr1,2,1))
  320.290 ns (9 allocations: 528 bytes)
false

julia> @btime all(Base.splat(<), IterTools.partition($itr,2,1))
  1.360 μs (37 allocations: 2.05 KiB)
true
4

For a general iterator it returns arrays (which need to be allocated):

julia> collect(Iterators.partition((i for i in 1:5), 2))
3-element Vector{Vector{Any}}:
 [1, 2]
 [3, 4]
 [5]
1 Like