What does "coalgebra" mean in the context of programming?

Question

I have heard the term "coalgebras" several times in functional programming and PLT circles, especially when the discussion is about objects, comonads, lenses, and such. Googling this term gives pages that give mathematical description of these structures which is pretty much incomprehensible to me. Can anyone please explain what coalgebras mean in the context of programming, what is their significance, and how they relate to objects and comonads?

Solution 1

Algebras

I think the place to start would be to understand the idea of an algebra. This is just a generalization of algebraic structures like groups, rings, monoids and so on. Most of the time, these things are introduced in terms of sets, but since we're among friends, I'll talk about Haskell types instead. (I can't resist using some Greek letters though—they make everything look cooler!)

An algebra, then, is just a type τ with some functions and identities. These functions take differing numbers of arguments of type τ and produce a τ: uncurried, they all look like (τ, τ,…, τ) → τ. They can also have "identities"—elements of τ that have special behavior with some of the functions.

The simplest example of this is the monoid. A monoid is any type τ with a function mappend ∷ (τ, τ) → τ and an identity mzero ∷ τ. Other examples include things like groups (which are just like monoids except with an extra invert ∷ τ → τ function), rings, lattices and so on.

All the functions operate on τ but can have different arities. We can write these out as τⁿ → τ, where τⁿ maps to a tuple of n τ. This way, it makes sense to think of identities as τ⁰ → τ where τ⁰ is just the empty tuple (). So we can actually simplify the idea of an algebra now: it's just some type with some number of functions on it.

An algebra is just a common pattern in mathematics that's been "factored out", just like we do with code. People noticed that a whole bunch of interesting things—the aforementioned monoids, groups, lattices and so on—all follow a similar pattern, so they abstracted it out. The advantage of doing this is the same as in programming: it creates reusable proofs and makes certain kinds of reasoning easier.

F-Algebras

However, we're not quite done with factoring. So far, we have a bunch of functions τⁿ → τ. We can actually do a neat trick to combine them all into one function. In particular, let's look at monoids: we have mappend ∷ (τ, τ) → τ and mempty ∷ () → τ. We can turn these into a single function using a sum type—Either. It would look like this:

op ∷ Monoid τ ⇒ Either (τ, τ) () → τ
op (Left (a, b)) = mappend (a, b)
op (Right ())    = mempty

We can actually use this transformation repeatedly to combine all the τⁿ → τ functions into a single one, for any algebra. (In fact, we can do this for any number of functions a → τ, b → τ and so on for any a, b,….)

This lets us talk about algebras as a type τ with a single function from some mess of Eithers to a single τ. For monoids, this mess is: Either (τ, τ) (); for groups (which have an extra τ → τ operation), it's: Either (Either (τ, τ) τ) (). It's a different type for every different structure. So what do all these types have in common? The most obvious thing is that they are all just sums of products—algebraic data types. For example, for monoids, we could create a monoid argument type that works for any monoid τ:

data MonoidArgument τ = Mappend τ τ -- here τ τ is the same as (τ, τ)
                      | Mempty      -- here we can just leave the () out

We can do the same thing for groups and rings and lattices and all the other possible structures.

What else is special about all these types? Well, they're all Functors! E.g.:

instance Functor MonoidArgument where
  fmap f (Mappend τ τ) = Mappend (f τ) (f τ)
  fmap f Mempty        = Mempty

So we can generalize our idea of an algebra even more. It's just some type τ with a function f τ → τ for some functor f. In fact, we could write this out as a typeclass:

class Functor f ⇒ Algebra f τ where
  op ∷ f τ → τ

This is often called an "F-algebra" because it's determined by the functor F. If we could partially apply typeclasses, we could define something like class Monoid = Algebra MonoidArgument.

Coalgebras

Now, hopefully you have a good grasp of what an algebra is and how it's just a generalization of normal algebraic structures. So what is an F-coalgebra? Well, the co implies that it's the "dual" of an algebra—that is, we take an algebra and flip some arrows. I only see one arrow in the above definition, so I'll just flip that:

class Functor f ⇒ CoAlgebra f τ where
  coop ∷ τ → f τ

And that's all it is! Now, this conclusion may seem a little flippant (heh). It tells you what a coalgebra is, but does not really give any insight on how it's useful or why we care. I'll get to that in a bit, once I find or come up with a good example or two :P.

Classes and Objects

After reading around a bit, I think I have a good idea of how to use coalgebras to represent classes and objects. We have a type C that contains all the possible internal states of objects in the class; the class itself is a coalgebra over C which specifies the methods and properties of the objects.

As shown in the algebra example, if we have a bunch of functions like a → τ and b → τ for any a, b,…, we can combine them all into a single function using Either, a sum type. The dual "notion" would be combining a bunch of functions of type τ → a, τ → b and so on. We can do this using the dual of a sum type—a product type. So given the two functions above (called f and g), we can create a single one like so:

both ∷ τ → (a, b)
both x = (f x, g x)

The type (a, a) is a functor in the straightforward way, so it certainly fits with our notion of an F-coalgebra. This particular trick lets us package up a bunch of different functions—or, for OOP, methods—into a single function of type τ → f τ.

The elements of our type C represent the internal state of the object. If the object has some readable properties, they have to be able to depend on the state. The most obvious way to do this is to make them a function of C. So if we want a length property (e.g. object.length), we would have a function C → Int.

We want methods that can take an argument and modify state. To do this, we need to take all the arguments and produce a new C. Let's imagine a setPosition method which takes an x and a y coordinate: object.setPosition(1, 2). It would look like this: C → ((Int, Int) → C).

The important pattern here is that the "methods" and "properties" of the object take the object itself as their first argument. This is just like the self parameter in Python and like the implicit this of many other languages. A coalgebra essentially just encapsulates the behavior of taking a self parameter: that's what the first C in C → F C is.

So let's put it all together. Let's imagine a class with a position property, a name property and setPosition function:

class C
  private
    x, y  : Int
    _name : String
  public
    name        : String
    position    : (Int, Int)
    setPosition : (Int, Int) → C

We need two parts to represent this class. First, we need to represent the internal state of the object; in this case it just holds two Ints and a String. (This is our type C.) Then we need to come up with the coalgebra representing the class.

data C = Obj { x, y  ∷ Int
             , _name ∷ String }

We have two properties to write. They're pretty trivial:

position ∷ C → (Int, Int)
position self = (x self, y self)

name ∷ C → String
name self = _name self

Now we just need to be able to update the position:

setPosition ∷ C → (Int, Int) → C
setPosition self (newX, newY) = self { x = newX, y = newY }

This is just like a Python class with its explicit self variables. Now that we have a bunch of self → functions, we need to combine them into a single function for the coalgebra. We can do this with a simple tuple:

coop ∷ C → ((Int, Int), String, (Int, Int) → C)
coop self = (position self, name self, setPosition self)

The type ((Int, Int), String, (Int, Int) → c)—for any c—is a functor, so coop does have the form we want: Functor f ⇒ C → f C.

Given this, C along with coop form a coalgebra which specifies the class I gave above. You can see how we can use this same technique to specify any number of methods and properties for our objects to have.

This lets us use coalgebraic reasoning to deal with classes. For example, we can bring in the notion of an "F-coalgebra homomorphism" to represent transformations between classes. This is a scary sounding term that just means a transformation between coalgebras that preserves structure. This makes it much easier to think about mapping classes onto other classes.

In short, an F-coalgebra represents a class by having a bunch of properties and methods that all depend on a self parameter containing each object's internal state.

Other Categories

So far, we've talked about algebras and coalgebras as Haskell types. An algebra is just a type τ with a function f τ → τ and a coalgebra is just a type τ with a function τ → f τ.

However, nothing really ties these ideas to Haskell per se. In fact, they're usually introduced in terms of sets and mathematical functions rather than types and Haskell functions. Indeed,we can generalize these concepts to any categories!

We can define an F-algebra for some category C. First, we need a functor F : C → C—that is, an endofunctor. (All Haskell Functors are actually endofunctors from Hask → Hask.) Then, an algebra is just an object A from C with a morphism F A → A. A coalgebra is the same except with A → F A.

What do we gain by considering other categories? Well, we can use the same ideas in different contexts. Like monads. In Haskell, a monad is some type M ∷ ★ → ★ with three operations:

map      ∷ (α → β) → (M α → M β)
return   ∷ α → M α
join     ∷ M (M α) → M α

The map function is just a proof of the fact that M is a Functor. So we can say that a monad is just a functor with two operations: return and join.

Functors form a category themselves, with morphisms between them being so-called "natural transformations". A natural transformation is just a way to transform one functor into another while preserving its structure. Here's a nice article helping explain the idea. It talks about concat, which is just join for lists.

With Haskell functors, the composition of two functors is a functor itself. In pseudocode, we could write this:

instance (Functor f, Functor g) ⇒ Functor (f ∘ g) where
  fmap fun x = fmap (fmap fun) x

This helps us think about join as a mapping from f ∘ f → f. The type of join is ∀α. f (f α) → f α. Intuitively, we can see how a function valid for all types α can be thought of as a transformation of f.

return is a similar transformation. Its type is ∀α. α → f α. This looks different—the first α is not "in" a functor! Happily, we can fix this by adding an identity functor there: ∀α. Identity α → f α. So return is a transformation Identity → f.

Now we can think about a monad as just an algebra based around some functor f with operations f ∘ f → f and Identity → f. Doesn't this look familiar? It's very similar to a monoid, which was just some type τ with operations τ × τ → τ and () → τ.

So a monad is just like a monoid, except instead of having a type we have a functor. It's the same sort of algebra, just in a different category. (This is where the phrase "A monad is just a monoid in the category of endofunctors" comes from as far as I know.)

Now, we have these two operations: f ∘ f → f and Identity → f. To get the corresponding coalgebra, we just flip the arrows. This gives us two new operations: f → f ∘ f and f → Identity. We can turn them into Haskell types by adding type variables as above, giving us ∀α. f α → f (f α) and ∀α. f α → α. This looks just like the definition of a comonad:

class Functor f ⇒ Comonad f where
  coreturn ∷ f α → α
  cojoin   ∷ f α → f (f α)

So a comonad is then a coalgebra in a category of endofunctors.

Solution 2

F-algebras and F-coalgebras are mathematical structures which are instrumental in reasoning about inductive types (or recursive types).

F-algebras

We'll start first with F-algebras. I will try to be as simple as possible.

I guess you know what is a recursive type. For example, this is a type for a list of integers:

data IntList = Nil | Cons (Int, IntList)

It is obvious that it is recursive - indeed, its definition refers to itself. Its definition consists of two data constructors, which have the following types:

Nil  :: () -> IntList
Cons :: (Int, IntList) -> IntList

Note that I have written type of Nil as () -> IntList, not simply IntList. These are in fact equivalent types from the theoretical point of view, because () type has only one inhabitant.

If we write signatures of these functions in a more set-theoretical way, we will get

Nil  :: 1 -> IntList
Cons :: Int × IntList -> IntList

where 1 is a unit set (set with one element) and A × B operation is a cross product of two sets A and B (that is, set of pairs (a, b) where a goes through all elements of A and b goes through all elements of B).

Disjoint union of two sets A and B is a set A | B which is a union of sets {(a, 1) : a in A} and {(b, 2) : b in B}. Essentially it is a set of all elements from both A and B, but with each of this elements 'marked' as belonging to either A or B, so when we pick any element from A | B we will immediately know whether this element came from A or from B.

We can 'join' Nil and Cons functions, so they will form a single function working on a set 1 | (Int × IntList):

Nil|Cons :: 1 | (Int × IntList) -> IntList

Indeed, if Nil|Cons function is applied to () value (which, obviously, belongs to 1 | (Int × IntList) set), then it behaves as if it was Nil; if Nil|Cons is applied to any value of type (Int, IntList) (such values are also in the set 1 | (Int × IntList), it behaves as Cons.

Now consider another datatype:

data IntTree = Leaf Int | Branch (IntTree, IntTree)

It has the following constructors:

Leaf   :: Int -> IntTree
Branch :: (IntTree, IntTree) -> IntTree

which also can be joined into one function:

Leaf|Branch :: Int | (IntTree × IntTree) -> IntTree

It can be seen that both of this joined functions have similar type: they both look like

f :: F T -> T

where F is a kind of transformation which takes our type and gives more complex type, which consists of x and | operations, usages of T and possibly other types. For example, for IntList and IntTree F looks as follows:

F1 T = 1 | (Int × T)
F2 T = Int | (T × T)

We can immediately notice that any algebraic type can be written in this way. Indeed, that is why they are called 'algebraic': they consist of a number of 'sums' (unions) and 'products' (cross products) of other types.

Now we can define F-algebra. F-algebra is just a pair (T, f), where T is some type and f is a function of type f :: F T -> T. In our examples F-algebras are (IntList, Nil|Cons) and (IntTree, Leaf|Branch). Note, however, that despite that type of f function is the same for each F, T and f themselves can be arbitrary. For example, (String, g :: 1 | (Int x String) -> String) or (Double, h :: Int | (Double, Double) -> Double) for some g and h are also F-algebras for corresponding F.

Afterwards we can introduce F-algebra homomorphisms and then initial F-algebras, which have very useful properties. In fact, (IntList, Nil|Cons) is an initial F1-algebra, and (IntTree, Leaf|Branch) is an initial F2-algebra. I will not present exact definitions of these terms and properties since they are more complex and abstract than needed.

Nonetheless, the fact that, say, (IntList, Nil|Cons) is F-algebra allows us to define fold-like function on this type. As you know, fold is a kind of operation which transforms some recursive datatype in one finite value. For example, we can fold a list of integer into a single value which is a sum of all elements in the list:

foldr (+) 0 [1, 2, 3, 4] -> 1 + 2 + 3 + 4 = 10

It is possible to generalize such operation on any recursive datatype.

The following is a signature of foldr function:

foldr :: ((a -> b -> b), b) -> [a] -> b

Note that I have used braces to separate first two arguments from the last one. This is not real foldr function, but it is isomorphic to it (that is, you can easily get one from the other and vice versa). Partially applied foldr will have the following signature:

foldr ((+), 0) :: [Int] -> Int

We can see that this is a function which takes a list of integers and returns a single integer. Let's define such function in terms of our IntList type.

sumFold :: IntList -> Int
sumFold Nil         = 0
sumFold (Cons x xs) = x + sumFold xs

We see that this function consists of two parts: first part defines this function's behavior on Nil part of IntList, and second part defines function's behavior on Cons part.

Now suppose that we are programming not in Haskell but in some language which allows usage of algebraic types directly in type signatures (well, technically Haskell allows usage of algebraic types via tuples and Either a b datatype, but this will lead to unnecessary verbosity). Consider a function:

reductor :: () | (Int × Int) -> Int
reductor ()     = 0
reductor (x, s) = x + s

It can be seen that reductor is a function of type F1 Int -> Int, just as in definition of F-algebra! Indeed, the pair (Int, reductor) is an F1-algebra.

Because IntList is an initial F1-algebra, for each type T and for each function r :: F1 T -> T there exist a function, called catamorphism for r, which converts IntList to T, and such function is unique. Indeed, in our example a catamorphism for reductor is sumFold. Note how reductor and sumFold are similar: they have almost the same structure! In reductor definition s parameter usage (type of which corresponds to T) corresponds to usage of the result of computation of sumFold xs in sumFold definition.

Just to make it more clear and help you see the pattern, here is another example, and we again begin from the resulting folding function. Consider append function which appends its first argument to second one:

(append [4, 5, 6]) [1, 2, 3] = (foldr (:) [4, 5, 6]) [1, 2, 3] -> [1, 2, 3, 4, 5, 6]

This how it looks on our IntList:

appendFold :: IntList -> IntList -> IntList
appendFold ys ()          = ys
appendFold ys (Cons x xs) = x : appendFold ys xs

Again, let's try to write out the reductor:

appendReductor :: IntList -> () | (Int × IntList) -> IntList
appendReductor ys ()      = ys
appendReductor ys (x, rs) = x : rs

appendFold is a catamorphism for appendReductor which transforms IntList into IntList.

So, essentially, F-algebras allow us to define 'folds' on recursive datastructures, that is, operations which reduce our structures to some value.

F-coalgebras

F-coalgebras are so-called 'dual' term for F-algebras. They allow us to define unfolds for recursive datatypes, that is, a way to construct recursive structures from some value.

Suppose you have the following type:

data IntStream = Cons (Int, IntStream)

This is an infinite stream of integers. Its only constructor has the following type:

Cons :: (Int, IntStream) -> IntStream

Or, in terms of sets

Cons :: Int × IntStream -> IntStream

Haskell allows you to pattern match on data constructors, so you can define the following functions working on IntStreams:

head :: IntStream -> Int
head (Cons (x, xs)) = x

tail :: IntStream -> IntStream
tail (Cons (x, xs)) = xs

You can naturally 'join' these functions into single function of type IntStream -> Int × IntStream:

head&tail :: IntStream -> Int × IntStream
head&tail (Cons (x, xs)) = (x, xs)

Notice how the result of the function coincides with algebraic representation of our IntStream type. Similar thing can also be done for other recursive data types. Maybe you already have noticed the pattern. I'm referring to a family of functions of type

g :: T -> F T

where T is some type. From now on we will define

F1 T = Int × T

Now, F-coalgebra is a pair (T, g), where T is a type and g is a function of type g :: T -> F T. For example, (IntStream, head&tail) is an F1-coalgebra. Again, just as in F-algebras, g and T can be arbitrary, for example,(String, h :: String -> Int x String) is also an F1-coalgebra for some h.

Among all F-coalgebras there are so-called terminal F-coalgebras, which are dual to initial F-algebras. For example, IntStream is a terminal F-coalgebra. This means that for every type T and for every function p :: T -> F1 T there exist a function, called anamorphism, which converts T to IntStream, and such function is unique.

Consider the following function, which generates a stream of successive integers starting from the given one:

nats :: Int -> IntStream
nats n = Cons (n, nats (n+1))

Now let's inspect a function natsBuilder :: Int -> F1 Int, that is, natsBuilder :: Int -> Int × Int:

natsBuilder :: Int -> Int × Int
natsBuilder n = (n, n+1)

Again, we can see some similarity between nats and natsBuilder. It is very similar to the connection we have observed with reductors and folds earlier. nats is an anamorphism for natsBuilder.

Another example, a function which takes a value and a function and returns a stream of successive applications of the function to the value:

iterate :: (Int -> Int) -> Int -> IntStream
iterate f n = Cons (n, iterate f (f n))

Its builder function is the following one:

iterateBuilder :: (Int -> Int) -> Int -> Int × Int
iterateBuilder f n = (n, f n)

Then iterate is an anamorphism for iterateBuilder.

Conclusion

So, in short, F-algebras allow to define folds, that is, operations which reduce recursive structure down into a single value, and F-coalgebras allow to do the opposite: construct a [potentially] infinite structure from a single value.

In fact in Haskell F-algebras and F-coalgebras coincide. This is a very nice property which is a consequence of presence of 'bottom' value in each type. So in Haskell both folds and unfolds can be created for every recursive type. However, theoretical model behind this is more complex than the one I have presented above, so I deliberately have avoided it.

Hope this helps.

Solution 3

Going through the tutorial paper A tutorial on (co)algebras and (co)induction should give you some insight about co-algebra in computer science.

Below is a citation of it to convince you,

In general terms, a program in some programming language manipulates data. During the development of computer science over the past few decades it became clear that an abstract description of these data is desirable, for example to ensure that one's program does not depend on the particular representation of the data on which it operates. Also, such abstractness facilitates correctness proofs.
This desire led to the use of algebraic methods in computer science, in a branch called algebraic specification or abstract data type theory. The object of study are data types in themselves, using notions of techniques which are familiar from algebra. The data types used by computer scientists are often generated from a given collection of (constructor) operations,and it is for this reason that "initiality" of algebras plays such an important role.
Standard algebraic techniques have proved useful in capturing various essential aspects of data structures used in computer science. But it turned out to be difficult to algebraically describe some of the inherently dynamical structures occurring in computing. Such structures usually involve a notion of state, which can be transformed in various ways. Formal approaches to such state-based dynamical systems generally make use of automata or transition systems, as classical early references.
During the last decade the insight gradually grew that such state-based systems should not be described as algebras, but as so-called co-algebras. These are the formal dual of algebras, in a way which will be made precise in this tutorial. The dual property of "initiality" for algebras, namely finality turned out to be crucial for such co-algebras. And the logical reasoning principle that is needed for such final co-algebras is not induction but co-induction.

---

Prelude, about Category theory. Category theory should be rename theory of functors. As categories are what one must define in order to define functors. (Moreover, functors are what one must define in order to define natural transformations.)

What's a functor? It's a transformation from one set to another which preserving their structure. (For more detail there is a lot of good description on the net).

What's is an F-algebra? It's the algebra of functor. It's just the study of the universal propriety of functor.

How can it be link to computer science ? Program can be view as a structured set of information. Program's execution correspond to modification of this structured set of information. It sound good that execution should preserve the program structure. Then execution can be view as the application of a functor over this set of information. (The one defining the program).

Why F-co-algebra ? Program are dual by essence as they are describe by information and they act on it. Then mainly the information which compose program and make them changed can be view in two way.

• Data which can be define as the information being processed by the program.
• State which can be define as the information being shared by the program.

Then at this stage, I'd like to say that,

• F-algebra is the study of functorial transformation acting over Data's Universe (as been defined here).
• F-co-algebras is the study of functorial transformation acting on State's Universe (as been defined here).

During the life of a program, data and state co-exist, and they complete each other. They are dual.

Solution 4

I'll start with stuff that is obviously programming-related and then add on some mathematics stuff, to keep it as concrete and down-to-earth as I can.

---

Let's quote some computer-scientists on coinduction…

http://www.cs.umd.edu/~micinski/posts/2012-09-04-on-understanding-coinduction.html

Induction is about finite data, co-induction is about infinite data.

The typical example of infinite data is the type of a lazy list (a stream). For example, lets say that we have the following object in memory:

 let (pi : int list) = (* some function which computes the digits of
 π. *)

The computer can’t hold all of π, because it only has a finite amount of memory! But what it can do is hold a finite program, which will produce any arbitrarily long expansion of π that you desire. As long as you only use finite pieces of the list, you can compute with that infinite list as much as you need.

However, consider the following program:

let print_third_element (k : int list) =   match k with
     | _ :: _ :: thd :: tl -> print thd


 print_third_element pi

This program should print the third digit of pi. But in some languages, any argument to a function is evaluated before being passed into a function (strict, not lazy, evaluation). If we use this reduction order, then our above program will run forever computing the digits of pi before it can be passed to our printer function (which never happens). Since the machine does not have infinite memory, the program will eventually run out of memory and crash. This might not be the best evaluation order.

http://adam.chlipala.net/cpdt/html/Coinductive.html

In lazy functional programming languages like Haskell, infinite data structures are everywhere. Infinite lists and more exotic datatypes provide convenient abstractions for communication between parts of a program. Achieving similar convenience without infinite lazy structures would, in many cases, require acrobatic inversions of control flow.

http://www.alexandrasilva.org/#/talks.html

---

Relating the ambient mathematical context to usual programming tasks

What is "an algebra"?

Algebraic structures generally look like:

1. Stuff
2. What the stuff can do

This should sound like objects with 1. properties and 2. methods. Or even better, it should sound like type signatures.

Standard mathematical examples include monoid ⊃ group ⊃ vector-space ⊃ "an algebra". Monoids are like automata: sequences of verbs (eg, f.g.h.h.nothing.f.g.f). A git log that always adds history and never deletes it would be a monoid but not a group. If you add inverses (eg negative numbers, fractions, roots, deleting accumulated history, un-shattering a broken mirror) you get a group.

Groups contain things that can be added or subtracted together. For example Durations can be added together. (But Dates cannot.) Durations live in a vector-space (not just a group) because they can also be scaled by outside numbers. (A type signature of scaling :: (Number,Duration) → Duration.)

Algebras ⊂ vector-spaces can do yet another thing: there’s some m :: (T,T) → T. Call this "multiplication" or don't, because once you leave Integers it’s less obvious what "multiplication" (or "exponentiation") should be.

(This is why people look to (category-theoretic) universal properties: to tell them what multiplication should do or be like:

)

---

Algebras → Coalgebras

Comultiplication is easier to define in a way that feels non-arbitrary, than is multiplication, because to go from T → (T,T) you can just repeat the same element. ("diagonal map" – like diagonal matrices/operators in spectral theory)

Counit is usually the trace (sum of diagonal entries), although again what's important is what your counit does; trace is just a good answer for matrices.

The reason to look at a dual space, in general, is because it's easier to think in that space. For example it's sometimes easier to think about a normal vector than about the plane it's normal to, but you can control planes (including hyperplanes) with vectors (and now I'm speaking of the familiar geometric vector, like in a ray-tracer).

---

Taming (un)structured data

Mathematicians might be modelling something fun like TQFT's, whereas programmers have to wrestle with

• dates/times (+ :: (Date,Duration) → Date),
• places (Paris ≠ (+48.8567,+2.3508)! It's a shape, not a point.),
• unstructured JSON which is supposed to be consistent in some sense,
• wrong-but-close XML,
• incredibly complex GIS data which should satisfy loads of sensible relations,
• regular expressions which meant something to you, but mean considerably less to perl.
• CRM that should hold all the executive's phone numbers and villa locations, his (now ex-) wife and kids' names, birthday and all the previous gifts, each of which should satisfy "obvious" relations (obvious to the customer) which are incredibly hard to code up,
• .....

Computer scientists, when talking about coalgebras, usually have set-ish operations in mind, like Cartesian product. I believe this is what people mean when they say like "Algebras are coalgebras in Haskell". But to the extent that programmers have to model complex data-types like Place, Date/Time, and Customer—and make those models look as much like the real world (or at least the end-user's view of the real world) as possible—I believe duals, could be useful beyond only set-world.

View more solutions

Comments

[Luis Casillas]

This is incredibly valuable. I'd managed to vague up some intuitions about this whole F-algebra business from reading and examples (e.g., from seeing their use with catamoprhisms), but this is just all crystal clear even to me. Thanks!

[Edward Kmett]

This is a great explanation.

[Tikhon Jelvis]

@EdwardKmett: Thanks. Is the stuff I added about classes and objects okay? I only read about it today, but it seems to make sense.

[Kristopher Micinski]

The explanation by analogy to classes is something that seems nonstandard (although I know there are papers on the topic!). I think the more common (and for me, easier to understand) analogy is considering infinite structures, where coalgebras observe codata.

[Tikhon Jelvis]

@KristopherMicinski: Right. I brought up the classes and objects because the question mentioned objects explicitly. I was actually also introduced to the topic via codata and only read about the classes/objects today.

[John Wiegley]

This is such a good exposition, Tikhon, thank you so much! I've seen parts of this said in so many different ways, but never until now did it make so much sense. You've made the concept of an algebra perfectly clear. I'm still fuzzy on coalgebras (the OOP analogy didn't really help me), but the fact that it just flips the arrows means it can't be too much harder. I also kept expecting you to tie the concept of mutating object state in with Edward's lens library, as it represents just such a coalgebra.

[C. A. McCann]

For what it's worth: The "category of endofunctors" here is more precisely a category whose objects are endofunctors on some category and whose arrows are natural transformations. This is a monoidal category, with functor composition corresponding to (,) and the identity functor to (). A monoid object within a monoidal category is an object with arrows corresponding to your monoid algebra, which describes a monoid object in Hask with product types as the monoidal structure. A monoid object in the category of endofunctors on C is a monad on C, so yes, your understanding is correct. :]

[Anthony]

This is one of the most valuable things I've ever seen on Stack Overflow! @C.A.McCann: Thank you for the clarification. It was much appreciated here.

[Anthony]

Does anyone know how (if at all) this explanation relates (if at all) to poly-categories? It feels very related, using type class contexts like that.

[C. A. McCann]

@Anthony: The only thing called 'polycategories' that I know of doesn't seem to have any relevance here. Could you clarify what connection you're seeing?

[Anthony]

@C.A.McCann: I'm still vague on this, but check out: ΣΠ-Polycategories, Additive Linear Logic, and Process Semantics. I think I see two connections here... one is the more obvious: that type classes can be seen as polycategories (as Pastro describes them), although this may simply overcomplicate things more than necessary; and the other is the more vague/cloudy (in my mind) relation between coalgebras, process calculi and linear logic to what was said above.

[C. A. McCann]

@Anthony: I'll have to take a look at the paper because I'm really not seeing the connection immediately. I gather that's only talking about the additive fragment of linear logic?

[Anthony]

@C.A.McCann: the connection regarding type classes is just that filly applied type-classes can be interpreted as a judgements in a sequent calculus. Polycategories seem to be a good model for sequent calculi, as shown by this paper. A reference on how type-class checking may look if one chose to go that route: comonad.com/reader/2012/… ; Anyway, yes it's only the additive fragment in this paper, given a polycategorical presentation, in this case, again to construct process calculi based on ALL.

[Anthony]

if anyone else is interested in this application of polycategories to sequent calculi Benton, Bierman, Paiva and Hyland. Linear \lambda-calculus and Categorical Models Revisited. is much shorter. For @C.A.McCann: this one covers the MELL fragment.

[fedvasu]

"A comonad is just a coalgebra in the category of endofunctors." Thanks for this superb troll-tagline.

[Mysterious Dan]

I haven't worked through your conclusion yet, but how can a comonad just be a coalgebra in a category of endofunctors if it has laws? (co)algebras have no associated laws.

[Mysterious Dan]

Okay, the more I look at the last line, the less correct it seems. If you drop the "just", I'll buy it, but being a coalgebra in endofunctors does not define being a comonad, unlike the obvious parallel being drawn to the usual "a monad is a monoid object in endofunctors".

[Tikhon Jelvis]

@MyseriousDan: You're probably right there. I didn't mean "just" as in "only" as much as "simply", but I can see how it's confusing.

[Mysterious Dan]

Cool, thanks :) If I had my way, I'd add a parenthetical statement saying "(with a few extra laws)" or something more pithy. Every comonad is a functor, for example, but they have some extra properties too.

[Eran]

Excellent answer! Reading the part about transforming any algebra to a sum type which is a functor instance was an aha moment for me. Do you have any references for it, or a "mathy" equivalent of it?

[Tikhon Jelvis]

@Eran: I'm not sure exactly what you're looking for. Is it about how you can combine multiple functions into one using a sum type? In that case, take a look at the definition of products and co-products in category theory: as the name implies, product types (e.g. tuples) are products and sum types are co-products. Both of these are universal constructions that also appear in other categories--for example, in the category created by elements of a partially ordered set, products and coproducts correspond to the lattice operations.

[Eran]

@TikhonJelvis I'm trying to understand algebraic semantics of computation and their generalization in the setting of category theory, so I was looking for references to seminal papers. It turns out the "mathy equivalent" I was looking for was the signature and how F-(co)algebras denote all signatures in a single function (functor) which is a sum (co-product) of products. This also ties back nicely to how algebras formalize algebraic data types. I'm pretty sure there's more category theory goodness to grok here but this is probably out of the scope for this discussion.

[lester]

Many thanks for the useful and detailed explanation! Best answer on SO for me too!

[imz -- Ivan Zakharyaschev]

So, coalgebras seem to fit as a better, first-class substitute of Haskell modules, so that we can construct various coalgebras satisfying an interface (= a signature, or better -- a "cosignature"? Since a "signature" is what an algebra has) and pass them as parameters to functions which depend the particular interface of a module that wish to use...

[imz -- Ivan Zakharyaschev]

To match OOP, we should have a guarantee that once we have called setPosition on an object once, we won't call it another time on that same "old" state of the object: we must use the "updated" state. In Haskell, it's a familiar problem similar to the one solved by IO monad. So, to simulate OOP, we should somehow restrict CoAlgebra uses by a monad, shouldn't we? (For example, if the CoAlgebra is a Haskell interface to a real foreign OOP system.)

[Max Galkin]

The type and definition of appendReductor looks a bit strange and didn't really help me see the pattern there... :) Can you double-check that it is correct?.. What should reductor types look like in general? In the definition of r there, is F1 determined by the IntList, or is it an arbitrary F?

[Florian F]

Great explanation already of F-Algebras. But a bit confusing is the part where you define fmap f and then Functor f, both having a f τ but where both f and τ have different meanings.