Yaya.Fold

Documentation

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

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

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

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

type Coalgebra c f a = a `c` 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 CoalgebraPrism f a = Prism' a (f a)

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 (->) (Nu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

ana :: forall (a :: k). Coalgebra (->) f a -> a -> Nu f

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

Defined in Yaya.Fold.Native.Internal

Methods

ana :: forall (a :: k). Coalgebra (->) f a -> a -> Cofix f

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

Defined in Yaya.Fold.Native

Methods

ana :: forall (a0 :: k). Coalgebra (->) (AndMaybe a) a0 -> a0 -> NonEmpty a

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

Defined in Yaya.Fold.Native

Methods

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

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

Defined in Yaya.Fold

Methods

ana :: forall (a0 :: k). Coalgebra (->) (Const (Maybe a)) a0 -> a0 -> Maybe a

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

Defined in Yaya.Fold.Native

Methods

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

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

Defined in Yaya.Fold.Native

Methods

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

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

Defined in Yaya.Fold

Methods

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

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.

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

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

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

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

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

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

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

newtype 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 => Projectable (->) (Mu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

cata :: forall (a :: k1). Algebra (->) f a -> Mu f -> a

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

Defined in Yaya.Fold

Methods

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

Monoid (Mu (XNor a))

Defined in Yaya.Applied

Methods

mempty :: Mu (XNor a)

mappend :: Mu (XNor a) -> Mu (XNor a) -> Mu (XNor a)

mconcat :: [Mu (XNor a)] -> Mu (XNor a)

Semigroup (Mu (XNor a))

Defined in Yaya.Applied

Methods

(<>) :: Mu (XNor a) -> Mu (XNor a) -> Mu (XNor a)

sconcat :: NonEmpty (Mu (XNor a)) -> Mu (XNor a)

stimes :: Integral b => b -> Mu (XNor a) -> Mu (XNor a)

(Functor f, Read1 f) => Read (Mu f)

Since: 0.6.1.0

Defined in Yaya.Fold

Methods

readsPrec :: Int -> ReadS (Mu f)

readList :: ReadS [Mu f]

readPrec :: ReadPrec (Mu f)

readListPrec :: ReadPrec [Mu f]

Show1 f => Show (Mu f)

Defined in Yaya.Fold

Methods

showsPrec :: Int -> Mu f -> ShowS

show :: Mu f -> String

showList :: [Mu f] -> ShowS

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

Defined in Yaya.Fold

Methods

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

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

(Functor f, Foldable f, Ord1 f) => Ord (Mu f)

Since: 0.6.1.0

Defined in Yaya.Fold

Methods

compare :: Mu f -> Mu f -> Ordering

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

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

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

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

max :: Mu f -> Mu f -> Mu f

min :: Mu f -> Mu 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 (->) (Nu f :: Type) (f :: Type -> Type)

Defined in Yaya.Fold

Methods

ana :: forall (a :: k). Coalgebra (->) f a -> a -> Nu f

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

IsList (Nu (XNor a))

This instance is safe, since both structures are lazy.

Defined in Yaya.Applied

Associated Types

type Item (Nu (XNor a))

Methods

fromList :: [Item (Nu (XNor a))] -> Nu (XNor a)

fromListN :: Int -> [Item (Nu (XNor a))] -> Nu (XNor a)

toList :: Nu (XNor a) -> [Item (Nu (XNor a))]

(Functor f, Read1 f) => Read (Nu f)

Since: 0.6.1.0

Defined in Yaya.Fold

Methods

readsPrec :: Int -> ReadS (Nu f)

readList :: ReadS [Nu f]

readPrec :: ReadPrec (Nu f)

readListPrec :: ReadPrec [Nu f]

type Item (Nu (XNor a))

Defined in Yaya.Applied

type Item (Nu (XNor a)) = 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 (->) Void Identity

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) Identity Void

Projectable (->) Natural Maybe

Defined in Yaya.Fold

Methods

project :: Coalgebra (->) Maybe Natural

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold.Native

Methods

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

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

Defined in Yaya.Fold.Native.Internal

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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 (->) Void Identity

Defined in Yaya.Fold

Methods

cata :: forall (a :: k1). Algebra (->) Identity a -> Void -> a

Recursive (->) Natural Maybe

Defined in Yaya.Fold.Native

Methods

cata :: forall (a :: k1). Algebra (->) Maybe a -> Natural -> a

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

Defined in Yaya.Fold

Methods

cata :: forall (a :: k1). Algebra (->) f a -> Mu f -> a

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

Defined in Yaya.Fold.Native

Methods

cata :: forall (a :: k1). Algebra (->) f a -> Fix f -> a

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

Defined in Yaya.Fold

Methods

cata :: forall (a0 :: k1). Algebra (->) (Const (Maybe a)) a0 -> Maybe a -> a0

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

Defined in Yaya.Fold

Methods

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

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 (->) Void Identity

Defined in Yaya.Fold

Methods

embed :: Algebra (->) Identity Void

Steppable (->) Natural Maybe

Defined in Yaya.Fold

Methods

embed :: Algebra (->) Maybe Natural

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold.Native

Methods

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

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

Defined in Yaya.Fold.Native.Internal

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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

Defined in Yaya.Fold

Methods

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

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.

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

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).

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

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

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

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

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

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

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

A less-constrained distribute for Identity.

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

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

elgotCata :: (Recursive (->) t f, Functor f, Comonad w) => DistributiveLaw (->) f w -> ElgotAlgebra (->) w f a -> t -> 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 (Pair b) f a -> t -> m a

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

gcata :: (Recursive (->) t f, Functor f, Comonad w) => DistributiveLaw (->) f w -> GAlgebra (->) 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

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

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

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

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.

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.

recursiveCompare :: (Recursive (->) t f, Steppable (->) u f, Functor f, Foldable f, Ord1 f) => t -> u -> Ordering

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

NB: Use recursiveCompare' if you need to use a custom comparator for f.

Since: 0.6.1.0

recursiveCompare' :: (Recursive (->) t f, Steppable (->) u f, Functor f, Foldable f) => (f () -> f () -> Ordering) -> t -> u -> Ordering

Like recursiveCompare, but allows you to provide a custom comparator for f.

Since: 0.6.1.0

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

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

NB: Use recursiveEq' if you need to use a custom comparator for f.

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

Like recursiveEq, but allows you to provide a custom comparator for f.

Since: 0.6.1.0

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

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

An implementation of showsPrec for any Recursive instance.

recursiveShowsPrec' :: Recursive (->) t f => Algebra (->) f (Int -> ShowS) -> Int -> t -> ShowS

Like recursiveShowsPrec, but allows you to provide a custom display function for f.

Since: 0.6.1.0

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

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

A less-constrained sequenceA for Identity.

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

steppableReadPrec :: (Steppable (->) t f, Read1 f) => ReadPrec t

An implementation of readPrec for any Steppable instance.

NB: Use steppableReadPrec' if you need to use a custom parsing function for f.

NB: This only requires Steppable, but the inverse operation is recursiveShowsPrec, which requires Recursive instead.

Since: 0.6.1.0

steppableReadPrec' :: Steppable (->) t f => (ReadPrec t -> ReadPrec [t] -> ReadPrec (f t)) -> ReadPrec t

Like steppableReadPrec, but allows you to provide a custom display function for f.

Since: 0.6.1.0

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.

zipAlgebraMs :: (Applicative m, Functor f) => AlgebraM (->) m f a -> AlgebraM (->) m f b -> AlgebraM (->) m f (Pair a b)

Combines two AlgebraMs with different carriers into a single tupled AlgebraM.

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

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