Kleene.Internal.Partition

Documentation

newtype Partition a

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

• unPartition :: Set a

Instances

Eq a => Eq (Partition a)

Defined in Kleene.Internal.Partition

Methods

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

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

Ord a => Ord (Partition a)

Defined in Kleene.Internal.Partition

Methods

compare :: Partition a -> Partition a -> Ordering

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

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

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

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

max :: Partition a -> Partition a -> Partition a

min :: Partition a -> Partition a -> Partition a

Show a => Show (Partition a)

Defined in Kleene.Internal.Partition

Methods

showsPrec :: Int -> Partition a -> ShowS

show :: Partition a -> String

showList :: [Partition a] -> ShowS

(Enum a, Bounded a, Ord a) => Semigroup (Partition a)

See wedge.

Defined in Kleene.Internal.Partition

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)

Defined in Kleene.Internal.Partition

Methods

mempty :: Partition a

mappend :: Partition a -> Partition a -> Partition a

mconcat :: [Partition a] -> Partition a

(Enum a, Bounded a, Ord a, Arbitrary a) => Arbitrary (Partition a)

invariant (asPartitionChar p)

Defined in Kleene.Internal.Partition

Methods

arbitrary :: Gen (Partition a)

shrink :: Partition a -> [Partition a]

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

Check invariant.

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

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

Construct Partition from list of RSets.

RSet intervals are closed on both sides.

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

whole :: Partition a

size :: Partition a -> Int

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

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)

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

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

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

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

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