kleene-0: Kleene algebra

Safe HaskellSafe
LanguageHaskell2010

Kleene.Internal.Partition

Synopsis

Documentation

newtype Partition a Source #

Partition devides type into disjoint connected partitions.

Note: we could have non-connecter partitions too, but that would be more complicated. This variant is correct by construction, but less precise.

It's enought to store last element of each piece.

Partition (fromList [x1, x2, x3]) :: Partition s describes a partition of Set s, as

\[ \{ x \mid x \le x_1 \} \cup \{ x \mid x_1 < x \le x_2 \} \cup \{ x \mid x_2 < x \le x_3 \} \cup \{ x \mid x_3 < x \} \]

Note: it's enough to check upper bound conditions only if checks are performed in order.

Invariant: maxBound is not in the set.

Constructors

Partition 

Fields

Instances

Eq a => Eq (Partition a) Source # 

Methods

(==) :: Partition a -> Partition a -> Bool #

(/=) :: Partition a -> Partition a -> Bool #

Ord a => Ord (Partition a) Source # 
Show a => Show (Partition a) Source # 
(Enum a, Bounded a, Ord a) => Semigroup (Partition a) Source #

See wedge.

Methods

(<>) :: Partition a -> Partition a -> Partition a #

sconcat :: NonEmpty (Partition a) -> Partition a #

stimes :: Integral b => b -> Partition a -> Partition a #

(Enum a, Bounded a, Ord a) => Monoid (Partition a) Source # 
(Enum a, Bounded a, Ord a, Arbitrary a) => Arbitrary (Partition a) Source #
invariant (asPartitionChar p)

Methods

arbitrary :: Gen (Partition a) #

shrink :: Partition a -> [Partition a] #

invariant :: (Ord a, Bounded a) => Partition a -> Bool Source #

Check invariant.

fromSeparators :: (Enum a, Bounded a, Ord a) => [a] -> Partition a Source #

fromRSets :: (Enum a, Bounded a, Ord a) => [RSet a] -> Partition a Source #

Construct Partition from list of RSets.

RSet intervals are closed on both sides.

fromRSet :: (Enum a, Bounded a, Ord a) => RSet a -> Partition a Source #

size :: Partition a -> Int Source #

Count of sets in a Partition.

>>> size whole
1
>>> size $ split (10 :: Word8)
2
size (asPartitionChar p) >= 1

examples :: (Bounded a, Enum a, Ord a) => Partition a -> Set a Source #

Extract examples from each subset in a Partition.

>>> examples $ split (10 :: Word8)
fromList [10,255]
>>> examples $ split (10 :: Word8) <> split 20
fromList [10,20,255]
invariant p ==> size (asPartitionChar p) === length (examples p)

intervals :: (Enum a, Bounded a, Ord a) => Partition a -> NonEmpty (a, a) Source #

all (curry (<=)) $ intervals $ asPartitionChar p

wedge :: Ord a => Partition a -> Partition a -> Partition a Source #

Wedge partitions.

>>> split (10 :: Word8) <> split 20
fromSeparators [10,20]
whole `wedge` (p :: Partition Char) === p
(p :: Partition Char) <> whole === p
asPartitionChar p <> q === q <> p
asPartitionChar p <> p === p
invariant $ asPartitionChar p <> q

split :: (Enum a, Bounded a, Eq a) => a -> Partition a Source #

Simplest partition: given x partition space into [min..x) and [x .. max]

>>> split (128 :: Word8)
fromSeparators [128]

toSF :: (Enum a, Bounded a, Ord a) => (a -> b) -> Partition a -> SF a b Source #

Make a step function.

>>> import Data.Word
>>> import Test.QuickCheck ((===))
>>> let asPartitionChar :: Partition Char -> Partition Char; asPartitionChar = id
>>> instance (Ord a, Enum a, Arbitrary a) => Arbitrary (RSet a) where arbitrary = fmap RSet.fromRangeList arbitrary