HMath.Discrete¶
Module index · Numerical conventions
Description
Finite-width bits, relations and propositional logic. Widths are explicit; zero has both leading- and trailing-zero count equal to its width. Boolean matrices use the OR/AND semiring. Logic enumerations are bounded to 12 inputs.
On this page¶
| API | Purpose |
|---|---|
| MultiSet | Finite multiset with exact nonnegative multiplicities. |
| multiset | Construct a finite multiset by counting equal ordered values with exact nonnegative Integer multiplicities. |
| multiplicity | Given value then multiset, return its Integer frequency, or zero when absent. |
| multisetEntries | Return (value,positive multiplicity) pairs in ascending value order. |
| multisetInsert | Given value then multiset, increment its multiplicity by one and return a new multiset. |
| multisetDelete | Given value then multiset, remove one occurrence, deleting its entry at zero. |
| multisetUnion | Add multiplicities of two multisets, retaining all distinct values. |
| multisetIntersection | Return shared values with minimum of the two multiplicities. |
| multisetDifference | Subtract right multiplicities from left, truncating at zero and removing empty entries. |
| BitSet | Opaque arbitrary-size dynamic bitset; bits outside its width are zero. |
| bitSet | Given width in [0,1048576] then nonnegative Integer less than 2^width, construct an opaque bitset. |
| bitWidth | Return declared number of bits, including leading zeros. |
| bitValue | Return unsigned Integer value of all bits within the declared width. |
| bitMember | Given bitset then zero-based bit index, return membership. |
| bitInsert | Given bitset then valid bit index, return a new bitset with that bit set. |
| bitDelete | Given bitset then valid bit index, return a new bitset with that bit cleared. |
| bitUnion | Return bitwise OR of equal-width bitsets. |
| bitIntersection | Return bitwise AND of equal-width bitsets; mismatched widths fail. |
| bitDifference | Return left bits with right bits cleared, requiring equal widths. |
| resizeBitSet | Shrinking explicitly discards high bits. |
| populationCount | Count set bits within declared width, returning Int. |
| leadingZeros | Count high-end zero bits within declared width. |
| trailingZeros | Count low-end zero bits; an all-zero bitset returns its declared width. |
| rotateBits | Given signed rotation count then bitset, rotate left modulo width (negative counts rotate right). |
| reverseBits | Reverse exactly the declared width of bits, preserving width and leading/trailing zero positions. |
| grayEncode | Return width-preserving reflected Gray code v xor (v shifted right one). |
| grayDecode | Decode reflected Gray bits to the corresponding width-preserving binary value. |
| hammingDistance | Count differing bit positions between equal-width bitsets. |
| setUnion | Treat lists as finite sets and return their sorted unique union; input order and multiplicity are discarded. |
| setIntersection | Return sorted unique values present in both input lists. |
| setDifference | Return sorted unique left values absent from the right list. |
| symmetricDifference | Return sorted unique values present in exactly one input list. |
| transitiveClosure | Warshall closure. |
| equivalenceClosure | Given square Bool relation matrix, add reflexivity and symmetry then compute transitive closure. |
| isEquivalence | Return whether a bounded square Bool relation is already reflexive, symmetric and transitive. |
| booleanMultiply | Multiply compatible square Bool relation matrices over OR/AND, representing relational composition. |
| Prop | Boolean proposition tree. |
| Literal | Declaration and type contract below. |
| Variable | Declaration and type contract below. |
| Not | Declaration and type contract below. |
| And | Declaration and type contract below. |
| Or | Declaration and type contract below. |
| Xor | Declaration and type contract below. |
| Implies | Declaration and type contract below. |
| Iff | Declaration and type contract below. |
| evaluateProp | Given variable Bool assignment list then proposition, evaluate literalsvariablesconnectives. |
| truthTable | Assignments in binary order, variable zero the least-significant bit. |
| Implicant | Value bits and a don't-care mask. |
| Implicant | Declaration and type contract below. |
| implicantValue | Fixed bit values of a Boolean implicant; positions masked by implicantMask are ignored. |
| implicantMask | Bit mask whose set bits denote don't-care positions in an implicant. |
| quineMcCluskey | Exact Quine--McCluskey prime generation followed by branch-and-bound cover selection. |
| implicantCovers | Given implicant then Integer minterm, compare bits where implicantMask is clear. |
Documentation
MultiSet
Finite multiset with exact nonnegative multiplicities. Union adds multiplicities; intersection takes minima and difference truncates at zero.
multiset
multiset :: Ord a => [a] -> MultiSet a Source #
Construct a finite multiset by counting equal ordered values with exact nonnegative Integer multiplicities.
multiplicity
multiplicity :: Ord a => a -> MultiSet a -> Integer Source #
Given value then multiset, return its Integer frequency, or zero when absent.
multisetEntries
multisetEntries :: MultiSet a -> [(a, Integer)] Source #
Return (value,positive multiplicity) pairs in ascending value order.
multisetInsert
multisetInsert :: Ord a => a -> MultiSet a -> MultiSet a Source #
Given value then multiset, increment its multiplicity by one and return a new multiset.
multisetDelete
multisetDelete :: Ord a => a -> MultiSet a -> MultiSet a Source #
Given value then multiset, remove one occurrence, deleting its entry at zero. Absent values are a no-op.
multisetUnion
multisetUnion :: Ord a => MultiSet a -> MultiSet a -> MultiSet a Source #
Add multiplicities of two multisets, retaining all distinct values. This is multiset sum rather than maximum-multiplicity union.
multisetIntersection
multisetIntersection :: Ord a => MultiSet a -> MultiSet a -> MultiSet a Source #
Return shared values with minimum of the two multiplicities.
multisetDifference
multisetDifference :: Ord a => MultiSet a -> MultiSet a -> MultiSet a Source #
Subtract right multiplicities from left, truncating at zero and removing empty entries.
BitSet
Opaque arbitrary-size dynamic bitset; bits outside its width are zero.
bitSet
bitSet :: Int -> Integer -> Either MathError BitSet Source #
Given width in [0,1048576] then nonnegative Integer less than 2^width, construct an opaque bitset. Invalid width/value fails; bit zero is least significant.
bitValue
bitValue :: BitSet -> Integer Source #
Return unsigned Integer value of all bits within the declared width.
bitMember
bitMember :: BitSet -> Int -> Either MathError Bool Source #
Given bitset then zero-based bit index, return membership. Out-of-width or negative indices return Left InvalidArgument.
bitInsert
bitInsert :: BitSet -> Int -> Either MathError BitSet Source #
Given bitset then valid bit index, return a new bitset with that bit set. Invalid index fails.
bitDelete
bitDelete :: BitSet -> Int -> Either MathError BitSet Source #
Given bitset then valid bit index, return a new bitset with that bit cleared. Invalid index fails.
bitUnion
bitUnion :: BitSet -> BitSet -> Either MathError BitSet Source #
Return bitwise OR of equal-width bitsets. Different widths fail; no implicit resize occurs.
bitIntersection
bitIntersection :: BitSet -> BitSet -> Either MathError BitSet Source #
Return bitwise AND of equal-width bitsets; mismatched widths fail.
bitDifference
bitDifference :: BitSet -> BitSet -> Either MathError BitSet Source #
Return left bits with right bits cleared, requiring equal widths. Width mismatch fails.
resizeBitSet
resizeBitSet :: Int -> BitSet -> Either MathError BitSet Source #
Shrinking explicitly discards high bits.
populationCount
populationCount :: BitSet -> Int Source #
Count set bits within declared width, returning Int.
leadingZeros
leadingZeros :: BitSet -> Int Source #
Count high-end zero bits within declared width. All-zero bitset returns its full width.
trailingZeros
trailingZeros :: BitSet -> Int Source #
Count low-end zero bits; an all-zero bitset returns its declared width.
rotateBits
rotateBits :: Int -> BitSet -> BitSet Source #
Given signed rotation count then bitset, rotate left modulo width (negative counts rotate right). Width-zero input is unchanged.
reverseBits
reverseBits :: BitSet -> BitSet Source #
Reverse exactly the declared width of bits, preserving width and leading/trailing zero positions.
grayEncode
grayEncode :: BitSet -> BitSet Source #
Return width-preserving reflected Gray code v xor (v shifted right one).
grayDecode
grayDecode :: BitSet -> BitSet Source #
Decode reflected Gray bits to the corresponding width-preserving binary value.
hammingDistance
hammingDistance :: BitSet -> BitSet -> Either MathError Int Source #
Count differing bit positions between equal-width bitsets. Different widths return Left InvalidArgument.
setUnion
setUnion :: Ord a => [a] -> [a] -> [a] Source #
Treat lists as finite sets and return their sorted unique union; input order and multiplicity are discarded.
setIntersection
setIntersection :: Ord a => [a] -> [a] -> [a] Source #
Return sorted unique values present in both input lists.
setDifference
setDifference :: Ord a => [a] -> [a] -> [a] Source #
Return sorted unique left values absent from the right list.
symmetricDifference
symmetricDifference :: Ord a => [a] -> [a] -> [a] Source #
Return sorted unique values present in exactly one input list.
transitiveClosure
transitiveClosure :: [[Bool]] -> Either MathError [[Bool]] Source #
Warshall closure. Paths must have positive length; use
equivalenceClosure when a reflexive closure is wanted.
equivalenceClosure
equivalenceClosure :: [[Bool]] -> Either MathError [[Bool]] Source #
Given square Bool relation matrix, add reflexivity and symmetry then compute transitive closure. Reject nonsquare or oversized (>512) relations.
isEquivalence
isEquivalence :: [[Bool]] -> Either MathError Bool Source #
Return whether a bounded square Bool relation is already reflexive, symmetric and transitive. Invalid matrix shape/size fails.
booleanMultiply
booleanMultiply :: [[Bool]] -> [[Bool]] -> Either MathError [[Bool]] Source #
Multiply compatible square Bool relation matrices over OR/AND, representing relational composition. Invalid dimensions or size bounds fail.
Prop
Boolean proposition tree. Literal and Variable leaves combine through Not,And,Or,Xor,Implies,Iff; Variable indices address the assignment list passed to evaluateProp.
evaluateProp
evaluateProp :: [Bool] -> Prop -> Either MathError Bool Source #
Given variable Bool assignment list then proposition, evaluate literalsvariablesconnectives. Invalid variable index or excessive expression depth returns Left MathError.
truthTable
truthTable :: Int -> Prop -> Either MathError [([Bool], Bool)] Source #
Assignments in binary order, variable zero the least-significant bit.
Implicant
Value bits and a don't-care mask. Both fields are bounded by the supplied
input width when returned by quineMcCluskey.
Constructors
| Implicant | |
Fields
| |
Instances
| Show Implicant Source # | |
| Eq Implicant Source # | |
| Ord Implicant Source # | |
quineMcCluskey
quineMcCluskey :: Int -> Int -> [Integer] -> [Integer] -> Either MathError [Implicant] Source #
Exact Quine--McCluskey prime generation followed by branch-and-bound cover selection. Objective is fewest terms, then literals, then lexical order. The explicit budget counts prime comparisons and covering-search nodes.