The Comonad.Reader

[Edit: re-introduced the domain function]

Recently Andy Gill posted a nice use of data families to memoize a narrow range of values to optimize Conal Elliott's functional linear maps.

I've tweaked Andy's definition slightly below to use a type family for D e instead of a data family, which avoids some of the syntactic noise of the domain function when D e = e, and lets it this be used transparently in some places. This change lacks substance however, and the source code links at the bottom include the code with and without this change.

Since I'm using data and type families, you'll need GHC 6.9.

 
class Applicative ((:~*) e) => NarrowMemo e where
        data (:~*) e :: * -> *
        type D e :: *
        apply :: (e :~* r) -> D e -> r
        memo :: (D e -> r) -> (e :~* r)
        domain :: D e -> e
 
instance NarrowMemo Bool where
        data Bool :~* a = MemoBool a a
        type D Bool = Bool
        apply (MemoBool o1 o2) True = o1
        apply (MemoBool o1 o2) False = o2
        memo f = MemoBool (f True) (f False)
        domain = id
 

We can quickly add in the missing bits for the Bool demo he supplied:

 
instance Functor ((:~*) Bool) where
        fmap f (MemoBool a b) = MemoBool (f a) (f b)
 
instance Applicative ((:~*) Bool) where
        pure x = MemoBool x x
        MemoBool f g  < *> MemoBool a b = MemoBool (f a) (g b)
 

And we can automatically generate an instance of Monad for (:~*)e if we really want to:

 
instance NarrowMemo e => Monad ((:~*) e) where
        return = pure
        m >>= k = memo $ apply (fmap k m) >>= apply -- in (->)e
 

And we can drop in a couple more instances to make it interesting. The tensor product:

 
instance (NarrowMemo a, NarrowMemo b) =>
    NarrowMemo (a,b) where
        data (a,b) :~* e = MemoBoth (a :~* (b :~* e))
        type D (a,b) = (D a, D b)
        apply (MemoBoth f) = uncurry (apply . apply f)
        memo f = MemoBoth $ memo $ \a -> memo (f . (,) a)
        domain = domain *** domain
 
instance (NarrowMemo a, NarrowMemo b) =>
    Functor ((:~*) (a,b)) where
        fmap f (MemoBoth g) = MemoBoth (fmap (fmap f) g)
 
instance (NarrowMemo a, NarrowMemo b) =>
    Applicative ((:~*) (a,b)) where
        pure = MemoBoth . pure . pure
        f < *> a = MemoBoth $
                memo $ \da ->
                memo $ \db ->
                let e = (da, db) in
                apply f e (apply a e)
 

and a disjoint sum, if only so we have some more memo tables to play with.

 
instance (NarrowMemo a, NarrowMemo b) =>
    NarrowMemo (Either a b) where
        data Either a b :~* e = MemoEither (a :~* e) (b :~* e)
        type D (Either a b) = Either (D a) (D b)
        apply (MemoEither l _) (Left a) = apply l a
        apply (MemoEither _ r) (Right b) = apply r b
        memo f = MemoEither (memo (f . Left)) (memo (f . Right))
        domain = domain +++ domain
 
instance (NarrowMemo a, NarrowMemo b) =>
    Functor ((:~*) (Either a b)) where
        fmap f (MemoEither a b) = MemoEither (fmap f a) (fmap f b)
 
instance (NarrowMemo a, NarrowMemo b) =>
    Applicative ((:~*) (Either a b)) where
        pure f = MemoEither (pure f) (pure f)
        MemoEither f g < *> MemoEither a b = MemoEither (f < *> a) (g < *> b)
 

Now, the reason I wanted to play with this was I hacked up a memoizing state-in-context comonad a couple of weeks back using unsafePerformIO and a memo table, but using Andy's trick we can build up a pure memoizing context comonad for smaller or more regular domains.

Recall the state-in-context comonad from category-extras.

 
class Comonad w => ComonadContext s w | w -> s where
        getC :: w a -> s
        modifyC :: (s -> s) -> w a -> a
 
data Context s a = Context (s -> a) s
 
instance ComonadContext s (Context s) where
        getC (Context _ s) = s
        modifyC m (Context f c) = f (m c)
 
instance Functor (Context s) where
        fmap f (Context f' s) = Context (f . f') s
 
instance Copointed (Context s) where
        extract   (Context f a) = f a
 
instance Comonad (Context s) where
        duplicate (Context f a) = Context (Context f) a
 

We can modify the definition to replace (->) with the version above of Andy's (:~*) to obtain a narrowly memoized version:

 
data NarrowContext e a = NarrowContext (e :~* a) (D e)
 
instance NarrowMemo e => Functor (NarrowContext e) where
        fmap f (NarrowContext t d) = NarrowContext (memo (f . apply t)) d
 
instance NarrowMemo e => Copointed (NarrowContext e) where
        extract (NarrowContext t d) = apply t d
 
instance NarrowMemo e => Comonad (NarrowContext e) where
        duplicate (NarrowContext f a) =
                NarrowContext (memo (NarrowContext f)) a
 
instance NarrowMemo e => ComonadContext (D e) (NarrowContext e a) where
        getC (NarrowContext _ e) = e
        modifyC f (NarrowContext g e) = apply g (f e)
 

Now any computation done in this modified state-in-context comonad is memoized and compositions of those computations are also memoized and built up from the memoized intermediate steps.

We should be able to play similar games with a lot of other (co)monads that use exponentials as well.

For instance (:~*) itself can play the role of a narrowly-memoized anonymous exponential comonad.

 
instance (NarrowMemo e, Monoid (D e)) => Copointed ((:~*) e) where
        extract t = apply t mempty
 
instance (NarrowMemo e, Monoid (D e)) => Comonad ((:~*) e) where
        duplicate f = memo $ m -> memo (apply f . mappend m)
 

[ Source Code (using data families only) ]
[ Source Code (using data and type families) ]

I want to spend some more time talking about Kan extensions, composition of Kan extensions, and the relationship between a monad and the monad generated by a monad.

But first, I want to take a moment to recall adjunctions and show how they relate to some standard (co)monads, before tying them back to Kan extensions.

Adjunctions 101

An adjunction between categories and consists of a pair of functors , and and a natural isomorphism:

We call the left adjoint functor, and the right adjoint functor and an adjoint pair, and write this relationship as

Borrowing a Haskell definition from Dave Menendez, an adjunction from the category of Haskell types (Hask) to Hask given by a pair of Haskell Functor instances can be defined as follows, where phi is witnessed by = leftAdjunct and = rightAdjunct. [haddock]

 
class (Functor f, Functor g) =>
    Adjunction f g | f -> g, g -> f where
        unit   :: a -> g (f a)
        counit :: f (g a) -> a
        leftAdjunct  :: (f a -> b) -> a -> g b
        rightAdjunct :: (a -> g b) -> f a -> b
 
        unit = leftAdjunct id
        counit = rightAdjunct id
        leftAdjunct f = fmap f . unit
        rightAdjunct f = counit . fmap f
 

Currying and Uncurrying

The most well known adjunction to a Haskell programmer is between the functors given by ((,)e) and ((->)e). (Recall that you can read ((,)e) as (e,) and ((->)e) as (e->); however, the latter syntax isn't valid Haskell as you aren't allowed to make (,) and (->) sections. We use this adjunction most every day in the form of the functions curry and uncurry.

 
curry :: ((a, b) -> c) -> a -> b -> c
curry f x y = f (x,y)
 
uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f ~(x,y) = f x y
 

However the arguments are unfortunately slightly flipped around when we go to define this as an adjunction.

 
instance Adjunction ((,)e) ((->)e) where
        leftAdjunct f a e  = f (e,a)
        rightAdjunct f ~(e,a) = f a e
 

This adjunction defines the relationship between the anonymous reader monad and the anonymous reader comonad (aka the product comonad).

All Readers are the Same

As an aside, if you look at the reader arrow, reader monad and reader comonad all side by side you can see that they are all basically the same thing. Kleisli arrows for the anonymous reader monad have the form a -> e -> b. The Reader arrow takes the form arr (a, e) b, which when arr is (->) this reads as (a,e) -> b, which is just a curried Kleisli arrow for the Reader monad. On the other hand the reader comonad is ((,)e), and its CoKleisli arrows have the form (e,a) -> b. So, putting these side by side:

 
a -> e -> b
(a , e) -> b
(e , a) -> b
 

You can clearly see these are all the same thing!

State and Composing Adjunctions

Once we define functor composition:

 
newtype O f g a = Compose { decompose :: f (g a) }
instance (Functor f, Functor g) => Functor (f `O` g) where
        fmap f = Compose . fmap (fmap f) . decompose
 

We can see that every adjunction gives rise to a monad:

 
instance Adjunction f g => Monad (g `O` f) where
        return = Compose . unit
        m >>= f =
             Compose .
             fmap (rightAdjunct (decompose . f)) $
             decompose m
 

and if you happen to have a Comonad typeclass lying around, a comonad:

 
class Comonad w where
        extract :: w a -> a
        duplicate :: w a -> w (w a)
        extend :: (w a -> b) -> w a -> w b
        extend f = fmap f . duplicate
        duplicate = extend id
 
instance Adjunction f g => Comonad (f `O` g) where
        extract = counit . decompose
        extend f =
                Compose .
                fmap (leftAdjunct (f . Compose)) .
                decompose
 

In reality, adjunction composition is of course not the only way you could form a monad by composition, so in practice a single composition constructor leads to ambiguity. Hence why in category-extras there is a base CompF functor, and specialized variations for different desired instances. For simplicity, I'll stick to `O` here.

We can compose adjunctions, yielding an adjunction, so long as we are careful to place things in the right order:

 
instance (Adjunction f1 g1, Adjunction f2 g2) =>
    Adjunction (f2 `O` f1) (g1 `O` g2) where
        counit =
               counit .
               fmap (counit . fmap decompose) .
               decompose
        unit =
               Compose .
               fmap (fmap Compose . unit) .
               unit
 

In fact, if we use the adjunction defined above, we can see that its just the State monad!

 
instance MonadState e ((->)e `O` (,)e) where
        get = compose $ s -> (s,s)
        put s = compose $ const (s,())
 

Not that I'd be prone to consider using that representation, but we can also see that we get the context comonad this way:

 
class Comonad w =>
    ComonadContext s w | w -> s where
        getC :: w a -> s
        modifyC :: (s -> s) -> w a -> a
 
instance ComonadContext e ((,)e `O` (->)e) where
        getC = fst . decompose
        modifyC f = uncurry (flip id . f) . decompose
 

Adjunctions as Kan Extensions

Unsurprisingly, since pretty much all of category theory comes around to being an observation about Kan extensions in the end, we can find some laws relating left- and right- Kan extensions to adjunctions.

Recall the definitions for right and left Kan extensions over Hask:

 
newtype Ran g h a = Ran
        { runRan :: forall b. (a -> g b) -> h b }
data Lan g h a = forall b. Lan (g b -> a) (h b)
 

Formally, if and only if the right Kan extension exists and is preserved by . (Saunders Mac Lane, Categories for the Working Mathematician p248). We can use this in Haskell to define a natural isomorphism between f and Ran g Identity witnessed by adjointToRan and ranToAdjoint below:

 
adjointToRan :: Adjunction f g => f a -> Ran g Identity a
adjointToRan f = Ran (a -> Identity $ rightAdjunct a f)
 
ranToAdjoint :: Adjunction f g => Ran g Identity a -> f a
ranToAdjoint r = runIdentity (runRan r unit)
 

We can construct a similar natural isomorphism for the right adjoint g of a Functor f and Lan f Identity:

 
adjointToLan :: Adjunction f g => g a -> Lan f Identity a
adjointToLan = Lan counit . Identity
 
lanToAdjoint :: Adjunction f g => Lan f Identity a -> g a
lanToAdjoint (Lan f v) = leftAdjunct f (runIdentity v)
 

So, with that in hand we can see that Ran f Identity -| f -| Lan f Identity, presuming Ran f Identity and Lan f Identity exist.

A More General Connection

Now, the first isomorphism above can be seen as a special case of a more general law relating functor composition and Kan extensions, where h = Identity in the composition below:

 
ranToComposedAdjoint ::
        Adjunction f g =>
        Ran g h a -> (h `O` f) a
ranToComposedAdjoint r = Compose (runRan r unit)
 
composedAdjointToRan ::
        (Functor h, Adjunction f g) =>
        (h `O` f) a -> Ran g h a
composedAdjointToRan f =
        Ran (a -> fmap (rightAdjunct a) (decompose f))
 

Similarly , we get the more generalize relationship for Lan:

 
lanToComposedAdjoint ::
        (Functor h, Adjunction f g) =>
        Lan f h a -> (h `o` g) a
lanToComposedAdjoint (Lan f v) =
        Compose (fmap (leftAdjunct f) v)
 
composedAdjointToLan ::
        Adjunction f g =>
        (h `o` g) a -> Lan f h a
composedAdjointToLan = Lan counit . decompose
 

Composing Kan Extensions

Using the above with the laws for composing right Kan extensions:

 
composeRan :: Ran f (Ran g h) a -> Ran (f `O` g) h a
composeRan r =
        Ran (f -> runRan (runRan r (decompose . f)) id)
 
decomposeRan ::
        Functor f =>
        Ran (f `O` g) h a ->  Ran f (Ran g h) a
decomposeRan r =
        Ran (f -> Ran (g -> runRan r (Compose . fmap g . f)))
 

or the laws for composing left Kan extensions:

 
composeLan ::
        Functor f =>
        Lan f (Lan g h) a -> Lan (f `O` g) h a
composeLan (Lan f (Lan g h)) =
        Lan (f . fmap g . decompose) h
 
decomposeLan :: Lan (f `O` g) h a -> Lan f (Lan g h) a
decomposeLan (Lan f h) = Lan (f . compose) (Lan id h)
 

can give you a lot of ways to construct monads:

Right Kan Extension as (almost) a Monad Transformer

You can lift many of operations from a monad m to the codensity monad of m. Unfortunately, we don't have quite the right type signature for an instance of MonadTrans, so we'll have to make do with our own methods:

[Edit: this has been since factored out into Control.Monad.Codensity to allow Codensity to actually be an instance of MonadTrans]

 
liftRan :: Monad m => m a -> Ran m m a
liftRan m = Ran (m >>=)
 
lowerRan :: Monad m => Ran m m a -> m a
lowerRan a = runRan a return
 
instance MonadReader r m =>
    MonadReader r (Ran m m) where
        ask = liftRan ask
        local f m = Ran (c -> ask >>=
              r -> local f (runRan m (local (const r) . c)))
 
instance MonadIO m =>
    MonadIO (Ran m m) where
        liftIO = liftRan . liftIO
 
instance MonadState s m =>
    MonadState s (Ran m m) where
        get = liftRan get
        put = liftRan . put
 

In fact the list of things you can lift is pretty much the same as what you can lift over the ContT monad transformer due to the similarity in the types. However, just because you lifted the operation into the right or left Kan extension, doesn't mean that it has the same asymptotic performance.

Similarly we can lift many comonadic operations to the Density comonad of a comonad using Lan.

[Edit: Refactored out into Control.Comonad.Density]

Changing Representation

Given a f -| g, g `O` f is a monad, and Ran (g `O` f) (g `O` f) is the monad generated by (g `O` f), described in the previous post. We showed above that this monad can do many of the same things that the original monad could do. From there you can decomposeRan to get Ran g (Ran f (g `O` f)), which you can show to be yet another monad, and you can continue on from there.

Each of these monads may have different operational characteristics and performance tradeoffs. For instance the codensity monad of a monad can offer better asymptotic performance in some usage scenarios.

Similarly the left Kan extension can be used to manipulate the representation of a comonad.

All of this code is encapsulated in category-extras [docs] [darcs] as of release 0.51.0

I think I may spend a post or two talking about Kan extensions.

They appear to be black magic to Haskell programmers, but as Saunders Mac Lane said in Categories for the Working Mathematician:

All concepts are Kan extensions.

So what is a Kan extension? They come in two forms: right- and left- Kan extensions.

First I'll talk about right Kan extensions, since Haskell programmers have a better intuition for them.

Introducing Right Kan Extension

If we observe the type for a right Kan extension over the category of Haskell types:

 
newtype Ran g h a = Ran
        { runRan :: forall b. (a -> g b) -> h b }
 

This is defined in category-extras under Control.Functor.KanExtension along with a lot of the traditional machinery for working with them.

We say that Ran g h is the right Kan extension of h along g. and mathematicians denote it . It has a pretty diagram associated with it, but thats as deep as I'll let the category theory go.

This looks an awful lot like the type of a continuation monad transformer:

 
newtype ContT r m a = ContT
        { runContT :: (a -> m r) -> m r }
 

The main difference is that we have two functors involved and that the body of the Kan extension is universally quantified over the value it contains, so the function it carries can't just hand you back an m r it has lying around unless the functor it has closed over doesn't depend at all on the type r.

Interestingly we can define an instance of Functor for a right Kan extension without even knowing that g or h are functors! Anything of kind * -> * will do.

 
instance Functor (Ran g h) where
        fmap f m = Ran (\k -> runRan m (k . f))
 

The monad generated by a functor

We can take the right Kan extension of a functor f along itself (this works for any functor in Haskell) and get what is known as the monad generated by f or the codensity monad of f:

 
instance Monad (Ran f f) where
	return x = Ran (\k -> k x)
	m >>= k = Ran (\c -> runRan m (\a -> runRan (k a) c))
 

This monad is mentioned in passing in Opmonoidal Monads by Paddy McCrudden and dates back further to Ross Street's "The formal theory of monads" from 1972. The term codensity seems to date back at least to Dubuc's thesis in 1974.

Again, this monad doesn't care one whit about the fact that f is a Functor in the Haskell sense.

This monad provides a useful opportunity for optimization. For instance Janis Voigtländer noted in Asymptotic improvement of functions over Free Monads that a particular monad could be used to improve performance -- Free monads as you'll recall are the tool used in Wouter Sweirstra's Data Types á la Carte, and provide an approach for, among other things, decomposing the IO monad into something more modular, so this is by no means a purely academic exercise!

Voigtländer's monad,

 
newtype C m a = C (forall b. (a -> m b) -> m b)
 

turns out to be just the right Kan extension of another monad along itself, and can equivalently be thought of as a ContT that has been universally quantified over its result type.

The improvement results from the fact that the continuation passing style transformation it applies keeps you from traversing back and forth over the entire tree when performing substitution in the free monad.

The Yoneda Lemma

Heretofore we've only used right Kan extensions where we have extended a functor along itself. Lets change that:

Dan Piponi posted a bit about the Yoneda lemma a couple of years back, which ended with the observation that the Yoneda lemma says that check and uncheck are inverses:

 
> check :: Functor f => f a -> (forall b . (a -> b) -> f b)
> check a f = fmap f a
 
> uncheck :: (forall b . (a -> b) -> f b) -> f a
> uncheck t = t id
 

We can see that this definition for a right Kan extension just boxes up that universal quantifier in a newtype and that we could instantiate:

 
> type Yoneda = Ran Identity
 

and we can define check and uncheck as:

 
check' :: Functor f => f a -> Yoneda f a
check' a = Ran (\f -> fmap (runIdentity . f) a)
 
uncheck' :: Yoneda f a -> f a
uncheck' t = runRan t Identity
 

Limits

We can go on and define categorical limits in terms of right Kan extensions using the Trivial functor that maps everything to a category with a single value and function. In Haskell, this is best expressed by:

 
data Trivial a = Trivial
instance Functor Trivial where
        fmap f _ = Trivial
trivialize :: a -> Trivial b
trivialize _ = Trivial
 
type Lim = Ran Trivial
 

Now, in Haskell, this gives us a clear operational understanding of categorical limits.

 
Lim f a ~ forall b. (a -> Trivial b) -> f b
 

This says that we can't use any information of the value a we supply, or given by the function (a -> Trivial b) when constructing f b, but we have to be able to define an f b for any type b requested. However, we have no way to get any b to plug into the functor! So the only (non-cheating) member of Lim Maybe a is Nothing, of Lim [] a is [], etc.

Left Kan extensions

Left Kan extensions are a bit more obscure to a Haskell programmer, because where right Kan extensions relate to the well-known ContT monad transformer, the left Kan extension is related to a less well known comonad transformer.

First, the a Haskell type for the Left Kan extension of h along g:

 
data Lan g h a = forall b. Lan (g b -> a) (h b)
 

This is related to the admittedly somewhat obscure state-in-context comonad transformer, which I constructed for category-extras.

 
newtype ContextT s w a = ContextT
        { runContextT :: (w s -> a, w s) }
 

However, the left Kan extension provides no information about the type b contained inside of its h functor and g and h are not necessarily the same functor.

As before we get that Lan g h is a Functor regardless of what g and h are, because we only have to map over the right hand side of the contained function:

 
instance Functor (Lan f g) where
	fmap f (Lan g h) = Lan (f . g) h
 

The comonad generated by a functor

We can also see that the left Kan extension of any functor f along itself is a comonad, even if f is not a Haskell Functor. This is of course known as the comonad generated by f, or the density comonad of f.

 
instance Comonad (Lan f f) where
	extract (Lan f a) = f a
	duplicate (Lan f ws) = Lan (Lan f) ws
 

Colimits

Finally we can derive colimits, by:

 
type Colim = Lan Trivial
 

then Colim f a ~ exists b. (Trivial b -> a, f b), and we can see that operationally, we have an f of some unknown type b and for all intents and purposes a value of type a since we can generate a Trivial b from thin air, so while limits allow only structures without values, colimits allow arbitrary structures, but keep you from inspecting the values in them by existential quantification. So for instance you could apply a length function to a Colim [] a, but not add up its values.

You can also build up a covariant analog of the traditional Yoneda lemma using Lan Identity, but I leave that as an exercise for the reader.

I've barely scratched the surface of what you can do with Kan extensions, but I just wanted to shine a little light on this dark corner of category theory.

For more information feel free to explore category-extras. For instance, both right and left Kan extensions along a functor are higher-order functors, and hence so are Yoneda, Lim, and Colim as defined above.

Thats all I have time for now.

Code for right and left Kan extensions, limits, colimits and the Yoneda lemma are all available from category-extras on hackage.

[Edit: the code has since been refactored to treat Yoneda, CoYoneda, Density and Codensity as separate newtypes to allow for instance both Yoneda and Codensity to be different monads]

 
> import Control.Arrow ((|||),(&&&),left)
> newtype Mu f = InF { outF :: f (Mu f) }
 

I want to talk about a novel recursion scheme that hasn't received a lot of attention from the Haskell community and its even more obscure dual -- which is necessarily more obscure because I believe this is the first time anyone has talked about it.

Jiri Adámek, Stefan Milius and Jiri Velebil have done a lot of work on Elgot algebras. Here I'd like to translate them into Haskell, dualize them, observe that the dual can encode primitive recursion, and provide some observations.

You can kind of think an Elgot algebra as a hylomorphism that cheats.

 
> elgot :: Functor f => (f b -> b) -> (a -> Either b (f a)) -> a -> b
> elgot phi psi = h where h = (id ||| phi . fmap h) . psi
 

If you look at the signature for a hylomorphism:

 
> hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
> hylo phi psi = h where h = phi . fmap h . psi
 

Then you can see that an Elgot algebra is basically a hylomorphism that is allowed to shortcircuit the infinite tower of fmaps and return an intermediate result directly.

In some sense you can say that the coalgebra-like side of the hylomorphism is no longer oblivious to the algebra used to deconstruct the intermediate result.

We can take the Elgot algebra and dualize it to get a novel construction where the algebra-like side is no longer oblivious to the coalgebra. This allows your algebra to cheat and just use the intermediate results constructed by the anamorphism to return an answer. I'll choose to call this co-(Elgot algebra) an Elgot coalgebra in the sequel.

 
> coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b
> coelgot phi psi = h where h = phi . (id &&& fmap h . psi)
 

In a lot of ways an Elgot algebra resembles Vene and Uustalu's apomorphism.

 
> apo :: Functor f => (a -> f (Either (Mu f) a)) -> a -> Mu f
> apo psi = h where h = InF . fmap h . (fmap Left . outF ||| psi) . Right
 

However, we have 'unfixed' the algebra to be used from InF to something more general and the layering of Either and f is different.

Now, a generalized apomorphism does something similar entangling two coalgebras, but the signature doesn't quite match up either, since a generalized apomorphism uses an F-coalgebras and an F-(b + _)-monadic coalgebra.

 
> g_apo :: Functor f => (b -> f b) -> (a -> f (Either b a)) -> a -> Mu f
> g_apo g f = h where h = InF . fmap h . (fmap Left . g ||| f) . Right
 

Similarly a zygomorphism, or more generally a mutumorphism entangles two algebras.

An Elgot algebra occupies a somewhat rare spot in the theory of constructive algorithmics or recursion schemes in that it while it mixes an algebra with a coalgebra like a hylomorphism or metamorphisms, it entangles them in a novel way.

If we specialize the Elgot algebra by