Safe Haskell	Safe
Language	Haskell2010

Kleene.Internal.Partition

Synopsis

newtype Partition a = Partition {
- unPartition :: Set a
}
invariant :: (Ord a, Bounded a) => Partition a -> Bool
fromSeparators :: (Enum a, Bounded a, Ord a) => [a] -> Partition a
fromRSets :: (Enum a, Bounded a, Ord a) => [RSet a] -> Partition a
fromRSet :: (Enum a, Bounded a, Ord a) => RSet a -> Partition a
whole :: Partition a
size :: Partition a -> Int
examples :: (Bounded a, Enum a, Ord a) => Partition a -> Set a
intervals :: (Enum a, Bounded a, Ord a) => Partition a -> NonEmpty (a, a)
wedge :: Ord a => Partition a -> Partition a -> Partition a
split :: (Enum a, Bounded a, Eq a) => a -> Partition a
toSF :: (Enum a, Bounded a, Ord a) => (a -> b) -> Partition a -> SF a b

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 unPartition :: Set a

Instances

Eq a => Eq (Partition a) Source #
Instance details Defined in Kleene.Internal.Partition Methods (==) :: Partition a -> Partition a -> Bool # (/=) :: Partition a -> Partition a -> Bool #
Ord a => Ord (Partition a) Source #
Instance details 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) Source #
Instance details 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) Source #	See `wedge`.
Instance details 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) Source #
Instance details 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) Source #	invariant (asPartitionChar p)
Instance details Defined in Kleene.Internal.Partition 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 #

whole :: 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 (uncurry (<=)) $ 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