Yaya.Fold

Documentation

type Algebra c f a = f a `c` a

type GAlgebra c w f a = f (w a) `c` a

type ElgotAlgebra c w f a = w (f a) `c` a

type AlgebraM c m f a = f a `c` m a

type GAlgebraM c m w f a = f (w a) `c` m a

type ElgotAlgebraM c m w f a = w (f a) `c` m a

type Coalgebra c f a = a `c` f a

type GCoalgebra c m f a = a `c` f (m a)

type ElgotCoalgebra c m f a = a `c` m (f a)

type CoalgebraM c m f a = a `c` m (f a)

Note that using a CoalgebraM “directly” is partial (e.g., with anaM). However, ana . Compose can accept a CoalgebraM and produce something like an effectful stream.

type GCoalgebraM c m n f a = a `c` m (f (n a))

class Projectable c t f | t -> f where

This type class is lawless on its own, but there exist types that can’t implement the corresponding embed operation. Laws are induced by implementing either Steppable (which extends this) or Corecursive (which doesn’t).

Methods

project :: Coalgebra c f t

Instances

Projectable ((->) :: Type -> Type -> Type) Natural Maybe

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) Maybe Natural

Projectable ((->) :: Type -> Type -> Type) Void Identity

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) Identity Void

Functor f => Projectable ((->) :: Type -> Type -> Type) (Nu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) f (Nu f)

Functor f => Projectable ((->) :: Type -> Type -> Type) (Mu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) f (Mu f)

Projectable ((->) :: Type -> Type -> Type) (Fix f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold.Native

Methods

project :: Coalgebra (->) f (Fix f)

Projectable ((->) :: Type -> Type -> Type) ([a] :: Type) (XNor a :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) (XNor a) [a]

Projectable ((->) :: Type -> Type -> Type) (NonEmpty a :: Type) (AndMaybe a :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) (AndMaybe a) (NonEmpty a)

Projectable ((->) :: Type -> Type -> Type) (Maybe a :: Type) (Const (Maybe a) :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) (Const (Maybe a)) (Maybe a)

Projectable ((->) :: Type -> Type -> Type) (Either a b :: Type) (Const (Either a b) :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) (Const (Either a b)) (Either a b)

Projectable ((->) :: Type -> Type -> Type) (Cofree f a :: Type) (EnvT a f :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) (EnvT a f) (Cofree f a)

Projectable ((->) :: Type -> Type -> Type) (Free f a :: Type) (FreeF f a :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) (FreeF f a) (Free f a)

class Projectable c t f => Steppable c t f | t -> f where

Structures you can walk through step-by-step.

Methods

embed :: Algebra c f t

Instances

Steppable ((->) :: Type -> Type -> Type) Natural Maybe

Defined in Yaya.Fold

Methods

embed :: Algebra (->) Maybe Natural

Steppable ((->) :: Type -> Type -> Type) Void Identity

Defined in Yaya.Fold

Methods

embed :: Algebra (->) Identity Void

Functor f => Steppable ((->) :: Type -> Type -> Type) (Nu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) f (Nu f)

Functor f => Steppable ((->) :: Type -> Type -> Type) (Mu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) f (Mu f)

Steppable ((->) :: Type -> Type -> Type) (Fix f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold.Native

Methods

embed :: Algebra (->) f (Fix f)

Steppable ((->) :: Type -> Type -> Type) ([a] :: Type) (XNor a :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) (XNor a) [a]

Steppable ((->) :: Type -> Type -> Type) (NonEmpty a :: Type) (AndMaybe a :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) (AndMaybe a) (NonEmpty a)

Steppable ((->) :: Type -> Type -> Type) (Maybe a :: Type) (Const (Maybe a) :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) (Const (Maybe a)) (Maybe a)

Steppable ((->) :: Type -> Type -> Type) (Either a b :: Type) (Const (Either a b) :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) (Const (Either a b)) (Either a b)

Steppable ((->) :: Type -> Type -> Type) (Cofree f a :: Type) (EnvT a f :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) (EnvT a f) (Cofree f a)

Steppable ((->) :: Type -> Type -> Type) (Free f a :: Type) (FreeF f a :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) (FreeF f a) (Free f a)

class Recursive c t f | t -> f where

Inductive structures that can be reasoned about in the way we usually do – with pattern matching.

Methods

cata :: Algebra c f a -> t `c` a

Instances

Recursive ((->) :: Type -> Type -> Type) Natural Maybe

Defined in Yaya.Fold.Native

Methods

cata :: Algebra (->) Maybe a -> Natural -> a

Recursive ((->) :: Type -> Type -> Type) Void Identity

Defined in Yaya.Fold

Methods

cata :: Algebra (->) Identity a -> Void -> a

Recursive ((->) :: Type -> Type -> Type) (Mu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

cata :: Algebra (->) f a -> Mu f -> a

Recursive ((->) :: Type -> Type -> Type) (Maybe a :: Type) (Const (Maybe a) :: Type -> Type)

Defined in Yaya.Fold

Methods

cata :: Algebra (->) (Const (Maybe a)) a0 -> Maybe a -> a0

Recursive ((->) :: Type -> Type -> Type) (Either a b :: Type) (Const (Either a b) :: Type -> Type)

Defined in Yaya.Fold

Methods

cata :: Algebra (->) (Const (Either a b)) a0 -> Either a b -> a0

class Corecursive c t f | t -> f where

Coinductive (potentially-infinite) structures that guarantee _productivity_ rather than termination.

Methods

ana :: Coalgebra c f a -> a `c` t

Instances

Corecursive ((->) :: Type -> Type -> Type) (Nu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

ana :: Coalgebra (->) f a -> a -> Nu f

Functor f => Corecursive ((->) :: Type -> Type -> Type) (Fix f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold.Native

Methods

ana :: Coalgebra (->) f a -> a -> Fix f

Corecursive ((->) :: Type -> Type -> Type) ([a] :: Type) (XNor a :: Type -> Type)

Defined in Yaya.Fold.Native

Methods

ana :: Coalgebra (->) (XNor a) a0 -> a0 -> [a]

Corecursive ((->) :: Type -> Type -> Type) (NonEmpty a :: Type) (AndMaybe a :: Type -> Type)

Defined in Yaya.Fold.Native

Methods

ana :: Coalgebra (->) (AndMaybe a) a0 -> a0 -> NonEmpty a

Corecursive ((->) :: Type -> Type -> Type) (Maybe a :: Type) (Const (Maybe a) :: Type -> Type)

Defined in Yaya.Fold

Methods

ana :: Coalgebra (->) (Const (Maybe a)) a0 -> a0 -> Maybe a

Corecursive ((->) :: Type -> Type -> Type) (Either a b :: Type) (Const (Either a b) :: Type -> Type)

Defined in Yaya.Fold

Methods

ana :: Coalgebra (->) (Const (Either a b)) a0 -> a0 -> Either a b

Functor f => Corecursive ((->) :: Type -> Type -> Type) (Cofree f a :: Type) (EnvT a f :: Type -> Type)

Defined in Yaya.Fold.Native

Methods

ana :: Coalgebra (->) (EnvT a f) a0 -> a0 -> Cofree f a

Functor f => Corecursive ((->) :: Type -> Type -> Type) (Free f a :: Type) (FreeF f a :: Type -> Type)

Defined in Yaya.Fold.Native

Methods

ana :: Coalgebra (->) (FreeF f a) a0 -> a0 -> Free f a

recursiveEq :: (Recursive (->) t f, Steppable (->) u f, Functor f, Foldable f, Eq1 f) => t -> u -> Bool

An implementation of Eq for any Recursive instance. Note that this is actually more general than Eq, as it can compare between different fixed-point representations of the same functor.

recursiveShowsPrec :: (Recursive (->) t f, Show1 f) => Int -> t -> ShowS

An implementation of Show for any Recursive instance.

data Mu f

A fixed-point operator for inductive / finite data structures.

• NB*: This is only guaranteed to be finite when f a is strict in a (having strict functors won't prevent Nu from being lazy). Using -XStrictData can help with this a lot.

Constructors

Mu (forall a. Algebra (->) f a -> a)

Instances

DFunctor Mu

Defined in Yaya.Fold

Methods

dmap :: (forall x. f x -> g x) -> Mu f -> Mu g

(Functor f, Foldable f, Eq1 f) => Eq (Mu f)

Defined in Yaya.Fold

Methods

(==) :: Mu f -> Mu f -> Bool

(/=) :: Mu f -> Mu f -> Bool

Show1 f => Show (Mu f)

Defined in Yaya.Fold

Methods

showsPrec :: Int -> Mu f -> ShowS

show :: Mu f -> String

showList :: [Mu f] -> ShowS

Recursive ((->) :: Type -> Type -> Type) (Mu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

cata :: Algebra (->) f a -> Mu f -> a

Functor f => Projectable ((->) :: Type -> Type -> Type) (Mu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) f (Mu f)

Functor f => Steppable ((->) :: Type -> Type -> Type) (Mu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) f (Mu f)

data Nu f where

A fixed-point operator for coinductive / potentially-infinite data structures.

Constructors

Nu :: Coalgebra (->) f a -> a -> Nu f

Instances

DFunctor Nu

Defined in Yaya.Fold

Methods

dmap :: (forall x. f x -> g x) -> Nu f -> Nu g

Corecursive ((->) :: Type -> Type -> Type) (Nu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

ana :: Coalgebra (->) f a -> a -> Nu f

Functor f => Projectable ((->) :: Type -> Type -> Type) (Nu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) f (Nu f)

Functor f => Steppable ((->) :: Type -> Type -> Type) (Nu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

embed :: Algebra (->) f (Nu f)

zipAlgebras :: Functor f => Algebra (->) f a -> Algebra (->) f b -> Algebra (->) f (a, b)

Combines two Algebras with different carriers into a single tupled Algebra.

lowerDay :: Projectable (->) t g => Algebra (->) (Day f g) a -> Algebra (->) f (t -> a)

Algebras over Day convolution are convenient for binary operations, but aren’t directly handleable by cata.

cata2 :: (Recursive (->) t f, Projectable (->) u g) => Algebra (->) (Day f g) a -> t -> u -> a

By analogy with liftA2 (which also relies on Day, at least conceptually).

lowerAlgebra :: (Functor f, Comonad w) => DistributiveLaw (->) f w -> GAlgebra (->) w f a -> Algebra (->) f (w a)

Makes it possible to provide a GAlgebra to cata.

lowerAlgebraM :: (Applicative m, Traversable f, Comonad w, Traversable w) => DistributiveLaw (->) f w -> GAlgebraM (->) m w f a -> AlgebraM (->) m f (w a)

Makes it possible to provide a GAlgebraM to cataM.

lowerCoalgebra :: (Functor f, Monad m) => DistributiveLaw (->) m f -> GCoalgebra (->) m f a -> Coalgebra (->) f (m a)

Makes it possible to provide a GCoalgebra to ana.

lowerCoalgebraM :: (Applicative m, Traversable f, Monad n, Traversable n) => DistributiveLaw (->) n f -> GCoalgebraM (->) m n f a -> CoalgebraM (->) m f (n a)

Makes it possible to provide a GCoalgebraM to anaM.

gcata :: (Recursive (->) t f, Functor f, Comonad w) => DistributiveLaw (->) f w -> GAlgebra (->) w f a -> t -> a

elgotCata :: (Recursive (->) t f, Functor f, Comonad w) => DistributiveLaw (->) f w -> ElgotAlgebra (->) w f a -> t -> a

gcataM :: (Monad m, Recursive (->) t f, Traversable f, Comonad w, Traversable w) => DistributiveLaw (->) f w -> GAlgebraM (->) m w f a -> t -> m a

elgotCataM :: (Monad m, Recursive (->) t f, Traversable f, Comonad w, Traversable w) => DistributiveLaw (->) f w -> ElgotAlgebraM (->) m w f a -> t -> m a

ezygoM :: (Monad m, Recursive (->) t f, Traversable f) => AlgebraM (->) m f b -> ElgotAlgebraM (->) m ((,) b) f a -> t -> m a

gana :: (Corecursive (->) t f, Functor f, Monad m) => DistributiveLaw (->) m f -> GCoalgebra (->) m f a -> a -> t

elgotAna :: (Corecursive (->) t f, Functor f, Monad m) => DistributiveLaw (->) m f -> ElgotCoalgebra (->) m f a -> a -> t

lambek :: (Steppable (->) t f, Recursive (->) t f, Functor f) => Coalgebra (->) f t

colambek :: (Projectable (->) t f, Corecursive (->) t f, Functor f) => Algebra (->) f t

type DistributiveLaw c f g = forall a. f (g a) `c` g (f a)

There are a number of distributive laws, including sequenceA, distribute, and sequenceL. Yaya also provides others for specific recursion schemes.

distIdentity :: Functor f => DistributiveLaw (->) f Identity

A less-constrained distribute for Identity.

seqIdentity :: Functor f => DistributiveLaw (->) Identity f

A less-constrained sequenceA for Identity.

distTuple :: Functor f => Algebra (->) f a -> DistributiveLaw (->) f ((,) a)

distEnvT :: Functor f => Algebra (->) f a -> DistributiveLaw (->) f w -> DistributiveLaw (->) f (EnvT a w)

seqEither :: Functor f => Coalgebra (->) f a -> DistributiveLaw (->) (Either a) f

attributeAlgebra :: (Steppable (->) t (EnvT a f), Functor f) => Algebra (->) f a -> Algebra (->) f t

Converts an Algebra to one that annotates the tree with the result for each node.

attributeCoalgebra :: Coalgebra (->) f a -> Coalgebra (->) (EnvT a f) a

Converts a Coalgebra to one that annotates the tree with the seed that generated each node.

ignoringAttribute :: Algebra (->) f a -> Algebra (->) (EnvT b f) a

This is just a more obvious name for composing lowerEnvT with your algebra directly.

unFree :: Steppable (->) t f => Algebra (->) (FreeF f t) t

It is somewhat common to have a natural transformation that looks like η :: forall a. f a -> Free g a. This maps naturally to a GCoalgebra (to pass to apo) with η . project, but the desired Algebra is more likely to be cata unFree . η than embed . η. See yaya-streams for some examples of this.

instances for non-recursive types

constEmbed :: Algebra (->) (Const a) a

constProject :: Coalgebra (->) (Const a) a

constCata :: Algebra (->) (Const b) a -> b -> a

constAna :: Coalgebra (->) (Const b) a -> a -> b

Optics

type BialgebraIso f a = Iso' (f a) a

type AlgebraPrism f a = Prism' (f a) a

type CoalgebraPrism f a = Prism' a (f a)

steppableIso :: Steppable (->) t f => BialgebraIso f t

birecursiveIso :: (Recursive (->) t f, Corecursive (->) t f) => BialgebraIso f a -> Iso' t a

recursivePrism :: (Recursive (->) t f, Corecursive (->) t f, Traversable f) => AlgebraPrism f a -> Prism' t a