Math.Combinatorics.Species.Util.Interval

A simple implementation of intervals of natural numbers, for use in tracking the possible sizes of structures of a species. For example, the species x + x^2 + x^3 will correspond to the interval [1,3].

The NatO type

data NatO

NatO is an explicit representation of the co-inductive Nat type which admits an infinite value, omega. Our intuition for the semantics of NatO comes from thinking of it as an efficient representation of lazy unary natural numbers, except that we can actually test for omega in finite time.

Instances

Eq NatO

Methods

(==) :: NatO -> NatO -> Bool

(/=) :: NatO -> NatO -> Bool

Ord NatO

Methods

compare :: NatO -> NatO -> Ordering

(<) :: NatO -> NatO -> Bool

(<=) :: NatO -> NatO -> Bool

(>) :: NatO -> NatO -> Bool

(>=) :: NatO -> NatO -> Bool

max :: NatO -> NatO -> NatO

min :: NatO -> NatO -> NatO

Show NatO

Methods

showsPrec :: Int -> NatO -> ShowS

show :: NatO -> String

showList :: [NatO] -> ShowS

C NatO

In fact, NatO forms a semiring, with 1 as the multiplicative unit.

Methods

(*) :: NatO -> NatO -> NatO

one :: NatO

fromInteger :: Integer -> NatO

(^) :: NatO -> Integer -> NatO

C NatO

NatO forms an additive monoid, with zero as the identity. This doesn't quite fit since Additive.C is supposed to be for groups, so the negate method just throws an error. But we'll never use it and NatO won't be directly exposed to users of the species library anyway.

Methods

zero :: NatO

(+) :: NatO -> NatO -> NatO

(-) :: NatO -> NatO -> NatO

negate :: NatO -> NatO

omega :: NatO

The infinite NatO value.

natO :: (Integer -> a) -> a -> NatO -> a

Eliminator for NatO values.

The Interval type

data Interval

An Interval is a closed range of consecutive integers. Both endpoints are represented as NatO values. For example, [2,5] represents the values 2,3,4,5; [2,omega] represents all integers greater than 1; intervals where the first endpoint is greater than the second also represent the empty interval.

Instances

Show Interval

Methods

showsPrec :: Int -> Interval -> ShowS

show :: Interval -> String

showList :: [Interval] -> ShowS

C Interval

Intervals form a semiring, with the multiplication operation being pointwise multiplication of their endpoints.

Methods

(*) :: Interval -> Interval -> Interval

one :: Interval

fromInteger :: Integer -> Interval

(^) :: Interval -> Integer -> Interval

C Interval

Intervals can be added by adding their endpoints pointwise.

Methods

zero :: Interval

(+) :: Interval -> Interval -> Interval

(-) :: Interval -> Interval -> Interval

negate :: Interval -> Interval

iLow :: Interval -> NatO

Get the lower endpoint of an Interval

iHigh :: Interval -> NatO

Get the upper endpoint of an Interval

Interval operations

decrI :: Interval -> Interval

Decrement both endpoints of an interval.

union :: Interval -> Interval -> Interval

The union of two intervals is the smallest interval containing both.

intersect :: Interval -> Interval -> Interval

The intersection of two intervals is the largest interval contained in both.

elem :: Integer -> Interval -> Bool

Test a given integer for interval membership.

toList :: Interval -> [Integer]

Convert an interval to a list of Integers.

Constructing intervals

natsI :: Interval

The range [0,omega] containing all natural numbers.

fromI :: NatO -> Interval

Construct an open range [n,omega].

emptyI :: Interval

The empty interval.

omegaI :: Interval

The interval which contains only omega.