Maintainer	hapytexeu+gh@gmail.com
Stability	experimental
Portability	POSIX
Safe Haskell	Safe
Language	Haskell2010

Dep.Data.Three

Contents

Defining a three
Paths in a three
Catamorphisms
Manipulate a Three
Lookups and constructions
Retrieve children according to a path
Convert the Three to an key-value list

Description

This modules defines a three, a tree-like data structure with a leaf, a node, and a link where both subtrees are the same. This is used to make more compact and efficient representations of a boolean function.

Synopsis

data Three a
- = Leaf a
- | Link (Three a)
- | Split (Three a) (Three a)
type ThreePath = [ThreeStep]
type ThreeStep = ThreeValue
three :: (a -> b) -> (b -> b) -> (b -> b -> b) -> Three a -> b
depth :: Three a -> Int
leftmost :: Three a -> a
rightmost :: Three a -> a
flipThree :: Three a -> Three a
flipAllThree :: Three a -> Three a
nstep :: NonDeterministicWalkable f step => f a -> step -> [f a]
apply :: (a -> a) -> ThreePath -> Three (a -> a)
applyTo :: (a -> a) -> ThreePath -> Three a -> Three a
wipe :: a -> ThreePath -> Three a -> Three a
wipeAll :: a -> Three a -> [ThreePath] -> Three a
children :: ThreePath -> Three a -> [a]
children' :: ThreePath -> Three a -> [a] -> [a]
toTraces :: Three a -> [(ThreeValues, a)]
toTraces' :: Three a -> [(ThreeValues, a)] -> [(ThreeValues, a)]
toTraces'' :: Three a -> ThreeValues -> [(ThreeValues, a)] -> [(ThreeValues, a)]

Defining a three

data Three a Source #

A data structure used to specify a mapping from a list of booleans to a value in a more compact way. This datastructure can effectively be used to define a sum of products or a product of sums.

Constructors

Leaf a	A leaf that contains a single value.
Link (Three a)	A link where it means that this variable does not matter but the next one(s) will.
Split (Three a) (Three a)	A split where this variable determines the outcome.

Instances

Instances details

Functor Three Source #
Instance details Defined in Dep.Data.Three Methods fmap :: (a -> b) -> Three a -> Three b # (<$) :: a -> Three b -> Three a #
Applicative Three Source #
Instance details Defined in Dep.Data.Three Methods pure :: a -> Three a # (<>) :: Three (a -> b) -> Three a -> Three b # liftA2 :: (a -> b -> c) -> Three a -> Three b -> Three c # (>) :: Three a -> Three b -> Three b # (<*) :: Three a -> Three b -> Three a #
Foldable Three Source #
Instance details Defined in Dep.Data.Three Methods fold :: Monoid m => Three m -> m # foldMap :: Monoid m => (a -> m) -> Three a -> m # foldMap' :: Monoid m => (a -> m) -> Three a -> m # foldr :: (a -> b -> b) -> b -> Three a -> b # foldr' :: (a -> b -> b) -> b -> Three a -> b # foldl :: (b -> a -> b) -> b -> Three a -> b # foldl' :: (b -> a -> b) -> b -> Three a -> b # foldr1 :: (a -> a -> a) -> Three a -> a # foldl1 :: (a -> a -> a) -> Three a -> a # toList :: Three a -> [a] # null :: Three a -> Bool # length :: Three a -> Int # elem :: Eq a => a -> Three a -> Bool # maximum :: Ord a => Three a -> a # minimum :: Ord a => Three a -> a # sum :: Num a => Three a -> a # product :: Num a => Three a -> a #
Traversable Three Source #
Instance details Defined in Dep.Data.Three Methods traverse :: Applicative f => (a -> f b) -> Three a -> f (Three b) # sequenceA :: Applicative f => Three (f a) -> f (Three a) # mapM :: Monad m => (a -> m b) -> Three a -> m (Three b) # sequence :: Monad m => Three (m a) -> m (Three a) #
Arbitrary1 Three Source #
Instance details Defined in Dep.Data.Three Methods liftArbitrary :: Gen a -> Gen (Three a) # liftShrink :: (a -> [a]) -> Three a -> [Three a] #
Eq1 Three Source #
Instance details Defined in Dep.Data.Three Methods liftEq :: (a -> b -> Bool) -> Three a -> Three b -> Bool #
Ord1 Three Source #
Instance details Defined in Dep.Data.Three Methods liftCompare :: (a -> b -> Ordering) -> Three a -> Three b -> Ordering #
NFData1 Three Source #
Instance details Defined in Dep.Data.Three Methods liftRnf :: (a -> ()) -> Three a -> () #
Hashable1 Three Source #
Instance details Defined in Dep.Data.Three Methods liftHashWithSalt :: (Int -> a -> Int) -> Int -> Three a -> Int #
Walkable Three Bool Source #
Instance details Defined in Dep.Data.Three Methods step :: Three a -> Bool -> Three a Source # stepValues' :: Foldable Three => Three a -> Bool -> [a] -> [a] Source # stepValues :: Foldable Three => Three a -> Bool -> [a] Source # allStep :: Functor g => g (Three a) -> Bool -> g (Three a) Source # allStepValues' :: (Foldable Three, Foldable g) => g (Three a) -> Bool -> [a] -> [a] Source # allStepValues :: (Foldable Three, Foldable g) => g (Three a) -> Bool -> [a] Source # walk :: Foldable g => Three a -> g Bool -> Three a Source # walkValues' :: (Foldable Three, Foldable g) => Three a -> g Bool -> [a] -> [a] Source # allWalkValues :: (Foldable Three, Foldable g, Functor g, Foldable h) => g (Three a) -> h Bool -> [a] Source # allWalk :: (Functor g, Foldable h) => g (Three a) -> h Bool -> g (Three a) Source #
NonDeterministicWalkable Three ThreeValue Source #
Instance details Defined in Dep.Data.Three Methods nstep' :: Three a -> ThreeValue -> [Three a] -> [Three a] Source # nstep :: Three a -> ThreeValue -> [Three a] Source # nstepValues' :: Foldable Three => Three a -> ThreeValue -> [a] -> [a] Source # nstepValues :: Foldable Three => Three a -> ThreeValue -> [a] Source # allNstep' :: Foldable g => g (Three a) -> ThreeValue -> [Three a] -> [Three a] Source # allNstep :: Foldable g => g (Three a) -> ThreeValue -> [Three a] Source # allNstepValues :: Foldable Three => [Three a] -> ThreeValue -> [a] Source # nwalk :: Foldable g => Three a -> g ThreeValue -> [Three a] Source # nwalkValues :: (Foldable Three, Foldable g) => Three a -> g ThreeValue -> [a] Source # allNwalk :: Foldable g => [Three a] -> g ThreeValue -> [Three a] Source # allNwalkValues :: (Foldable Three, Foldable g) => [Three a] -> g ThreeValue -> [a] Source #
Lift a => Lift (Three a :: Type) Source #
Instance details Defined in Dep.Data.Three Methods lift :: Three a -> Q Exp # liftTyped :: Three a -> Q (TExp (Three a)) #
Eq a => Eq (Three a) Source #
Instance details Defined in Dep.Data.Three Methods (==) :: Three a -> Three a -> Bool # (/=) :: Three a -> Three a -> Bool #
Data a => Data (Three a) Source #
Instance details Defined in Dep.Data.Three Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Three a -> c (Three a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Three a) # toConstr :: Three a -> Constr # dataTypeOf :: Three a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Three a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Three a)) # gmapT :: (forall b. Data b => b -> b) -> Three a -> Three a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Three a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Three a -> r # gmapQ :: (forall d. Data d => d -> u) -> Three a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Three a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Three a -> m (Three a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Three a -> m (Three a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Three a -> m (Three a) #
Ord a => Ord (Three a) Source #
Instance details Defined in Dep.Data.Three Methods compare :: Three a -> Three a -> Ordering # (<) :: Three a -> Three a -> Bool # (<=) :: Three a -> Three a -> Bool # (>) :: Three a -> Three a -> Bool # (>=) :: Three a -> Three a -> Bool # max :: Three a -> Three a -> Three a # min :: Three a -> Three a -> Three a #
Read a => Read (Three a) Source #
Instance details Defined in Dep.Data.Three Methods readsPrec :: Int -> ReadS (Three a) # readList :: ReadS [Three a] # readPrec :: ReadPrec (Three a) # readListPrec :: ReadPrec [Three a] #
Show a => Show (Three a) Source #
Instance details Defined in Dep.Data.Three Methods showsPrec :: Int -> Three a -> ShowS # show :: Three a -> String # showList :: [Three a] -> ShowS #
Generic (Three a) Source #
Instance details Defined in Dep.Data.Three Associated Types type Rep (Three a) :: Type -> Type # Methods from :: Three a -> Rep (Three a) x # to :: Rep (Three a) x -> Three a #
Semigroup a => Semigroup (Three a) Source #
Instance details Defined in Dep.Data.Three Methods (<>) :: Three a -> Three a -> Three a # sconcat :: NonEmpty (Three a) -> Three a # stimes :: Integral b => b -> Three a -> Three a #
Monoid a => Monoid (Three a) Source #
Instance details Defined in Dep.Data.Three Methods mempty :: Three a # mappend :: Three a -> Three a -> Three a # mconcat :: [Three a] -> Three a #
Arbitrary a => Arbitrary (Three a) Source #
Instance details Defined in Dep.Data.Three Methods arbitrary :: Gen (Three a) # shrink :: Three a -> [Three a] #
Binary a => Binary (Three a) Source #
Instance details Defined in Dep.Data.Three Methods put :: Three a -> Put # get :: Get (Three a) # putList :: [Three a] -> Put #
Default a => Default (Three a) Source #
Instance details Defined in Dep.Data.Three Methods def :: Three a #
NFData a => NFData (Three a) Source #
Instance details Defined in Dep.Data.Three Methods rnf :: Three a -> () #
Hashable a => Hashable (Three a) Source #
Instance details Defined in Dep.Data.Three Methods hashWithSalt :: Int -> Three a -> Int # hash :: Three a -> Int #
Opposite a => Opposite (Three a) Source #
Instance details Defined in Dep.Data.Three Methods opposite :: Three a -> Three a Source #
Eq a => Simplify (Three a) Source #
Instance details Defined in Dep.Data.Three Methods simplify :: Three a -> Three a Source #
Generic1 Three Source #
Instance details Defined in Dep.Data.Three Associated Types type Rep1 Three :: k -> Type # Methods from1 :: forall (a :: k). Three a -> Rep1 Three a # to1 :: forall (a :: k). Rep1 Three a -> Three a #
type Rep (Three a) Source #
Instance details Defined in Dep.Data.Three type Rep (Three a) = D1 ('MetaData "Three" "Dep.Data.Three" "dep-software-0.1.0.0-ImGw9o7wQ122cC0Rs2n7ZK" 'False) (C1 ('MetaCons "Leaf" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: (C1 ('MetaCons "Link" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Three a))) :+: C1 ('MetaCons "Split" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Three a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Three a)))))
type Rep1 Three Source #
Instance details Defined in Dep.Data.Three type Rep1 Three = D1 ('MetaData "Three" "Dep.Data.Three" "dep-software-0.1.0.0-ImGw9o7wQ122cC0Rs2n7ZK" 'False) (C1 ('MetaCons "Leaf" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: (C1 ('MetaCons "Link" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 Three)) :+: C1 ('MetaCons "Split" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 Three) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 Three))))

Paths in a three

type ThreePath = [ThreeStep] Source #

A type of a list (non-deterministic) steps in a Three structure.

type ThreeStep = ThreeValue Source #

A type alias for (non-deterministic) steps in a Three structure.

Catamorphisms

three :: (a -> b) -> (b -> b) -> (b -> b -> b) -> Three a -> b Source #

A catamorphism on the Three object. Here one can provide functions to use for the Leaf, the Link and the Split to catamorph a Three object to another object.

depth Source #

Arguments

:: Three a	The `Three` object to determine the maximum depth from.
-> Int	The depth of the given `Three` object.

Determine the maximum depth of the Three tree.

leftmost Source #

Arguments

:: Three a	The `Three` to obtain the leftmost item from.
-> a	The leftmost item in the given `Three`.

Obtain the leftmost item of the Three.

rightmost Source #

Arguments

:: Three a	The `Three` to obtain the rightmost item from.
-> a	The rightmost item in the given `Three`.

Obtain the rightmost item of the Three.

Manipulate a `Three`

flipThree Source #

Arguments

:: Three a	The given `Three` to flip.
-> Three a	The corresponding flipped `Three`.

Flip the most basic level such that True now maps on False and vice versa. This is for example used to render Karnaugh cards.

flipAllThree Source #

Arguments

:: Three a	The given `Three` to flip.
-> Three a	The corresponding flipped `Three`.

Flip all the nodes in the Three such that the False subtree is now a True subtree, and the True subtree is now the False subtree.

Lookups and constructions

nstep Source #

Arguments

:: NonDeterministicWalkable f step
=> f a	The given initial state where we make a non-determinstic step.
-> step	The step that we make, such step can result in zero, one or more new states.
-> [f a]	The list of the possible states with the new step.

Take a non-deterministic step that can result in multiple outcomes.

apply Source #

Arguments

:: (a -> a)	The given function to apply for the items that satisfy the given path.
-> ThreePath	The given path to use.
-> Three (a -> a)	A `Three` object of functions where the elements that satisfy the path will use the given function and the others will use `id`.

Construct a Three that will apply the given function for the items that satisfy the given path of three-valued objects.

applyTo Source #

Arguments

:: (a -> a)	The given function to apply to some parts of the `Three`.
-> ThreePath	The given path that specifies what for what parts of the `Three` we should apply the function.
-> Three a	The given `Three` where (part) of the `Three` will be modified with a given function.
-> Three a	The resulting `Three` after applying the given function to parts of the `Three` that satisfy the given path.

Apply the given function to the elements in the given Three that satisfy the given path.

wipe Source #

Arguments

:: a	The given value such that we replace parts of the three with the given `ThreePath` to this value.
-> ThreePath	The given path that specifies what for what parts of the `Three` we will set the value.
-> Three a	The given `Three` where (part) of the `Three` will be changed to a `Leaf` with the given value.
-> Three a	The resulting `Three` after changing the items that match the given `ThreePath` to the given value.

Convert the given items that match the given ThreePath to the Leaf with a given element.

wipeAll Source #

Arguments

:: a	The given element to use when we wipe.
-> Three a	The original `Three` where we will wipe items.
-> [ThreePath]	The list of paths to wipe.
-> Three a	The `Three` object after wiping each element in the given list.

Wipe with the given value all the given ThreePaths.

Retrieve children according to a path

children Source #

Arguments

:: ThreePath	The given `ThreePath` for the query.
-> Three a	The given `Three` that we query.
-> [a]	A list of children that satisfy the given `ThreePath`.

Obtain the children that satisfy a given ThreePath.

children' Source #

Arguments

:: ThreePath	The given `ThreePath` for the query.
-> Three a	The given `Three` that we query.
-> [a]	The list of tail elements.
-> [a]	The list of children followed by the given list of tail elements.

Obtain the children that satisfy the given ThreePath.

Convert the `Three` to an key-value list

toTraces Source #

Arguments

:: Three a
-> [(ThreeValues, a)]	The list of addresses in reverse with the corresponding value.

Convert the given Three to a list of 2-tuples with as first item the "address" in reverse, and as second item the value associated with this.

toTraces' Source #

Arguments

:: Three a
-> [(ThreeValues, a)]	The list of trailing items that can be added at the end.
-> [(ThreeValues, a)]	The list of addresses in reverse with the corresponding value.

Convert the given Three to a list of 2-tuples with as first item the "address" in reverse, and as second item the value associated with this.

toTraces'' Source #

Arguments

:: Three a
-> ThreeValues	The current address that will be manipulated as we walk through the `Three` in reverse order.
-> [(ThreeValues, a)]	The list of trailing items that can be added at the end.
-> [(ThreeValues, a)]	The list of addresses in reverse with the corresponding value.

Convert the given Three to a list of 2-tuples with as first item the "address" in reverse, and as second item the value associated with this.

Defining a three

Instances

Paths in a three

Catamorphisms

Manipulate a Three

Lookups and constructions

Retrieve children according to a path

Convert the Three to an key-value list

Manipulate a `Three`

Convert the `Three` to an key-value list