Range

Range module: integer ranges as first-class values.

A range is a record {start: Int, stop: Int, step: Int}. Ranges are half-open: [start, stop) when step > 0, (stop, start] when step < 0. step must be non-zero; new/2 defaults to step = 1. Every function that walks a range (to_list, each, and the ones built on to_list) takes it refined as {v : IntRange | v.step != 0} and panics on a zero step, which would otherwise never advance.

Types

typeIntRangeIntRange = { start : Int, stop : Int, step : Int }#

The record every function here takes. Records are structural, so a plain {start: ..., stop: ..., step: ...} literal is one; the name exists so a refinement can read its step.

Functions

fnallall(r : {v : IntRange | v.step != 0}, f : Int -> Bool) : Bool#

Returns true if every element satisfies f (true for an empty range).

Examples

march> Range.all(Range.new(1, 5), fn x -> x > 0)
true
march> Range.all(Range.new(0, 0), fn x -> x > 100)
true

fnanyany(r : {v : IntRange | v.step != 0}, f : Int -> Bool) : Bool#

Returns true if at least one element satisfies f (false for an empty range).

Examples

march> Range.any(Range.new(1, 5), fn x -> x == 4)
true
march> Range.any(Range.new(1, 5), fn x -> x == 5)
false

fncontainscontains(r : {start: Int, stop: Int, step: Int}, n : Int) : Bool#

Returns true if n is one of the range's elements: within the bounds and on a step boundary. O(1).

Examples

march> Range.contains(Range.new_step(0, 10, 3), 6)
true
march> Range.contains(Range.new_step(0, 10, 3), 7)
false
march> Range.contains(Range.new(0, 5), 5)
false
march> Range.contains(Range.new_step(5, 0, -1), 1)
true

fneacheach(r : {v : IntRange | v.step != 0}, f : Int -> Unit) : Unit#

Calls f on each element in iteration order, for side effects. Returns (). Panics if the step is zero (also a refinement precondition).

Examples

Range.each(Range.new(0, 3), fn i -> println(int_to_string(i)))
-- prints 0, 1 and 2 on separate lines

fnfilterfilter(r : {v : IntRange | v.step != 0}, f : Int -> Bool[p]) : List(Int[p])#

Returns the list of elements satisfying predicate f, in iteration order. Every element of the result is known to satisfy f (an abstract refinement p, as for List.filter).

Examples

march> Range.filter(Range.new(0, 10), fn x -> x % 4 == 0)
[0, 4, 8]

fnfirstfirst(r : {start: Int, stop: Int, step: Int}) : Option(Int)#

Returns Some of the first element (start), or None if the range is empty.

Examples

march> Range.first(Range.new(3, 6))
Some(3)
march> Range.first(Range.new(6, 3))
None

fnis_emptyis_empty(r : {start: Int, stop: Int, step: Int}) : Bool#

Returns true if the range contains no elements. O(1).

Examples

march> Range.is_empty(Range.new(2, 2))
true
march> Range.is_empty(Range.new_step(2, 0, -1))
false

fnlastlast(r : {start: Int, stop: Int, step: Int}) : Option(Int)#

Returns Some of the last element, or None if the range is empty. O(1); the last element is the final step boundary, not necessarily stop - 1.

Examples

march> Range.last(Range.new(3, 6))
Some(5)
march> Range.last(Range.new_step(0, 10, 3))
Some(9)
march> Range.last(Range.new(6, 3))
None

fnmapmap(r : {v : IntRange | v.step != 0}, f : Int -> b) : List(b)#

Applies f to each element in iteration order, returning a list of results.

Examples

march> Range.map(Range.new(1, 4), fn x -> x * x)
[1, 4, 9]
march> Range.map(Range.new(1, 1), fn x -> x * x)
[]

fnnewnew(start : Int, stop : Int) : {v : IntRange | v.step != 0}#

Creates the half-open range [start, stop) with step 1. The range is empty when stop <= start.

Examples

march> Range.to_list(Range.new(0, 4))
[0, 1, 2, 3]
march> Range.to_list(Range.new(3, 3))
[]

fnnew_stepnew_step(start : Int, stop : Int, step : {Int | _ != 0}) : {v : IntRange | v.step != 0}#

Creates a range with an explicit step. With step > 0 it covers [start, stop) counting up; with step < 0 it covers (stop, start] counting down. Panics if step is zero (also a refinement precondition).

Examples

march> Range.to_list(Range.new_step(0, 10, 3))
[0, 3, 6, 9]
march> Range.to_list(Range.new_step(5, 0, -2))
[5, 3, 1]
march> Range.to_list(Range.new_step(0, 5, -1))
[]

fnreducereduce(r : {v : IntRange | v.step != 0}, acc : b, f : b -> Int -> b) : b#

Left fold over the range in iteration order; f is called as f(acc, element).

Examples

march> Range.reduce(Range.new(1, 5), 1, fn (acc, x) -> acc * x)
24
march> Range.reduce(Range.new_step(3, 0, -1), [], fn (acc, x) -> Cons(x, acc))
[1, 2, 3]

fnreversereverse(r : {v : IntRange | v.step != 0}) : {start: Int, stop: Int, step: Int}#

Returns a range with the same elements iterated in the opposite direction (start becomes the last element, step is negated). An empty range is returned unchanged. O(n): the elements are materialised to find the last one.

Examples

march> Range.to_list(Range.reverse(Range.new(0, 4)))
[3, 2, 1, 0]
march> Range.to_list(Range.reverse(Range.new_step(0, 10, 3)))
[9, 6, 3, 0]
march> Range.to_list(Range.reverse(Range.new(2, 2)))
[]

fnsizesize(r : {start: Int, stop: Int, step: Int}) : Int#

Returns the number of elements in the range, computed arithmetically in O(1).

Examples

march> Range.size(Range.new(0, 10))
10
march> Range.size(Range.new_step(0, 10, 3))
4
march> Range.size(Range.new(5, 2))
0

fnsumsum(r : {v : IntRange | v.step != 0}) : Int#

Returns the sum of all elements in the range (0 for an empty range).

Examples

march> Range.sum(Range.new(1, 101))
5050
march> Range.sum(Range.new_step(10, 0, -5))
15
march> Range.sum(Range.new(5, 5))
0

fnto_listto_list(r : {v : IntRange | v.step != 0}) : List(Int)#

Converts the range to a list of integers, in iteration order. O(n). Panics if the step is zero (also a refinement precondition).

Examples

march> Range.to_list(Range.new(1, 4))
[1, 2, 3]
march> Range.to_list(Range.new_step(3, 0, -1))
[3, 2, 1]