This is an alternative site for discovering Elm packages.
You may be looking for the
official Elm package site
instead.

A representation of numeric intervals (also known as *ranges*.)

type Interval
= Bounded Bound Bound
| Degenerate Float
| Empty

An interval over the reals. May be over either the Ordinary Reals `(-∞, +∞)`

or
the Extended Reals `[-∞, +∞]`

.
`Bounded x y`

will always satisfy `x < y`

. (`x == y`

is either degenerate or empty)

Opaque type.

type Bound
= Inclusive Float
| Exclusive Float

Represents an upper or lower, closed or open endpoint of an Interval.
This encompasses the "endpoints" of unbounded intervals when the bound value
is either of the `Infinity`

values in the floating point spec.

Opaque type.

`interval`

is the primary constructor; the others are just for convenience.

interval : Bound -> Bound -> Interval

Constructs an `Interval`

from two Bounds.

degenerate : Float -> Interval

A degenerate Interval.

empty : Interval

An empty Interval.

leftBounded : Bound -> Interval

Convenience function for a left-bounded Interval (from some n to +∞)

rightBounded : Bound -> Interval

Convenience function for a right-bounded Interval (from -∞ to some n)

unbounded : Interval

An unbounded Interval over the Extended Reals. `[-∞, +∞]`

excludes : Float -> Bound

An exclusive endpoint of an interval.

includes : Float -> Bound

An inclusive endpoint of an interval.

hull : Interval -> Interval -> Interval

The convex hull of two intervals. This is similar to union in that it includes all the points of the component intervals, and for non-overlapping intervals, the points between them.

intersection : Interval -> Interval -> Interval

The intersection of two intervals. If the intervals overlap, this is the common part. If not, this is the empty interval.

intervalToString : Interval -> String

Return a String representation of an Interval.

interior : Interval -> Interval

Returns the largest open interval contained within a.

```
-- `interior([x, y]) == (x, y)`
interior (interval (includes 0) (includes 2)) == interval (excludes 0) (excludes 2)
```

closure : Interval -> Interval

Returns the smallest closed interval containing a.

```
-- `closure((x, y)) == [x, y]`
interior (interval (excludes 0) (excludes 2)) == interval (includes 0) (includes 2)
```

subtract : Interval -> Interval -> List Interval

Subtract interval `b`

from interval `a`

, returning a list of the parts of
`a`

that did not intersect with `b`

.

E.g.:

- [1, 3) - (1, 2] = [ {1}, (2, 3) ]

upperBoundValue : Interval -> Maybe Float

Extract the value of the upper bound of an Interval.

lowerBoundValue : Interval -> Maybe Float

Extract the value of the lower bound of an Interval.

adjoins : Interval -> Interval -> Bool

Are these two intervals adjoins? I.e., do they share an upper-lower or lower-upper bound, exactly one of which is closed, and do not intersect each other?

```
let
a = interval (includes 1) (excludes 3) -- [1, 3)
b = interval (includes 2) (includes 4) -- [3, 4]
c = interval (includes 3) (includes 4) -- (3, 4]
d = interval (includes 3) (includes 4) -- [2, 3]
in
[ adjoins a b = True
, adjoins a c = False
, adjoins a d = False
]
```

intersects : Interval -> Interval -> Bool

Do these two intervals intersect?

```
let
a = interval (includes 1) (excludes 3)
b = interval (includes 2) (includes 4)
c = interval (includes 3) (includes 4)
in
[ intersects a b = True
, intersects a c = False
]
```

intersectsPoint : Interval -> Float -> Bool

Does this interval contain the given point?

```
let
a = interval (includes 1) (excludes 3)
in
[ intersectsPoint a 0 = False
, intersectsPoint a 1 = True
, intersectsPoint a 3 = False
]
```

isBounded : Interval -> Bool

Does this interval have finite bounds?

isDegenerate : Interval -> Bool

Is this a degenerate (point-valued) interval?

isEmpty : Interval -> Bool

Is this an empty interval?

isLeftBounded : Interval -> Bool

Does this interval have a finite lower bound, and an infinite upper bound?

isRightBounded : Interval -> Bool

Does this interval have a finite upper bound, and an infinite lower bound?

isLeftOpen : Interval -> Bool

Is the lower bound of this interval open?

isRightOpen : Interval -> Bool

Is the upper bound of this interval open?

```
module Interval
exposing
( adjoins
, Bound
, closure
, degenerate
, empty
, excludes
, hull
, includes
, interior
, intersection
, intersects
, intersectsPoint
, Interval
, interval
, intervalToString
, isBounded
, isDegenerate
, isEmpty
, isLeftBounded
, isLeftOpen
, isRightBounded
, isRightOpen
, leftBounded
, lowerBoundValue
, rightBounded
, subtract
, unbounded
, upperBoundValue
)
{-| A representation of numeric intervals (also known as *ranges*.)
# Types
@docs Interval
@docs Bound
# Constructors
`interval` is the primary constructor; the others are just for convenience.
@docs interval
@docs degenerate
@docs empty
@docs leftBounded
@docs rightBounded
@docs unbounded
# Endpoint (Bound) constructors
@docs excludes
@docs includes
# Operations on Intervals
@docs hull
@docs intersection
@docs intervalToString
@docs interior
@docs closure
@docs subtract
@docs upperBoundValue
@docs lowerBoundValue
# Tests on Intervals
@docs adjoins
@docs intersects
@docs intersectsPoint
@docs isBounded
@docs isDegenerate
@docs isEmpty
@docs isLeftBounded
@docs isRightBounded
@docs isLeftOpen
@docs isRightOpen
# Related reading
- [Interval](<https://en.wikipedia.org/wiki/Interval_(mathematics)>
- [Interval tree](https://en.wikipedia.org/wiki/Interval_tree)
- [Allen's interval algebra](https://en.wikipedia.org/wiki/Allen%27s_interval_algebra)
-}
{-| An interval over the reals. May be over either the Ordinary Reals `(-∞, +∞)` or
the Extended Reals `[-∞, +∞]`.
`Bounded x y` will always satisfy `x < y`. (`x == y` is either degenerate or empty)
Opaque type.
-}
type Interval
= Bounded Bound Bound
| Degenerate Float
| Empty
{-| Represents an upper or lower, closed or open endpoint of an Interval.
This encompasses the "endpoints" of unbounded intervals when the bound value
is either of the `Infinity` values in the floating point spec.
Opaque type.
-}
type Bound
= Inclusive Float
| Exclusive Float
{-| An inclusive endpoint of an interval.
-}
includes : Float -> Bound
includes n =
Inclusive n
{-| An exclusive endpoint of an interval.
-}
excludes : Float -> Bound
excludes n =
Exclusive n
boundValue : Bound -> Float
boundValue b =
case b of
Inclusive n ->
n
Exclusive n ->
n
{-| An empty Interval.
-}
empty : Interval
empty =
Empty
{-| A degenerate Interval.
-}
degenerate : Float -> Interval
degenerate n =
Degenerate n
{-| An unbounded Interval over the [Extended Reals.] `[-∞, +∞]`
[Extended Reals.]: https://en.wikipedia.org/wiki/Interval_(mathematics)#Infinite_endpoints
-}
unbounded : Interval
unbounded =
interval (Inclusive <| -1 / 0) (Inclusive <| 1 / 0)
{-| Convenience function for a right-bounded Interval (from -∞ to some n)
-}
rightBounded : Bound -> Interval
rightBounded b =
interval (Inclusive <| -1 / 0) b
{-| Convenience function for a left-bounded Interval (from some n to +∞)
-}
leftBounded : Bound -> Interval
leftBounded b =
interval b (Inclusive <| 1 / 0)
{-| Constructs an `Interval` from two Bounds.
-}
interval : Bound -> Bound -> Interval
interval i j =
let
t =
boundValue i
u =
boundValue j
in
case (t == u) of
True ->
case ( i, j ) of
( Inclusive _, Inclusive _ ) ->
Degenerate t
( _, _ ) ->
Empty
False ->
case (t < u) of
True ->
Bounded i j
False ->
Empty
{-| Return a String representation of an Interval.
-}
intervalToString : Interval -> String
intervalToString interval =
case interval of
Empty ->
"{}"
Degenerate n ->
"{" ++ toString n ++ "}"
Bounded x y ->
let
left =
case x of
Exclusive n ->
"(" ++ toString n
Inclusive n ->
"[" ++ toString n
right =
case y of
Exclusive n ->
toString n ++ ")"
Inclusive n ->
toString n ++ "]"
in
left ++ ", " ++ right
{-| Return the outer minimum of two Bounds.
minOuterBound (includes 1) (excludes 1) == (includes 1)
minOuterBound (includes 1) (excludes 0) == (excludes 0)
-}
minOuterBound : Bound -> Bound -> Bound
minOuterBound a b =
let
x =
boundValue a
y =
boundValue b
in
case (x < y) of
True ->
a
False ->
case (y < x) of
True ->
b
False ->
-- x == y
andInclusives a b
{-| Return the outer maximum of two Bounds.
maxOuterBound (includes 1) (excludes 1) == (includes 1)
maxOuterBound (includes 1) (excludes 2) == (excludes 2)
-}
maxOuterBound : Bound -> Bound -> Bound
maxOuterBound a b =
let
x =
boundValue a
y =
boundValue b
in
case (x < y) of
True ->
b
False ->
case (y < x) of
True ->
a
False ->
-- x == y
andInclusives a b
{-| Return the inner minimum of two Bounds.
minOuterBound (includes 1) (excludes 1) == (excludes 1)
minOuterBound (includes 0) (excludes 1) == (includes 0)
-}
minInnerBound : Bound -> Bound -> Bound
minInnerBound a b =
let
x =
boundValue a
y =
boundValue b
in
case (x < y) of
True ->
a
False ->
case (y < x) of
True ->
b
False ->
-- x == y
andExclusives a b
{-| Return the inner maximum of two Bounds.
maxInnerBound (includes 1) (excludes 1) == (excludes 1)
maxInnerBound (includes 0) (excludes 1) == (includes 0)
-}
maxInnerBound : Bound -> Bound -> Bound
maxInnerBound a b =
let
x =
boundValue a
y =
boundValue b
in
case (x < y) of
True ->
b
False ->
case (y < x) of
True ->
a
False ->
-- x == y
andExclusives a b
{-| If either Bound is Exclusive, return that. Else, both are Inclusive; return the first.
-}
andInclusives : Bound -> Bound -> Bound
andInclusives a b =
case ( a, b ) of
( Inclusive _, Inclusive _ ) ->
a
( Exclusive _, _ ) ->
a
( _, Exclusive _ ) ->
b
{-| If either Bound is Inclusive, return that. Else, both are Exclusive; return the first.
-}
andExclusives : Bound -> Bound -> Bound
andExclusives a b =
case ( a, b ) of
( Exclusive _, Exclusive _ ) ->
a
( Inclusive _, _ ) ->
a
( _, Inclusive _ ) ->
b
{-| The intersection of two intervals. If the intervals overlap, this is the common part. If not, this is the empty interval.
-}
intersection : Interval -> Interval -> Interval
intersection a b =
case ( a, b ) of
( Empty, _ ) ->
Empty
( _, Empty ) ->
Empty
( Degenerate x, Degenerate y ) ->
case (x == y) of
True ->
Degenerate x
False ->
Empty
( Degenerate w, Bounded y z ) ->
interval
(maxOuterBound (includes w) y)
(minOuterBound (includes w) z)
( Bounded w x, Degenerate y ) ->
interval
(maxOuterBound w (includes y))
(minOuterBound x (includes y))
( Bounded w x, Bounded y z ) ->
interval
(maxOuterBound w y)
(minOuterBound x z)
{-| The convex hull of two intervals. This is similar to union in that
it includes all the points of the component intervals, and for
non-overlapping intervals, the points between them.
-}
hull : Interval -> Interval -> Interval
hull a b =
case ( a, b ) of
( Empty, _ ) ->
b
( _, Empty ) ->
a
( Degenerate x, Degenerate y ) ->
interval (includes <| min x y) (includes <| max x y)
( Degenerate w, Bounded y z ) ->
interval
(minInnerBound (includes w) y)
(maxInnerBound (includes w) z)
( Bounded w x, Degenerate y ) ->
interval
(minInnerBound w (includes y))
(maxInnerBound x (includes y))
( Bounded w x, Bounded y z ) ->
interval
(minInnerBound w y)
(maxInnerBound x z)
{-| Extract the value of the lower bound of an Interval.
-}
lowerBoundValue : Interval -> Maybe Float
lowerBoundValue a =
case a of
Empty ->
Nothing
Degenerate n ->
Just n
Bounded l u ->
Just <| boundValue l
{-| Extract the value of the upper bound of an Interval.
-}
upperBoundValue : Interval -> Maybe Float
upperBoundValue a =
case a of
Empty ->
Nothing
Degenerate n ->
Just n
Bounded l u ->
Just <| boundValue l
{-| Do these two intervals intersect?
let
a = interval (includes 1) (excludes 3)
b = interval (includes 2) (includes 4)
c = interval (includes 3) (includes 4)
in
[ intersects a b = True
, intersects a c = False
]
-}
intersects : Interval -> Interval -> Bool
intersects a b =
case ( a, b ) of
( Empty, _ ) ->
False
( _, Empty ) ->
False
( Degenerate x, Degenerate y ) ->
x == y
( Degenerate w, Bounded y z ) ->
(intersection a b) == a
( Bounded w x, Degenerate y ) ->
(intersection a b) == b
( Bounded w x, Bounded y z ) ->
(intersection a b) /= empty
{-| Are these two intervals adjoins? I.e., do they share an upper-lower or
lower-upper bound, exactly one of which is closed, and do not intersect each other?
let
a = interval (includes 1) (excludes 3) -- [1, 3)
b = interval (includes 2) (includes 4) -- [3, 4]
c = interval (includes 3) (includes 4) -- (3, 4]
d = interval (includes 3) (includes 4) -- [2, 3]
in
[ adjoins a b = True
, adjoins a c = False
, adjoins a d = False
]
-}
adjoins : Interval -> Interval -> Bool
adjoins a b =
case ( a, b ) of
( Empty, _ ) ->
False
( _, Empty ) ->
False
( Degenerate x, Degenerate y ) ->
False
( Degenerate w, Bounded y z ) ->
(isOpenBound y && w == boundValue y) || (isOpenBound z && w == boundValue z)
( Bounded w x, Degenerate y ) ->
(isOpenBound w && y == boundValue w) || (isOpenBound x && y == boundValue x)
( Bounded w x, Bounded y z ) ->
let
( wOpen, xOpen, yOpen, zOpen ) =
( isOpenBound w, isOpenBound x, isOpenBound y, isOpenBound z )
upperLowerMatch =
(xOpen |> xor yOpen)
&& (boundValue x == boundValue y)
lowerUpperMatch =
(wOpen |> xor zOpen)
&& (boundValue w == boundValue z)
in
not (a |> intersects b) && (upperLowerMatch || lowerUpperMatch)
{-| Does this interval contain the given point?
let
a = interval (includes 1) (excludes 3)
in
[ intersectsPoint a 0 = False
, intersectsPoint a 1 = True
, intersectsPoint a 3 = False
]
-}
intersectsPoint : Interval -> Float -> Bool
intersectsPoint a n =
case a of
Empty ->
False
Degenerate x ->
x == n
Bounded w x ->
intersection a (degenerate n) == (degenerate n)
{-| Does this interval have finite bounds?
-}
isBounded : Interval -> Bool
isBounded a =
case a of
Empty ->
False
Degenerate x ->
not <| isInfinite x
Bounded x y ->
not <| isInfinite (boundValue x) || isInfinite (boundValue y)
{-| Is this a degenerate (point-valued) interval?
-}
isDegenerate : Interval -> Bool
isDegenerate a =
case a of
Degenerate _ ->
True
Empty ->
False
Bounded _ _ ->
False
{-| Is this an empty interval?
-}
isEmpty : Interval -> Bool
isEmpty a =
case a of
Empty ->
True
Degenerate _ ->
False
Bounded _ _ ->
False
{-| Does this interval have a finite lower bound, and an infinite upper bound?
-}
isLeftBounded : Interval -> Bool
isLeftBounded a =
case a of
Empty ->
False
Degenerate x ->
False
Bounded x y ->
(not <| isInfinite (boundValue x)) && isInfinite (boundValue y)
{-| Does this interval have a finite upper bound, and an infinite lower bound?
-}
isRightBounded : Interval -> Bool
isRightBounded a =
case a of
Empty ->
False
Degenerate x ->
False
Bounded x y ->
(not <| isInfinite (boundValue y)) && isInfinite (boundValue x)
{-| Is this interval unbounded?
-}
isUnbounded : Interval -> Bool
isUnbounded a =
case a of
Empty ->
False
Degenerate _ ->
False
Bounded lower upper ->
(isInfinite <| boundValue lower) && (isInfinite <| boundValue upper)
isOpenBound : Bound -> Bool
isOpenBound b =
case b of
Inclusive _ ->
False
Exclusive _ ->
True
{-| Is the lower bound of this interval open?
-}
isLeftOpen : Interval -> Bool
isLeftOpen a =
case a of
Empty ->
False
Degenerate _ ->
False
Bounded lower upper ->
isOpenBound lower
{-| Is the upper bound of this interval open?
-}
isRightOpen : Interval -> Bool
isRightOpen a =
case a of
Empty ->
False
Degenerate _ ->
False
Bounded lower upper ->
isOpenBound upper
{-| Returns the largest open interval contained within a.
-- `interior([x, y]) == (x, y)`
interior (interval (includes 0) (includes 2)) == interval (excludes 0) (excludes 2)
-}
interior : Interval -> Interval
interior a =
case a of
Empty ->
empty
Degenerate _ ->
empty
Bounded x y ->
let
t =
boundValue x
u =
boundValue y
in
interval (excludes t) (excludes u)
{-| Returns the smallest closed interval containing a.
-- `closure((x, y)) == [x, y]`
interior (interval (excludes 0) (excludes 2)) == interval (includes 0) (includes 2)
-}
closure : Interval -> Interval
closure a =
case a of
Empty ->
empty
Degenerate _ ->
a
Bounded x y ->
let
t =
boundValue x
u =
boundValue y
in
interval (includes t) (includes u)
{-| Subtract interval `b` from interval `a`, returning a list of the parts of
`a` that did not intersect with `b`.
E.g.:
- [1, 3) - (1, 2] = [ {1}, (2, 3) ]
-}
subtract : Interval -> Interval -> List Interval
subtract a b =
if (a |> intersects b) then
case ( a, b ) of
( _, Empty ) ->
[ a ]
( Empty, _ ) ->
[]
( Degenerate w, _ ) ->
[]
( Bounded w x, Degenerate y ) ->
-- ?w, x? - {y} = [ ?w, y), (y, x? ]
[ interval w (excludes y)
, interval (excludes y) x
]
( Bounded w x, Bounded y z ) ->
let
left =
if (minInnerBound w y == w && w /= y) then
[ interval w (invertBound y) ]
else
[]
right =
if (maxInnerBound x z == x && x /= z) then
[ interval (invertBound z) x ]
else
[]
in
List.append left right
else
[ a ]
{-| Hold the bound value steady, but invert the open/closed property.
-}
invertBound : Bound -> Bound
invertBound b =
case b of
Inclusive n ->
Exclusive n
Exclusive n ->
Inclusive n
```