サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
災害への備え
bartoszmilewski.com
You might have heard people say that functional programming is more academic, and real engineering is done in imperative style. I’m going to show you that real engineering is functional, and I’m going to illustrate it using a computer game that is designed by engineers for engineers. It’s a simulation game called Factorio, in which you are given resources that you have to explore, build factories
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
Abstract: I derive a free monoidal (applicative) functor as an initial algebra of a higher-order functor using Day convolution. I thought I was done with monoids for a while, after writing my Monoids on Steroids post, but I keep bumping into them. This time I read a paper by Capriotti and Kaposi about Free Applicative Functors and it got me thinking about the relationship between applicative and m
Stalking a Hylomorphism in the Wild Posted by Bartosz Milewski under Programming [22] Comments Trying to improve my Haskell coding skills, I decided to test myself at solving the 2017 Advent of Code problems. It’s been a lot of fun and a great learning experience. One problem in particular stood out for me because, for the first time, it let me apply, in anger, the ideas I learned from category th
Profunctor Optics: The Categorical View Posted by Bartosz Milewski under Category Theory, Lens, Programming [9] Comments Abstract: I present a uniform derivation of profunctor optics: isos, lenses, prisms, and grates based on the Yoneda lemma in the (enriched) profunctor category. In particular, lenses and prisms correspond to Tambara modules with the cartesian and cocartesian tensor product. This
This is part 25 of Categories for Programmers. Previously: F-Algebras. See the Table of Contents. If we interpret endofunctors as ways of defining expressions, algebras let us evaluate them and monads let us form and manipulate them. By combining algebras with monads we not only gain a lot of functionality but we can also answer a few interesting questions. One such question concerns the relation
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
Applicative Functors Posted by Bartosz Milewski under Category Theory, Functional Programming, Haskell, Type System [5] Comments Unlike monads, which came into programming straight from category theory, applicative functors have their origins in programming. McBride and Paterson introduced applicative functors as a programming pearl in their paper Applicative programming with effects. They also pr
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
Lenses: Yoneda with Adjunctions Posted by Bartosz Milewski under Category Theory, Haskell, Lens, Programming Leave a Comment In the previous post I explored the application of the Yoneda lemma in the functor category to derive some results from the Haskell lens library. In particular I derived the profunctor representation of isos. There is one more trick that is used in the lens library: combinin
Profunctor Polymorphism Posted by Bartosz Milewski under Category Theory, Haskell, Lens, Programming [6] Comments The connection between the Haskell lens library and category theory is a constant source of amazement to me. The most interesting part is that lenses are formulated in terms of higher order functions that are polymorphic in functors (or, more generally, profunctors). Consider, for inst
Adjunctions Posted by Bartosz Milewski under Category Theory, Functional Programming, Haskell, Programming [55] Comments This is part 18 of Categories for Programmers. Previously: It’s All About Morphisms. See the Table of Contents. In mathematics we have various ways of saying that one thing is like another. The strictest is equality. Two things are equal if there is no way to distinguish one fro
I came in contact with Tambara modules when working on a categorical understanding of lenses. They were first mentioned to me by Edward Kmett, who implemented their Haskell version, Data.Profunctor.Tambara. Recently I had a discussion with Russell O’Connor about profunctor lenses. He then had a discussion with James “xplat” Deikun, who again pointed out the importance of Tambara modules. That fina
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
Operads, Type Level Nats, and Tic-Tac-Toe Posted by Bartosz Milewski under Category Theory, Haskell, Programming [6] Comments This summer I spent some time talking with Edward Kmett about lots of things. (Which really means that he was talking and I was trying to keep up.) One of the topics was operads. The ideas behind operads are not that hard, if you’ve heard about category theory. But the Hask
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
This is part 14 of Categories for Programmers. Previously: Free Monoids. See the Table of Contents. It’s about time we had a little talk about sets. Mathematicians have a love/hate relationship with set theory. It’s the assembly language of mathematics — at least it used to be. Category theory tries to step away from set theory, to some extent. For instance, it’s a known fact that the set of all s
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,
次のページ
このページを最初にブックマークしてみませんか?
『 Bartosz Milewski's Programming Cafe』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く