StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
16022059
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
27
CommunityOwnedDate
CreationDate
2013-04-15T18:17:28.103
FavoriteCount
0
LastActivityDate
2013-05-07T16:26:57.483
LastEditDate
2013-05-07T16:26:57.483
LastEditorUserId
286871
OwnerUserId
286871
ParentId
16015020
PostTypeId
2
Score
450
ViewCount
0
LastEditorDisplayName
text
Body
<h1>Algebras</h1> 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 <code>τ</code> with some functions and identities. These functions take differing numbers of arguments of type <code>τ</code> and produce a <code>τ</code>: uncurried, they all look like <code>(τ, τ,…, τ) → τ</code>. They can also have "identities"—elements of <code>τ</code> that have special behavior with some of the functions. The simplest example of this is the monoid. A monoid is any type <code>τ</code> with a function <code>mappend ∷ (τ, τ) → τ</code> and an identity <code>mzero ∷ τ</code>. Other examples include things like groups (which are just like monoids except with an extra <code>invert ∷ τ → τ</code> function), rings, lattices and so on. All the functions operate on <code>τ</code> but can have different arities. We can write these out as <code>τⁿ → τ</code>, where <code>τⁿ</code> maps to a tuple of <code>n</code> <code>τ</code>. This way, it makes sense to think of identities as <code>τ⁰ → τ</code> where <code>τ⁰</code> is just the empty tuple <code>()</code>. 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. <h2>F-Algebras</h2> However, we're not quite done with factoring. So far, we have a bunch of functions <code>τⁿ → τ</code>. We can actually do a neat trick to combine them all into one function. In particular, let's look at monoids: we have <code>mappend ∷ (τ, τ) → τ</code> and <code>mempty ∷ () → τ</code>. We can turn these into a single function using a sum type—<code>Either</code>. It would look like this: <pre><code>op ∷ Monoid τ ⇒ Either (τ, τ) () → τ op (Left (a, b)) = mappend (a, b) op (Right ()) = mempty </code></pre> We can actually use this transformation repeatedly to combine all the <code>τⁿ → τ</code> functions into a single one, for any algebra. (In fact, we can do this for any number of functions <code>a → τ</code>, <code>b → τ</code> and so on for any <code>a, b,…</code>.) This lets us talk about algebras as a type <code>τ</code> with a single function from some mess of <code>Either</code>s to a single <code>τ</code>. For monoids, this mess is: <code>Either (τ, τ) ()</code>; for groups (which have an extra <code>τ → τ</code> operation), it's: <code>Either (Either (τ, τ) τ) ()</code>. 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 τ: <pre><code>data MonoidArgument τ = Mappend τ τ -- here τ τ is the same as (τ, τ) | Mempty -- here we can just leave the () out </code></pre> 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 <code>Functors</code>! E.g.: <pre><code>instance Functor MonoidArgument where fmap f (Mappend τ τ) = Mappend (f τ) (f τ) fmap f Mempty = Mempty </code></pre> So we can generalize our idea of an algebra even more. It's just some type <code>τ</code> with a function <code>f τ → τ</code> for some functor <code>f</code>. In fact, we could write this out as a typeclass: <pre><code>class Functor f ⇒ Algebra f τ where op ∷ f τ → τ </code></pre> This is often called an "F-algebra" because it's determined by the functor <code>F</code>. If we could partially apply typeclasses, we could define something like <code>class Monoid = Algebra MonoidArgument</code>. <h1>Coalgebras</h1> 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: <pre><code>class Functor f ⇒ CoAlgebra f τ where coop ∷ τ → f τ </code></pre> 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. <h2>Classes and Objects</h2> 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 <code>C</code> that contains all the possible internal states of objects in the class; the class itself is a coalgebra over <code>C</code> which specifies the methods and properties of the objects. As shown in the algebra example, if we have a bunch of functions like <code>a → τ</code> and <code>b → τ</code> for any <code>a, b,…</code>, we can combine them all into a single function using <code>Either</code>, a sum type. The dual "notion" would be combining a bunch of functions of type <code>τ → a</code>, <code>τ → b</code> and so on. We can do this using the dual of a sum type—a product type. So given the two functions above (called <code>f</code> and <code>g</code>), we can create a single one like so: <pre><code>both ∷ τ → (a, b) both x = (f x, g x) </code></pre> The type <code>(a, a)</code> 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 <code>τ → f τ</code>. The elements of our type <code>C</code> 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 <code>C</code>. So if we want a length property (e.g. <code>object.length</code>), we would have a function <code>C → Int</code>. 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 <code>C</code>. Let's imagine a <code>setPosition</code> method which takes an <code>x</code> and a <code>y</code> coordinate: <code>object.setPosition(1, 2)</code>. It would look like this: <code>C → ((Int, Int) → C)</code>. 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 <code>self</code> parameter in Python and like the implicit <code>this</code> of many other languages. A coalgebra essentially just encapsulates the behavior of taking a <code>self</code> parameter: that's what the first <code>C</code> in <code>C → F C</code> is. So let's put it all together. Let's imagine a class with a <code>position</code> property, a <code>name</code> property and <code>setPosition</code> function: <pre><code>class C private x, y : Int _name : String public name : String position : (Int, Int) setPosition : (Int, Int) → C </code></pre> 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 <code>Int</code>s and a <code>String</code>. (This is our type <code>C</code>.) Then we need to come up with the coalgebra representing the class. <pre><code>data C = Obj { x, y ∷ Int , _name ∷ String } </code></pre> We have two properties to write. They're pretty trivial: <pre><code>position ∷ C → (Int, Int) position self = (x self, y self) name ∷ C → String name self = _name self </code></pre> Now we just need to be able to update the position: <pre><code>setPosition ∷ C → (Int, Int) → C setPosition self (newX, newY) = self { x = newX, y = newY } </code></pre> This is just like a Python class with its explicit <code>self</code> variables. Now that we have a bunch of <code>self →</code> functions, we need to combine them into a single function for the coalgebra. We can do this with a simple tuple: <pre><code>coop ∷ C → ((Int, Int), String, (Int, Int) → C) coop self = (position self, name self, setPosition self) </code></pre> The type <code>((Int, Int), String, (Int, Int) → c)</code>—for any <code>c</code>—is a functor, so <code>coop</code> does have the form we want: <code>Functor f ⇒ C → f C</code>. Given this, <code>C</code> along with <code>coop</code> 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 <code>self</code> parameter containing each object's internal state. <h1>Other Categories</h1> So far, we've talked about algebras and coalgebras as Haskell types. An algebra is just a type <code>τ</code> with a function <code>f τ → τ</code> and a coalgebra is just a type <code>τ</code> with a function <code>τ → f τ</code>. 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 <code>C</code>. First, we need a functor <code>F : C → C</code>—that is, an endofunctor. (All Haskell <code>Functor</code>s are actually endofunctors from <code>Hask → Hask</code>.) Then, an algebra is just an object <code>A</code> from <code>C</code> with a morphism <code>F A → A</code>. A coalgebra is the same except with <code>A → F A</code>. 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 <code>M ∷ ★ → ★</code> with three operations: <pre><code>map ∷ (α → β) → (M α → M β) return ∷ α → M α join ∷ M (M α) → M α </code></pre> The <code>map</code> function is just a proof of the fact that <code>M</code> is a <code>Functor</code>. So we can say that a monad is just a functor with two operations: <code>return</code> and <code>join</code>. 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. <a href="http://lukepalmer.wordpress.com/2008/04/28/whats-a-natural-transformation/">Here's</a> a nice article helping explain the idea. It talks about <code>concat</code>, which is just <code>join</code> for lists. With Haskell functors, the composition of two functors is a functor itself. In pseudocode, we could write this: <pre><code>instance (Functor f, Functor g) ⇒ Functor (f ∘ g) where fmap fun x = fmap (fmap fun) x </code></pre> This helps us think about <code>join</code> as a mapping from <code>f ∘ f → f</code>. The type of <code>join</code> is <code>∀α. f (f α) → f α</code>. Intuitively, we can see how a function valid for all types <code>α</code> can be thought of as a transformation of <code>f</code>. <code>return</code> is a similar transformation. Its type is <code>∀α. α → f α</code>. This looks different—the first <code>α</code> is not "in" a functor! Happily, we can fix this by adding an identity functor there: <code>∀α. Identity α → f α</code>. So <code>return</code> is a transformation <code>Identity → f</code>. Now we can think about a monad as just an algebra based around some functor <code>f</code> with operations <code>f ∘ f → f</code> and <code>Identity → f</code>. Doesn't this look familiar? It's very similar to a monoid, which was just some type <code>τ</code> with operations <code>τ × τ → τ</code> and <code>() → τ</code>. 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: <code>f ∘ f → f</code> and <code>Identity → f</code>. To get the corresponding coalgebra, we just flip the arrows. This gives us two new operations: <code>f → f ∘ f</code> and <code>f → Identity</code>. We can turn them into Haskell types by adding type variables as above, giving us <code>∀α. f α → f (f α)</code> and <code>∀α. f α → α</code>. This looks just like the definition of a comonad: <pre><code>class Functor f ⇒ Comonad f where coreturn ∷ f α → α cojoin ∷ f α → f (f α) </code></pre> So a comonad is then a coalgebra in a category of endofunctors.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POWhat does "coalgebra" mean in the context of programming?
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USTikhon Jelvis
UserOwnerUserId
1. USTikhon Jelvis
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POWhat does "coalgebra" mean in the context of programming?
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.