lib.interval
Library for integer and real interval arithmetic.
Intervals are represented by attrsets with the following attributes.
If it is an integer interval, integer is set to true otherwise false,
always present. The set { integer = true (or false); } represents the open
interval $(-∞,∞)$, if the interval has a lower bound the attrset has two
attributes, min set to the bound and lInc which is true if the lower
bound is closed, similarly with max and uInc if there is an upper bound.
There is no canonical representation for the empty interval, any interval
containing no values is considered empty.
Real intervals are different from integer intervals in that they contain an infinite amount of values, unless they are a singleton interval with only a single value. Nix's numbers are either integers or double-precision floating point values. Floating point values form a discrete set of finite size, so an interval of floating point values is really not that similar from an interval of integer values. Since the floating point values are merely chosen as a practical representation of real values, we treat non-integer intervals as intervals of real numbers. This has an impact on the interpretation of connectedness for example, even if there are no possible floating point values in between two given intervals, they are not considered connected if a real value exists that would exist in between them. This is partly a pragmatic decision because Nix does not provide a way to get the next or previous floating point value.
Based on Haskell library data-interval.
Type
Interval :: { integer :: Bool
, lInc? :: Bool
, min? :: Number
, max? :: Number
, uInc? :: Bool
}
Examples
Right-open interval with inclusive lower bound "a", [a,∞).
{ integer = false; min = a; lInc = true; }
Left-open interval with lower bound "a" and upper bound "b", (a,b].
{ integer = false; min = a; lInc = false; max = b; uInc = true; }
Intervals used throughout the examples, (-∞,∞), (15,∞), [3,3], [2,4] and ø.
whole = { integer = false; }
real = { integer = false; lInc = false; min = 15; }
singleR = { integer = false; lInc = true; min = 3; max = 3; uInc = true; }
integer = { integer = true; lInc = true; min = 2; max = 4; uInc = true; }
empty = { integer = false; lInc = false; min = 0; max = 0; uInc = false; }
lib.interval.hull
The convex hull of two intervals, the smallest interval containing all the values in either interval.
Inputs
i1i2- Intervals to compute the hull over.
Type
hull :: Interval -> Interval -> Interval
Examples
Example
lib.interval.hull usage example
The hull of the unbounded interval is always unbounded.
map (hull whole) [ real singleR integer empty ]
=> [ whole whole whole whole ]
The hull of a real interval and an integer interval is always a real interval.
hull real integer
=> { integer = false; lInc = true; min = 2; } # $[2,∞)$
hull singleR integer
=> # $[2,4]$
{ integer = false; lInc = true; min = 2; max = 4; uInc = true; }
An empty interval has no effect on the bounds of the hull.
map (hull empty) [ whole real singleR integer empty ]
=> [ whole real singleR integer empty ]
lib.interval.intersection
The intersection of two non-overlapping intervals will be empty. Note that
this is not the same as the empty attrset {}, which is not a valid
interval, nor the interval without bounds that includes all numbers,
represented by { integer = true/false; }.
Inputs
i1i2- Intervals to intersect
Type
intersection :: Interval -> Interval -> Interval
Examples
Example
lib.interval.intersection usage example
# The intersection with an empty interval is always empty.
# Note: There is no canonical representation of the empty interval so the
# result may be a different representation of the empty interval.
map (i: isEmpty (intersection empty i)) [ whole real singleR integer empty ]
=> [ true true true true true ]
# The intersection of a real interval and an integer interval is always an
# integer interval.
intersection real integer
=> # $(15,4]$, which is empty.
{ integer = true; lInc = false; min = 15; max = 4; uInc = true; }
intersection singleR integer
=> #$[3,3]$
{ integer = true; lInc = true; min = 3; max = 3; uInc = true; }
# The unbounded interval has no effect on the bounds of the intersection.
map (intersection whole) [ whole real singleR integer empty ]
=> [ whole real singleR integer empty ]
lib.interval.isConnected
If two intervals are connected their convex hull only contains elements that are contained in either interval, unless only one interval is an integer interval.
Inputs
i1i2- Intervals to check for connectivity
Type
isConnected :: Interval -> Interval -> Bool
Examples
Example
lib.interval.isConnected usage example
# An empty interval is connected to any other interval.
map (isConnected empty) [ whole real singleR integer empty ]
=> [ true true true true true ]
# The unbounded interval is connected to any other interval.
map (isConnected whole) [ whole real singleR integer empty ]
=> [ true true true true true ]
# Overlapping intervals, which share at least one value, are trivially
# connected.
# Note: The unbounded interval shares at least one value with any non-empty
# interval.
map (isConnected integer)
[
real
singleR
{ integer = false; lInc = true; min = 4; } # $[ 4,∞)$
{ integer = false; lInc = false; min = 3; } # $( 3,∞)$
{ integer = false; max = 3; uInc = false; } # $(-∞,3)$
{ integer = false; max = 2; uInc = true; } # $(-∞,2]$
# $[1,5]$
{ integer = false; lInc = true; min = 1; max = 5; uInc = true; }
]
=> [ true true true true true true true ]
# If bounds are equal and at least one of them is closed, intervals are
# connected.
map (isConnected integer)
[
{ integer = false; lInc = false; min = 4; } # $( 4,∞)$
{ integer = false; max = 2; uInc = false; } # $(-∞,2)$
]
=> [ true true ]
# For integer intervals, bounds can be different while no values existing
# in between them and therefore the intervals are connected.
map (isConnected integer)
[
{ integer = true; lInc = true; min = 1; } # $[ 5,∞)$
{ integer = true; max = 2; uInc = true; } # $(-∞,1]$
]
=> [ true true ]
lib.interval.isEmpty
No value exists that is both greater than (or equal to if the lower bound is inclusive) the lower bound and less than (or equal to if the upper bound is inclusive) the upper bound.
Inputs
interval- Interval to check for emptiness
Type
isEmpty :: Interval -> Bool
Examples
Example
lib.interval.isEmpty usage example
# Intervals that contain at least one value are not empty.
map isEmpty [ whole real singleR integer ]
=> [ false false false false ]
# There is no canonical representation of the empty interval.
isEmpty [
empty
{ integer = true; lInc = false; min = 3; max = 2; uInc = true; }
{ integer = false; lInc = true; min = 7; max = -5; uInc = true; }
]
=> [ true true true ]
lib.interval.isSubsetOf
One interval is a subset of another if all the values it contains are contained in the other.
Inputs
i1- Subset to check
i2 - Superset to compare to
Type
isSubsetOf :: Interval -> Interval -> Bool
Examples
Example
lib.interval.isSubsetOf usage example
# Empty intervals are trivially subsets of any other intervals.
map (isSubsetOf empty) [ whole real singleR integer empty ]
=> [ true true true true true ]
# Every interval is a subset of the unbounded real interval.
map (i: isSubsetOf i whole) [ whole real singleR integer empty ]
=> [ true true true true true ]
# Note: Real intervals can be subsets of integer intervals, if they only
# contain a single value and that value is an integer, but we
# disregard this case. A real interval is never considered a subset
# of an integer interval.
map (i: isSubsetOf i
{ integer = false; lInc = true; min = 1; max = 5; uInc = true; }
)
[ singleR integer ]
=> [ true true ]
isSubsetOf singleR integer
=> false # Is it a feature or a bug?
lib.interval.overlaps
Intervals overlap if both contain a common value.
Inputs
i1i2- Intervals to check for overlap
Type
overlaps :: Interval -> Interval -> Bool
Examples
Example
lib.interval.overlaps usage example
# Empty intervals never overlap.
map (overlaps empty) [ whole real singleR integer empty ]
=> [ false false false false false ]
# The unbounded real interval overlaps with any non-empty interval.
map (overlaps whole) [ whole real singleR integer ]
=> [ true true true true ]
# Interval overlap does not depend on whether intervals are restricted to
# integers.
overlaps real singleR
=> false
overlaps real integer
=> false
overlaps singleR integer
=> true
lib.interval.show
Convert an interval to a string for display in error messages for example. The information of whether an interval is restricted to integers or not is lost.
Closed bounds are indicated with square brackets [], open bounds with
parentheses (). Unlimited bounds are represented by negative and positive
infinity,-∞ and ∞.
Inputs
interval- Intervals to check for overlap
Type
overlaps :: Interval -> Interval -> Bool
Examples
Example
lib.interval.overlaps usage example
map show [ whole real singleR integer empty ]
=> [
"(-∞,∞)"
"(15,∞)"
"[3,3]"
"[2,4]"
"(0,0)"
]