species-0.3.2.3: Computational combinatorial species

Stability experimental byorgey@cis.upenn.edu None

Math.Combinatorics.Species.Util.Interval

Contents

Description

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].

Synopsis

# The `NatO` type

data NatO Source

`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 Ord NatO Show NatO C NatO In fact, `NatO` forms a semiring, with 1 as the multiplicative unit. 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.

The infinite `NatO` value.

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

Eliminator for `NatO` values.

# The `Interval` type

data Interval Source

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 C Interval Intervals form a semiring, with the multiplication operation being pointwise multiplication of their endpoints. C Interval Intervals can be added by adding their endpoints pointwise.

Get the lower endpoint of an `Interval`

Get the upper endpoint of an `Interval`

# Interval operations

Decrement both endpoints of an interval.

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

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

Test a given integer for interval membership.

toList :: Interval -> [Integer]Source

Convert an interval to a list of Integers.

# Constructing intervals

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

Construct an open range [n,omega].

The empty interval.

The interval which contains only omega.