Safe Haskell	Safe
Language	Haskell2010

Algebra.Heyting.Free

Synopsis

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

Documentation

data Free a Source #

Free Heyting algebra.

Note: Eq and PartialOrd instances aren't structural.

>>> Top == (Var 'x' ==> Var 'x')
True

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

You can test for taulogogies:

>>> leq Top $ (Var 'A' /\ Var 'B' ==> Var 'C') <=>  (Var 'A' ==> Var 'B' ==> Var 'C')
True

>>> leq Top $ (Var 'A' /\ neg (Var 'A')) <=> Bottom
True

>>> leq Top $ (Var 'A' \/ neg (Var 'A')) <=> Top
False

Constructors

Var a
Bottom
Top
(Free a) :/\: (Free a) infixr 6
(Free a) :\/: (Free a) infixr 5
(Free a) :=>: (Free a) infixr 4

Instances

Instances details

Foldable Free Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

fold :: Monoid m => Free m -> m

foldMap :: Monoid m => (a -> m) -> Free a -> 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.Heyting.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)

Applicative Free Source #

Instance details

Defined in Algebra.Heyting.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

Functor Free Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

fmap :: (a -> b) -> Free a -> Free b

(<$) :: a -> Free b -> Free a

Monad Free Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

(>>=) :: Free a -> (a -> Free b) -> Free b

(>>) :: Free a -> Free b -> Free b

return :: a -> Free a

Generic1 Free Source #

Instance details

Defined in Algebra.Heyting.Free

Associated Types

type Rep1 Free

Instance details

Defined in Algebra.Heyting.Free

type Rep1 Free = D1 ('MetaData "Free" "Algebra.Heyting.Free" "lattices-2.2.1.1-J46lACPEOTBKo73SIhecCd" 'False) ((C1 ('MetaCons "Var" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: (C1 ('MetaCons "Bottom" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Top" 'PrefixI 'False) (U1 :: Type -> Type))) :+: (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)) :+: C1 ('MetaCons ":=>:" ('InfixI 'RightAssociative 4) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 Free) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 Free)))))

Methods

from1 :: Free a -> Rep1 Free a

to1 :: Rep1 Free a -> Free a

Arbitrary a => Arbitrary (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

arbitrary :: Gen (Free a)

shrink :: Free a -> [Free a]

Data a => Data (Free a) Source #

Instance details

Defined in Algebra.Heyting.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 :: forall r r'. (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)

Generic (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

Associated Types

type Rep (Free a)

Instance details

Defined in Algebra.Heyting.Free

type Rep (Free a) = D1 ('MetaData "Free" "Algebra.Heyting.Free" "lattices-2.2.1.1-J46lACPEOTBKo73SIhecCd" 'False) ((C1 ('MetaCons "Var" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: (C1 ('MetaCons "Bottom" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Top" 'PrefixI 'False) (U1 :: Type -> Type))) :+: (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))) :+: C1 ('MetaCons ":=>:" ('InfixI 'RightAssociative 4) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Free a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Free a))))))

Methods

from :: Free a -> Rep (Free a) x

to :: Rep (Free a) x -> Free a

Show a => Show (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

showsPrec :: Int -> Free a -> ShowS

show :: Free a -> String

showList :: [Free a] -> ShowS

Ord a => Eq (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

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

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

Heyting (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

(==>) :: Free a -> Free a -> Free a Source #

neg :: Free a -> Free a Source #

(<=>) :: Free a -> Free a -> Free a Source #

BoundedJoinSemiLattice (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

bottom :: Free a Source #

BoundedMeetSemiLattice (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

top :: Free a Source #

Lattice (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

(\/) :: Free a -> Free a -> Free a Source #

(/\) :: Free a -> Free a -> Free a Source #

Ord a => PartialOrd (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

Methods

leq :: Free a -> Free a -> Bool Source #

comparable :: Free a -> Free a -> Bool Source #

type Rep1 Free Source #

Instance details

Defined in Algebra.Heyting.Free

type Rep1 Free = D1 ('MetaData "Free" "Algebra.Heyting.Free" "lattices-2.2.1.1-J46lACPEOTBKo73SIhecCd" 'False) ((C1 ('MetaCons "Var" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1) :+: (C1 ('MetaCons "Bottom" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Top" 'PrefixI 'False) (U1 :: Type -> Type))) :+: (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)) :+: C1 ('MetaCons ":=>:" ('InfixI 'RightAssociative 4) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 Free) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec1 Free)))))

type Rep (Free a) Source #

Instance details

Defined in Algebra.Heyting.Free

type Rep (Free a) = D1 ('MetaData "Free" "Algebra.Heyting.Free" "lattices-2.2.1.1-J46lACPEOTBKo73SIhecCd" 'False) ((C1 ('MetaCons "Var" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: (C1 ('MetaCons "Bottom" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Top" 'PrefixI 'False) (U1 :: Type -> Type))) :+: (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))) :+: C1 ('MetaCons ":=>:" ('InfixI 'RightAssociative 4) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Free a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Free a))))))

liftFree :: a -> Free a Source #

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

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

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

toExpr :: Free a -> Expr a Source #