Feldspar.Range

Bounded integer ranges

Definition

data Range a

A bounded range of values of type a

Constructors

Range

Fields

lowerBound :: a

upperBound :: a

Instances

Eq a => Eq (Range a)

BoundedInt a => Num (Range a)

Implements fromInteger as a singletonRange, and implements correct range propagation for arithmetic operations.

BoundedInt a => Ord (Range a)

Show a => Show (Range a)

BoundedInt a => Lattice (Range a)

(BoundedInt a, BoundedInt b, BoundedInt c) => Num (Range a, Range b, Range c)

type BoundedInt a = (BoundedSuper a, BoundedSuper (UnsignedRep a))

Convenience alias for bounded integers

class (Ord a, Num a, Bounded a, Integral a, FiniteBits a) => BoundedSuper a

Super class to BoundedInt

Instances

(Ord a, Num a, Bounded a, Integral a, FiniteBits a) => BoundedSuper a

type family UnsignedRep a

Type famliy to determine the bit representation of a type

Instances

type UnsignedRep Int = Word

type UnsignedRep Int8 = Word8

type UnsignedRep Int16 = Word16

type UnsignedRep Int32 = Int32

type UnsignedRep Int64 = Word64

type UnsignedRep Word8 = Word8

type UnsignedRep Word16 = Word16

type UnsignedRep Word32 = Word32

type UnsignedRep Word64 = Word64

type UnsignedRep IntN = Word32

type UnsignedRep WordN = Word32

unsigned :: (Integral a, Integral (UnsignedRep a)) => a -> UnsignedRep a

Convert an Integral to its unsigned representation while preserving bit width

handleSign :: forall a b. BoundedInt a => (Range a -> b) -> (Range a -> b) -> Range a -> b

A convenience function for defining range propagation. handleSign propU propS chooses propU for unsigned types and propS for signed types.

showBound :: (Show a, BoundedInt a) => a -> String

Shows a bound.

showRange :: (Show a, BoundedInt a) => Range a -> String

A textual representation of ranges.

mapMonotonic :: (a -> b) -> Range a -> Range b

Requires a monotonic function

mapMonotonic2 :: (a -> b -> c) -> Range a -> Range b -> Range c

Requires a monotonic function

Lattice operations

emptyRange :: BoundedInt a => Range a

The range containing no elements

fullRange :: BoundedInt a => Range a

The range containing all elements of a type

range :: Ord a => a -> a -> Range a

Construct a range

singletonRange :: a -> Range a

The range containing one element

naturalRange :: BoundedInt a => Range a

The range from 0 to the maximum element

positiveRange :: BoundedInt a => Range a

The range from 1 to the maximum element

negativeRange :: forall a. BoundedInt a => Range a

The range from the smallest negative element to -1. Undefined for unsigned types

rangeSize :: BoundedInt a => Range a -> a

The size of a range. Beware that the size may not always be representable for signed types. For instance rangeSize (range minBound maxBound) :: Int gives a nonsense answer.

isEmpty :: BoundedInt a => Range a -> Bool

Checks if the range is empty

isFull :: BoundedInt a => Range a -> Bool

Checks if the range contains all values of the type

isSingleton :: BoundedInt a => Range a -> Bool

Checks is the range contains exactly one element

isSubRangeOf :: BoundedInt a => Range a -> Range a -> Bool

r1 `isSubRangeOf` r2 checks is all the elements in r1 are included in r2

isNatural :: BoundedInt a => Range a -> Bool

Checks whether a range is a sub-range of the natural numbers.

isPositive :: BoundedInt a => Range a -> Bool

Checks whether a range is a sub-range of the positive numbers.

isNegative :: BoundedInt a => Range a -> Bool

Checks whether a range is a sub-range of the negative numbers.

inRange :: BoundedInt a => a -> Range a -> Bool

a `inRange` r checks is a is an element of the range r.

rangeOp :: BoundedInt a => (Range a -> Range a) -> Range a -> Range a

A convenience function for defining range propagation. If the input range is empty then the result is also empty.

rangeOp2 :: BoundedInt a => (Range a -> Range a -> Range a) -> Range a -> Range a -> Range a

See rangeOp.

rangeUnion :: BoundedInt a => Range a -> Range a -> Range a

Union on ranges.

rangeIntersection :: BoundedInt a => Range a -> Range a -> Range a

Intersection on ranges.

disjoint :: BoundedInt a => Range a -> Range a -> Bool

disjoint r1 r2 returns true when r1 and r2 have no elements in common.

rangeByRange :: BoundedInt a => Range a -> Range a -> Range a

rangeByRange ra rb: Computes the range of the following set

{x | a <- ra, b <- rb, x <- Range a b}

rangeGap :: BoundedInt a => Range a -> Range a -> Range a

rangeGap r1 r2 returns a range of all the elements between r1 and r2 including the boundary elements. If r1 and r2 have elements in common the result is an empty range.

rangeLess :: BoundedInt a => Range a -> Range a -> Bool

r1 `rangeLess` r2:

Checks if all elements of r1 are less than all elements of r2.

rangeLessEq :: BoundedInt a => Range a -> Range a -> Bool

r1 `rangeLessEq` r2:

Checks if all elements of r1 are less than or equal to all elements of r2.

Propagation

rangeAbs :: BoundedInt a => Range a -> Range a

Propagates range information through abs.

rangeSignum :: BoundedInt a => Range a -> Range a

Propagates range information through signum.

rangeSignumSigned :: BoundedInt a => Range a -> Range a

Signed case for rangeSignum.

rangeSignumUnsigned :: BoundedInt a => Range a -> Range a

Unsigned case for rangeSignum.

rangeNeg :: BoundedInt a => Range a -> Range a

Propagates range information through negation.

rangeNegUnsigned :: BoundedInt a => Range a -> Range a

Unsigned case for rangeNeg.

rangeNegSigned :: BoundedInt a => Range a -> Range a

Signed case for rangeNeg.

rangeAdd :: BoundedInt a => Range a -> Range a -> Range a

Propagates range information through addition.

rangeAddUnsigned :: BoundedInt a => Range a -> Range a -> Range a

Unsigned case for rangeAdd.

rangeAddSigned :: BoundedInt a => Range a -> Range a -> Range a

Signed case for rangeAdd.

rangeSub :: BoundedInt a => Range a -> Range a -> Range a

Propagates range information through subtraction.

rangeSubUnsigned :: BoundedInt a => Range a -> Range a -> Range a

Unsigned case for rangeSub.

rangeSubSigned :: BoundedInt a => Range a -> Range a -> Range a

subSat :: BoundedInt a => a -> a -> a

Saturating unsigned subtraction

rangeSubSat :: BoundedInt a => Range a -> Range a -> Range a

Range propagation for subSat

rangeMul :: BoundedInt a => Range a -> Range a -> Range a

Propagates range information through multiplication

rangeMulSigned :: forall a. BoundedInt a => Range a -> Range a -> Range a

Signed case for rangeMul.

rangeMulUnsigned :: forall a. BoundedInt a => Range a -> Range a -> Range a

Unsigned case for rangeMul.

bits :: forall b. BoundedInt b => b -> Int

Returns the position of the highest bit set to 1. Counting starts at 1.

rangeExp :: BoundedInt a => Range a -> Range a -> Range a

Propagates range information through exponentiation.

rangeExpUnsigned :: BoundedInt a => Range a -> Range a -> Range a

Unsigned case for rangeExp.

rangeExpSigned :: BoundedInt a => Range a -> Range a -> Range a

Sigend case for rangeExp

maxPlus :: BoundedInt a => a -> a -> a

a `maxPlus` b adds a and b but if the addition overflows then maxBound is returned.

minOrUnsigned :: BoundedInt a => a -> a -> a -> a -> a

Accurate lower bound for .|. on unsigned numbers.

minOr :: BoundedSuper a => a -> a -> a -> a -> a

maxOrUnsigned :: BoundedInt a => a -> a -> a -> a -> a

Accurate upper bound for .|. on unsigned numbers.

maxOr :: BoundedSuper a => a -> a -> a -> a -> a

minAndUnsigned :: BoundedInt a => a -> a -> a -> a -> a

Accurate lower bound for .&. on unsigned numbers

maxAndUnsigned :: BoundedInt a => a -> a -> a -> a -> a

Accurate upper bound for .&. on unsigned numbers

minXorUnsigned :: BoundedInt a => a -> a -> a -> a -> a

Accurate lower bound for xor on unsigned numbers

maxXorUnsigned :: BoundedInt a => a -> a -> a -> a -> a

Accurate upper bound for xor on unsigned numbers

minOrSigned :: BoundedInt a => a -> a -> a -> a -> a

maxOrSigned :: BoundedInt a => a -> a -> a -> a -> a

minAndSigned :: BoundedInt a => a -> a -> a -> a -> a

maxAndSigned :: BoundedInt a => a -> a -> a -> a -> a

rangeOr :: forall a. BoundedInt a => Range a -> Range a -> Range a

Propagates range information through .|..

rangeOrUnsignedAccurate :: BoundedInt a => Range a -> Range a -> Range a

Accurate range propagation through .|. for unsigned types.

rangeOrSignedAccurate :: BoundedInt a => Range a -> Range a -> Range a

rangeAnd :: forall a. BoundedInt a => Range a -> Range a -> Range a

Propagating range information through .&..

rangeAndUnsignedAccurate :: BoundedInt a => Range a -> Range a -> Range a

Accurate range propagation through .&. for unsigned types

rangeAndSignedAccurate :: BoundedInt a => Range a -> Range a -> Range a

rangeXor :: forall a. BoundedInt a => Range a -> Range a -> Range a

Propagating range information through xor.

rangeXorUnsignedAccurate :: BoundedInt a => Range a -> Range a -> Range a

Accurate range propagation through xor for unsigned types

rangeShiftLU :: (BoundedInt a, BoundedInt b) => Range a -> Range b -> Range a

| Propagating range information through shiftLU.

rangeShiftLUUnsigned :: (BoundedInt a, Integral b) => Range a -> Range b -> Range a

Unsigned case for rangeShiftLU.

rangeShiftRU :: (BoundedInt a, BoundedInt b) => Range a -> Range b -> Range a

Propagating range information through shiftRU.

rangeShiftRUUnsigned :: (BoundedInt a, BoundedInt b) => Range a -> Range b -> Range a

Unsigned case for rangeShiftRU.

correctShiftRU :: (Num a, Bits a, BoundedInt b) => a -> b -> a

This is a replacement fror Haskell's shiftR. If we carelessly use Haskell's variant then we will get left shifts for very large shift values.

rangeComplement :: (Bits a, BoundedInt a) => Range a -> Range a

Propagating range information through complement

rangeMax :: BoundedInt a => Range a -> Range a -> Range a

Propagates range information through max.

rangeMin :: BoundedInt a => Range a -> Range a -> Range a

Analogous to rangeMax

rangeMod :: BoundedInt a => Range a -> Range a -> Range a

Propagates range information through mod. Note that we assume Haskell semantics for mod.

rangeRem :: BoundedInt a => Range a -> Range a -> Range a

Propagates range information through rem. Note that we assume Haskell semantics for rem.

predAbs :: (Bounded a, Eq a, Num a, Enum a) => a -> a

rangeDiv :: BoundedInt a => Range a -> Range a -> Range a

Propagates range information through div

rangeDivU :: BoundedInt a => Range a -> Range a -> Range a

Unsigned case for rangeDiv

rangeQuot :: BoundedInt a => Range a -> Range a -> Range a

Propagates range information through quot.

rangeQuotU :: BoundedInt a => Range a -> Range a -> Range a

Unsigned case for rangeQuot.

rangeLessAbs :: BoundedInt a => Range a -> Range a -> Bool

Writing d `rangeLess` abs r doesn't mean what you think it does because r may contain minBound which doesn't have a positive representation. Instead, this function should be used.

absRangeLessAbs :: BoundedInt a => Range a -> Range a -> Bool

Similar to rangeLessAbs but replaces the expression abs d `rangeLess` abs r instead.

Products of ranges

liftR :: (BoundedInt b, BoundedInt c, BoundedInt d) => (forall a. BoundedInt a => Range a) -> (Range b, Range c, Range d)

binopR :: (BoundedInt a, BoundedInt b, BoundedInt c) => (forall d. BoundedInt d => Range d -> Range d -> Range d) -> (Range a, Range b, Range c) -> (Range a, Range b, Range c) -> (Range a, Range b, Range c)

mapR :: (BoundedInt a, BoundedInt b, BoundedInt c) => (forall d. BoundedInt d => Range d -> Range d) -> (Range a, Range b, Range c) -> (Range a, Range b, Range c)

approx :: (BoundedInt a, BoundedInt b, BoundedInt c, BoundedInt d) => (Range a, Range b, Range c) -> Range d