はてなブックマーク

Defunctionalization and Freyd’s Theorem Posted by Bartosz Milewski under Category Theory, Programming [9] Comments The main idea of functional programming is to treat functions like any other data types. In particular, we want to be able to pass functions as arguments to other functions, return them as values, and store them in data structures. But what kind of data type is a function? It’s a type

Terminal Coalgebra as Directed Limit Posted by Bartosz Milewski under Programming 1 Comment Previously, we talked about the construction of initial algebras. The dual construction is that of terminal coalgebras. Just like an algebra can be used to fold a recursive data structure into a single value, a coalgebra can do the reverse: it lets us build a recursive data structure from a single seed. Her

Fixed Points and Diagonal Arguments Posted by Bartosz Milewski under Programming [5] Comments What does Gödel’s incompletness theorem, Russell’s paradox, Turing’s halting problem, and Cantor’s diagonal argument have to do with the fact that negation has no fixed point? The surprising answer is that they are all related through Lawvere’s fixed point theorem. Before we dive deep into category theory

Fibrations, Cleavages, and Lenses Posted by Bartosz Milewski under Programming [2] Comments In category theory, as in life, you spend half of your time trying to forget things, and half of the time trying to recover them. A morphism, the basic building block of every category, is like a defective isomorphism. It maps the initial state to the final state, but it provides no guarantees that you can

The Power of Adjunctions Posted by Bartosz Milewski under Category Theory, Monads, Programming [15] Comments In my previous blog post, Programming with Universal Constructions, I mentioned in passing that one-to-one mappings between sets of morphisms are often a manifestation of adjunctions between functors. In fact, an adjunction just extends a universal construction over the whole category (or t

Programming with Universal Constructions Posted by Bartosz Milewski under Programming 1 Comment As functional programmers we are interested in functions. Category theorists are similarly interested in morphisms. There is a slight difference in approach, though. A programmer must implement a function, whereas a mathematician is often satisfied with the proof of existence of a morphism (unless said

Promonads, Arrows, and Einstein Notation for Profunctors Posted by Bartosz Milewski under Category Theory, Haskell, Monads, Programming 1 Comment I’ve been working with profunctors lately. They are interesting beasts, both in category theory and in programming. In Haskell, they form the basis of profunctor optics–in particular the lens library. Profunctor Recap The categorical definition of a prof

Recursion Schemes for Higher Algebras Posted by Bartosz Milewski under Category Theory, Functional Programming, Haskell, Monads, Programming [4] Comments Abstract The use of free monads, free applicatives, and cofree comonads lets us separate the construction of (often effectful or context-dependent) computations from their interpretation. In this paper I show how the ad hoc process of writing int

Free Monoidal Functors, Categorically! Posted by Bartosz Milewski under Category Theory [14] Comments Functors from a monoidal category C to Set form a monoidal category with Day convolution as product. A monoid in this category is a lax monoidal functor. We define an initial algebra using a higher order functor and show that it corresponds to a free lax monoidal functor. Recently I’ve been obsess

This is part 24 of Categories for Programmers. Previously: Comonads. See the Table of Contents. We’ve seen several formulations of a monoid: as a set, as a single-object category, as an object in a monoidal category. How much more juice can we squeeze out of this simple concept? Let’s try. Take this definition of a monoid as a set m with a pair of functions: μ :: m × m -> m η :: 1 -> m Here, 1 is

If there is one structure that permeates category theory and, by implication, the whole of mathematics, it’s the monoid. To study the evolution of this concept is to study the power of abstraction and the idea of getting more for less, which is at the core of mathematics. When I say “evolution” I don’t necessarily mean chronological development. I’m looking at a monoid as if it were a life form ev

Monads Categorically Posted by Bartosz Milewski under Category Theory, Haskell, Monads, Programming [18] Comments This is part 22 of Categories for Programmers. Previously: Monads and Effects. See the Table of Contents. If you mention monads to a programmer, you’ll probably end up talking about effects. To a mathematician, monads are about algebras. We’ll talk about algebras later — they play an i

Yoneda Embedding Posted by Bartosz Milewski under Category Theory, Functional Programming, Haskell, Programming 1 Comment This is part 16 of Categories for Programmers. Previously: The Yoneda Lemma. See the Table of Contents. We’ve seen previously that, when we fix an object a in the category C, the mapping C(a, -) is a (covariant) functor from C to Set. x -> C(a, x) (The codomain is Set because t

The Yoneda Lemma Posted by Bartosz Milewski under Category Theory, Haskell, Programming [25] Comments This is part 15 of Categories for Programmers. Previously: Representable Functors. See the Table of Contents. Most constructions in category theory are generalizations of results from other more specific areas of mathematics. Things like products, coproducts, monoids, exponentials, etc., have been

From Lenses to Yoneda Embedding Posted by Bartosz Milewski under Category Theory, Functional Programming, Haskell, Lens, Programming [6] Comments Lenses are a fascinating subject. Edward Kmett’s lens library is an indispensable tool in every Haskell programmer’s toolbox. I set out to write this blog post with the goal of describing some new insights into their categorical interpretation, but then

Using Monads in C++ to Solve Constraints: 3. The Tale of Two Monads Posted by Bartosz Milewski under C++, Functional Programming, Programming Leave a Comment This is part 3 of the miniseries about solving a simple constraint-satisfaction problem: s e n d + m o r e --------- m o n e y using monads in C++. Previously: The State Monad A constraint satisfaction problem may be solved by brute force, by

Using Monads in C++ to Solve Constraints: 1. The List Monad Posted by Bartosz Milewski under C++, Functional Programming, Haskell, Monads, Programming [26] Comments I am sometimes asked by C++ programmers to give an example of a problem that can’t be solved without monads. This is the wrong kind of question — it’s like asking if there is a problem that can’t be solved without for loops. Obviously,