feldspar-language-0.7: A functional embedded language for DSP and parallelism

Safe HaskellSafe-Inferred
LanguageHaskell2010

Feldspar.Range

Contents

Description

Bounded integer ranges

Synopsis

Definition

data Range a Source

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)) Source

Convenience alias for bounded integers

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

Super class to BoundedInt

Instances

type family UnsignedRep a Source

Type famliy to determine the bit representation of a type

Instances

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

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 Source

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 Source

Shows a bound.

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

A textual representation of ranges.

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

Requires a monotonic function

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

Requires a monotonic function

Lattice operations

emptyRange :: BoundedInt a => Range a Source

The range containing no elements

fullRange :: BoundedInt a => Range a Source

The range containing all elements of a type

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

Construct a range

singletonRange :: a -> Range a Source

The range containing one element

naturalRange :: BoundedInt a => Range a Source

The range from 0 to the maximum element

positiveRange :: BoundedInt a => Range a Source

The range from 1 to the maximum element

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

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

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

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 Source

Checks if the range is empty

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

Checks if the range contains all values of the type

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

Checks is the range contains exactly one element

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

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

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

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

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

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

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

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

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

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

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

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 Source

See rangeOp.

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

Union on ranges.

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

Intersection on ranges.

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

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

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

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 Source

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 Source

r1 `rangeLess` r2:

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

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

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 Source

Propagates range information through abs.

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

Propagates range information through signum.

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

Signed case for rangeSignum.

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

Unsigned case for rangeSignum.

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

Propagates range information through negation.

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

Unsigned case for rangeNeg.

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

Signed case for rangeNeg.

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

Propagates range information through addition.

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

Unsigned case for rangeAdd.

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

Signed case for rangeAdd.

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

Propagates range information through subtraction.

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

Unsigned case for rangeSub.

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

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

Saturating unsigned subtraction

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

Range propagation for subSat

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

Propagates range information through multiplication

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

Signed case for rangeMul.

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

Unsigned case for rangeMul.

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

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

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

Propagates range information through exponentiation.

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

Unsigned case for rangeExp.

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

Sigend case for rangeExp

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

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

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

Accurate lower bound for .|. on unsigned numbers.

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

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

Accurate upper bound for .|. on unsigned numbers.

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

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

Accurate lower bound for .&. on unsigned numbers

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

Accurate upper bound for .&. on unsigned numbers

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

Accurate lower bound for xor on unsigned numbers

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

Accurate upper bound for xor on unsigned numbers

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

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

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

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

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

Propagates range information through .|..

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

Accurate range propagation through .|. for unsigned types.

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

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

Propagating range information through .&..

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

Accurate range propagation through .&. for unsigned types

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

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

Propagating range information through xor.

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

Accurate range propagation through xor for unsigned types

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

| Propagating range information through shiftLU.

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

Unsigned case for rangeShiftLU.

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

Propagating range information through shiftRU.

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

Unsigned case for rangeShiftRU.

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

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 Source

Propagating range information through complement

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

Propagates range information through max.

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

Analogous to rangeMax

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

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

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

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

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

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

Propagates range information through div

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

Unsigned case for rangeDiv

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

Propagates range information through quot.

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

Unsigned case for rangeQuot.

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

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 Source

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) Source

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) Source

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) Source

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