Safe Haskell	None
Language	Haskell2010

Control.Alternative.Free.LZLC

Contents

Type definitions
Universal properties
Auxiliary definitions

Description

Free alternative (with left zero + left catch).

Alternative laws were not set to one, clear definition, but there are two major ones.

For an instance of (Alternative f), both laws have these in common.

Inherited laws from Applicative
(f a, empty, <|>) forms monoid for any type a.
Left zero law: empty <*> x === empty.

Candidate #1 of the Alternative law have Left distribution law.

-- Left distribution
(x <|> y) <*> z === (x <*> z) <|> (y <*> z)

Another candidate #2 have Left catch law instead.

-- Left catch
pure x <|> y === pure x

Reference Typeclassopedia https://wiki.haskell.org/Typeclassopedia#Laws_6 for more about these laws.

The "free alternative" construction for the alternative #1 (with Left distribution) is known and implemented.

This module provides the free alternative #2.

Synopsis

data Free (f :: Type -> Type) a where
- FreeTrivial :: forall (f :: Type -> Type) a. Trivial f a -> Free f a
- FreeSumZOf' :: forall (f :: Type -> Type) a. NontrivialSumZ (Summand f) a -> Free f a
- FreeApZOf' :: forall (f :: Type -> Type) a. NontrivialApZ (Factor f) a -> Free f a
- pattern SumZOf :: SumZ (Summand f) a -> Free f a
- pattern ApZOf :: Functor f => ApZ (Factor f) a -> Free f a
newtype Summand (f :: Type -> Type) a = Summand {
- runSummand :: Either (f a) (NontrivialApZ (Factor f) a)
}
viewSummand :: Summand f a -> Either (f a) (ApZ (Factor f) a)
newtype Factor (f :: Type -> Type) a = Factor {
- runFactor :: Either (f a) (NontrivialSumZ (Summand f) a)
}
viewFactor :: Factor f a -> Either (f a) (SumZ (Summand f) a)
viewSumZ :: forall (f :: Type -> Type) a. Free f a -> SumZ (Summand f) a
reviewSumZ :: forall (f :: Type -> Type) a. SumZ (Summand f) a -> Free f a
viewApZ :: forall (f :: Type -> Type) a. Free f a -> ApZ (Factor f) a
reviewApZ :: forall (f :: Type -> Type) a. Functor f => ApZ (Factor f) a -> Free f a
hoistFree :: (forall x. f x -> g x) -> Free f a -> Free g a
liftFree :: f a -> Free f a
foldFree :: forall f g a. Alternative g => (forall x. f x -> g x) -> Free f a -> g a
data Trivial (f :: Type -> Type) a
- = TrivialZero
- | TrivialPure a
- | TrivialLift (f a)
type SumZ (f :: Type -> Type) a = ListZ a (f a)
data NontrivialSumZ (f :: Type -> Type) a
- = ConsZee (f a) a
- | ConsMany (f a) (f a) (ListZ a (f a))
data NontrivialApZ (f :: Type -> Type) a where
- ApZero :: forall (f :: Type -> Type) a1 a. f a1 -> NontrivialApZ f a
- ApMany :: forall (f :: Type -> Type) a1 b a. f a1 -> f b -> ApZ f (b -> a1 -> a) -> NontrivialApZ f a

Type definitions

data Free (f :: Type -> Type) a where Source #

The Free (left zero + left catch) Alternative.

The constructors of Free is named intentionally verbose.

To construct a value of Free f a, a convenient and recommended way is to use liftFree and methods of Alternative (Free f) instances.

To pattern match a value of Free f a, a convenient and recommended way is to use ApZOf and SumZOf pattern synonyms, along with viewFactor and viewSummand to pattern match on Factor and Summand further.

Constructors

FreeTrivial :: forall (f :: Type -> Type) a. Trivial f a -> Free f a
FreeSumZOf' :: forall (f :: Type -> Type) a. NontrivialSumZ (Summand f) a -> Free f a
FreeApZOf' :: forall (f :: Type -> Type) a. NontrivialApZ (Factor f) a -> Free f a

Bundled Patterns

pattern SumZOf :: SumZ (Summand f) a -> Free f a	View `Free f a` as a sum of `Summand f`, terminated by either `Nil` or `Zee a` (corresponding `empty` or `pure a` respectively)
pattern ApZOf :: Functor f => ApZ (Factor f) a -> Free f a	View `Free f a` as a product of `Factor f`, terminated by either `Zero` or `Pure a` (corresponding `empty` or `pure a` respectively)

Instances

Instances details

FFunctor Free Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods ffmap :: forall (g :: Type -> Type) (h :: Type -> Type) x. (Functor g, Functor h) => (g ~> h) -> Free g x -> Free h x #
FMonad Free Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods fpure :: forall (g :: Type -> Type). Functor g => g ~> Free g # fbind :: forall (g :: Type -> Type) (h :: Type -> Type) a. (Functor g, Functor h) => (g ~> Free h) -> Free g a -> Free h a #
Functor f => Alternative (Free f) Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods empty :: Free f a # (<\|>) :: Free f a -> Free f a -> Free f a # some :: Free f a -> Free f [a] # many :: Free f a -> Free f [a] #
Functor f => Applicative (Free f) Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods pure :: a -> Free f a # (<>) :: Free f (a -> b) -> Free f a -> Free f b # liftA2 :: (a -> b -> c) -> Free f a -> Free f b -> Free f c # (>) :: Free f a -> Free f b -> Free f b # (<*) :: Free f a -> Free f b -> Free f a #
Functor f => Functor (Free f) Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods fmap :: (a -> b) -> Free f a -> Free f b # (<$) :: a -> Free f b -> Free f a #

newtype Summand (f :: Type -> Type) a Source #

Subexpressions of Free f a which can't be written as any one of

```
empty
```
```
pure a
```
Nontrivial sum x | y

Constructors

Summand
Fields runSummand :: Either (f a) (NontrivialApZ (Factor f) a)

Instances

Instances details

FFunctor Summand Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods ffmap :: forall (g :: Type -> Type) (h :: Type -> Type) x. (Functor g, Functor h) => (g ~> h) -> Summand g x -> Summand h x #
Functor f => Functor (Summand f) Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods fmap :: (a -> b) -> Summand f a -> Summand f b # (<$) :: a -> Summand f b -> Summand f a #

viewSummand :: Summand f a -> Either (f a) (ApZ (Factor f) a) Source #

Summand f a is either f a or a product of multiple Factor f values. The Right case never returns a trivial summand, which is one of

Zero,
Pure a,
liftApZ fac for one fac :: Factor f a

newtype Factor (f :: Type -> Type) a Source #

Subexpressions of Free f a which can't be written as any one of

```
empty
```
```
pure a
```
Nontrivial product x * y

Constructors

Factor
Fields runFactor :: Either (f a) (NontrivialSumZ (Summand f) a)

Instances

Instances details

FFunctor Factor Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods ffmap :: forall (g :: Type -> Type) (h :: Type -> Type) x. (Functor g, Functor h) => (g ~> h) -> Factor g x -> Factor h x #
Functor f => Functor (Factor f) Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods fmap :: (a -> b) -> Factor f a -> Factor f b # (<$) :: a -> Factor f b -> Factor f a #

viewFactor :: Factor f a -> Either (f a) (SumZ (Summand f) a) Source #

Factor f a is either f a or a sum of multiple Summand f values. The Right case never returns a trivial factor, which is one of

Nil,
Zee a,
Cons suma Nil for one suma :: Summand f a

viewSumZ :: forall (f :: Type -> Type) a. Free f a -> SumZ (Summand f) a Source #

reviewSumZ :: forall (f :: Type -> Type) a. SumZ (Summand f) a -> Free f a Source #

viewApZ :: forall (f :: Type -> Type) a. Free f a -> ApZ (Factor f) a Source #

reviewApZ :: forall (f :: Type -> Type) a. Functor f => ApZ (Factor f) a -> Free f a Source #

Universal properties

hoistFree :: (forall x. f x -> g x) -> Free f a -> Free g a Source #

liftFree :: f a -> Free f a Source #

foldFree :: forall f g a. Alternative g => (forall x. f x -> g x) -> Free f a -> g a Source #

Auxiliary definitions

data Trivial (f :: Type -> Type) a Source #

Trivial expressions

Constructors

TrivialZero
TrivialPure a
TrivialLift (f a)

Instances

Instances details

Functor f => Functor (Trivial f) Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods fmap :: (a -> b) -> Trivial f a -> Trivial f b # (<$) :: a -> Trivial f b -> Trivial f a #

type SumZ (f :: Type -> Type) a = ListZ a (f a) Source #

Formal sum of f a ending in either pure a (Zee a) or empty (Nil).

data NontrivialSumZ (f :: Type -> Type) a Source #

Trivial f a + NontrivialSumZ f a ~ SumZ f a = ListZ a (f a)

Constructors

ConsZee (f a) a
ConsMany (f a) (f a) (ListZ a (f a))

Instances

Instances details

FFunctor NontrivialSumZ Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods ffmap :: forall (g :: Type -> Type) (h :: Type -> Type) x. (Functor g, Functor h) => (g ~> h) -> NontrivialSumZ g x -> NontrivialSumZ h x #
Functor f => Functor (NontrivialSumZ f) Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods fmap :: (a -> b) -> NontrivialSumZ f a -> NontrivialSumZ f b # (<$) :: a -> NontrivialSumZ f b -> NontrivialSumZ f a #

data NontrivialApZ (f :: Type -> Type) a where Source #

Trivial f a + NontrivialApZ f a ~ ApZ f a

Constructors

ApZero :: forall (f :: Type -> Type) a1 a. f a1 -> NontrivialApZ f a
ApMany :: forall (f :: Type -> Type) a1 b a. f a1 -> f b -> ApZ f (b -> a1 -> a) -> NontrivialApZ f a

Instances

Instances details

FFunctor NontrivialApZ Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods ffmap :: forall (g :: Type -> Type) (h :: Type -> Type) x. (Functor g, Functor h) => (g ~> h) -> NontrivialApZ g x -> NontrivialApZ h x #
Functor (NontrivialApZ f) Source #
Instance details Defined in Control.Alternative.Free.LZLC Methods fmap :: (a -> b) -> NontrivialApZ f a -> NontrivialApZ f b # (<$) :: a -> NontrivialApZ f b -> NontrivialApZ f a #