Safe Haskell	Safe
Language	Haskell2010

Algebra.Lattice.Free

Synopsis

data Free a
- = Var a
- | (Free a) :/\: (Free a)
- | (Free a) :\/: (Free a)
liftFree :: a -> Free a
lowerFree :: Lattice b => (a -> b) -> Free a -> b
substFree :: Free a -> (a -> Free b) -> Free b
retractFree :: Lattice a => Free a -> a
toExpr :: Free a -> Expr a

Documentation

data Free a Source #

Free distributive lattice.

Eq and PartialOrd instances aren't structural.

>>> (Var 'x' /\ Var 'y') == (Var 'y' /\ Var 'x' /\ Var 'x')
True

>>> Var 'x' == Var 'y'
False

This is distributive lattice.

>>> import Algebra.Lattice.M3 -- non distributive lattice
>>> let x = M3a; y = M3b; z = M3c
>>> let lhs = Var x \/ (Var y /\ Var z)
>>> let rhs = (Var x \/ Var y) /\ (Var x \/ Var z)

Free is distributive so

>>> lhs == rhs
True

but when retracted, values are inequal

>>> retractFree lhs == retractFree rhs
False

>>> (retractFree lhs, retractFree rhs)
(M3a,M3i)

Constructors

Var a
(Free a) :/\: (Free a) infixr 6
(Free a) :\/: (Free a) infixr 5

Instances

Monad Free Source #
Instance details Defined in Algebra.Lattice.Free Methods (>>=) :: Free a -> (a -> Free b) -> Free b # (>>) :: Free a -> Free b -> Free b # return :: a -> Free a # fail :: String -> Free a #
Functor Free Source #
Instance details Defined in Algebra.Lattice.Free Methods fmap :: (a -> b) -> Free a -> Free b # (<$) :: a -> Free b -> Free a #
Applicative Free Source #
Instance details Defined in Algebra.Lattice.Free Methods pure :: a -> Free a # (<>) :: Free (a -> b) -> Free a -> Free b # liftA2 :: (a -> b -> c) -> Free a -> Free b -> Free c # (>) :: Free a -> Free b -> Free b # (<*) :: Free a -> Free b -> Free a #
Foldable Free Source #
Instance details Defined in Algebra.Lattice.Free Methods fold :: Monoid m => Free m -> m # foldMap :: Monoid m => (a -> m) -> Free a -> m # foldr :: (a -> b -> b) -> b -> Free a -> b # foldr' :: (a -> b -> b) -> b -> Free a -> b # foldl :: (b -> a -> b) -> b -> Free a -> b # foldl' :: (b -> a -> b) -> b -> Free a -> b # foldr1 :: (a -> a -> a) -> Free a -> a # foldl1 :: (a -> a -> a) -> Free a -> a # toList :: Free a -> [a] # null :: Free a -> Bool # length :: Free a -> Int # elem :: Eq a => a -> Free a -> Bool # maximum :: Ord a => Free a -> a # minimum :: Ord a => Free a -> a # sum :: Num a => Free a -> a # product :: Num a => Free a -> a #
Traversable Free Source #
Instance details Defined in Algebra.Lattice.Free Methods traverse :: Applicative f => (a -> f b) -> Free a -> f (Free b) # sequenceA :: Applicative f => Free (f a) -> f (Free a) # mapM :: Monad m => (a -> m b) -> Free a -> m (Free b) # sequence :: Monad m => Free (m a) -> m (Free a) #
Ord a => Eq (Free a) Source #
Instance details Defined in Algebra.Lattice.Free Methods (==) :: Free a -> Free a -> Bool # (/=) :: Free a -> Free a -> Bool #
Data a => Data (Free a) Source #
Instance details Defined in Algebra.Lattice.Free Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Free a -> c (Free a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Free a) # toConstr :: Free a -> Constr # dataTypeOf :: Free a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Free a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Free a)) # gmapT :: (forall b. Data b => b -> b) -> Free a -> Free a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Free a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Free a -> r # gmapQ :: (forall d. Data d => d -> u) -> Free a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Free a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Free a -> m (Free a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Free a -> m (Free a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Free a -> m (Free a) #
Show a => Show (Free a) Source #
Instance details Defined in Algebra.Lattice.Free Methods showsPrec :: Int -> Free a -> ShowS # show :: Free a -> String # showList :: [Free a] -> ShowS #
Generic (Free a) Source #
Instance details Defined in Algebra.Lattice.Free Associated Types type Rep (Free a) :: Type -> Type # Methods from :: Free a -> Rep (Free a) x # to :: Rep (Free a) x -> Free a #
Arbitrary a => Arbitrary (Free a) Source #
Instance details Defined in Algebra.Lattice.Free Methods arbitrary :: Gen (Free a) # shrink :: Free a -> [Free a] #
Ord a => PartialOrd (Free a) Source #
Instance details Defined in Algebra.Lattice.Free Methods leq :: Free a -> Free a -> Bool Source # comparable :: Free a -> Free a -> Bool Source #
Lattice (Free a) Source #
Instance details Defined in Algebra.Lattice.Free Methods (\/) :: Free a -> Free a -> Free a Source # (/\) :: Free a -> Free a -> Free a Source #
Generic1 Free Source #
Instance details Defined in Algebra.Lattice.Free Associated Types type Rep1 Free :: k -> Type # Methods from1 :: Free a -> Rep1 Free a # to1 :: Rep1 Free a -> Free a #
type Rep (Free a) Source #
Instance details Defined in Algebra.Lattice.Free type Rep (Free a) = D1 (MetaData "Free" "Algebra.Lattice.Free" "lattices-2-GNwPiglY2qIELYMTNuLIEL" False) (C1 (MetaCons "Var" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a)) :+: (C1 (MetaCons ":/\\:" (InfixI RightAssociative 6) False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Free a)) :: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Free a))) :+: C1 (MetaCons ":\\/:" (InfixI RightAssociative 5) False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Free a)) :: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Free a)))))
type Rep1 Free Source #
Instance details Defined in Algebra.Lattice.Free type Rep1 Free = D1 (MetaData "Free" "Algebra.Lattice.Free" "lattices-2-GNwPiglY2qIELYMTNuLIEL" False) (C1 (MetaCons "Var" PrefixI False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1) :+: (C1 (MetaCons ":/\\:" (InfixI RightAssociative 6) False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec1 Free) :: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec1 Free)) :+: C1 (MetaCons ":\\/:" (InfixI RightAssociative 5) False) (S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec1 Free) :: S1 (MetaSel (Nothing :: Maybe Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec1 Free))))

liftFree :: a -> Free a Source #

lowerFree :: Lattice b => (a -> b) -> Free a -> b Source #

substFree :: Free a -> (a -> Free b) -> Free b Source #

retractFree :: Lattice a => Free a -> a Source #

toExpr :: Free a -> Expr a Source #