Category theory for beginners
slideshare.net
slideshare.net
[1]: http://www.amazon.com/Algebra-Chapter-Graduate-Studies-Mathe...
[2]: http://jeremykun.com/2013/04/24/introducing-categories/
It's like learning music theory without ever composing and performing. It's like being a eunuchs in a harem; knowing how it's done, seeing it done, but unable to actually do it.[0] You need to do it to gain any real understanding and/or ability.
It's like reading about programming, but never actually writing programs.
[0] http://www.goodreads.com/quotes/33229-critics-are-like-eunuc...
j2kun's site [2] is highly recommended for anyone looking for a foothold into CT. It begins with a brief look at the universal property of free monoids (by implementing lift for lists), followed by various constructions (many in the category of Set). It (currently) ends with a discussion of map, filter, and (the universal property) of fold. Some constructions/proofs are provided in ML (which I've been meaning to get acquainted with (and while "clunky" is better suited than Haskell for the intended purpose, imo)).
So yeah, thanks again! I hope you get time to continue the series...
Firstly, thanks for all your great stuff on Math/Programming, it's been a great source of inspiration!
I would have liked to include Universal Properties, but I decided it was just too much to grasp for one session.
The audience were professional programmers, so there was a strong underlying message of "this is directly applicable to what you do". UMPs have got something important to say about abstraction -- what it means to have only what you need and no more. It just would have popped heads by the time I'd built up to it.
Cheers! Keep up the blogging :)
I look forward to reading the code parts.
But I have to agree with other posters - it took a lot of studying to get to the point where I can understand your slides. I think by the time you can read mathematics like this, it is because you already understand it verbosely.
As for people who don't agree that this is for beginners, I don't think you will be able to feel like you get it until you sit down with the work and stare at it a lot until it makes sense to you. It sounds stupid and silly, but that's the only way I can really communicate how to learn this stuff with a feeling of adequate understanding. The simplicity and elegance of the pictures do not adequately convey how difficult this stuff is to comprehend, especially if your mathematical foundation involves reasoning about real things. It is descriptive of abstract layers of terms, and the relationships they construct. Category theory is essentially the math of maths.
Instead of clicking through a 209-slide PowerPoint presentation you likely won't be able understand, I suggest reading these free books on those subjects:
http://www.fecundity.com/codex/forallx.pdf
> Bottom is a member of any type, even the trivial type () [...] If it were not, the compiler could solve the halting problem and statically determine whether any computation terminated
You can imagine function composition and identity don't work too well on things that never complete.
1) Programming is maths 2) Programming is about abstraction and finding patterns 3) CT describes abstract patterns in maths, and is therefore directly applicable to everyday programming. 4) (Exposition of Categories, Functors, Monoids) 5) Comparison of the mathematical concepts to equivalent programming concepts 6) Composability is a huge advantage for software in the large and the small; categories and monoids capture the essence of composable patterns. 7) Abstraction is hugely important for software; it allows to only know what we need, and no more. Category Theory gives us deeper, and dare I say, simpler abstractions. We can find underlying patterns and commonalities that we might have missed otherwise.
Trivial examples are things like Map-Reduce, the first step describes is done by applying a monoidal functor
T B -> T A,
the fact that the functor is monoidal allows for the work to be distributed across lots of nodes with no communication, the second step uses some associative algebra
T A -> A
to compute the final result, associativity allows for easily parallizable computation of subresults.
They start off with objects, what are they? Are they sets? I'm going to assume they're sets. Then the arrows represent mappings, something like a function that takes an input and maps to stuff in one of those other objects (set of objects?). Then the codomain is the set of objects you can get to by calling that function on the domain of objects.
Am I in the right ball-park here?
Treat objects and arrows abstractly like you're building a graph. Actual meaning can be applied later. A category is thus a set (or proper class) of objects, O, and a set (or proper class) of arrows, A along with two mappings dom and cod from A -> O. The laws are first that for any object (o in O) there exists an arrow (id(o) in A) such that dom(id(o)) = o and cod(id(o)) = o and second that if you have two arrows (f, g in A) such that cod(f) = dom(g) then there is defined their composition (compose(f,g) in A) such that dom(compose(f,g)) = dom(f) and cod(compose(f,g)) = cod(g).
You can draw all that as the objects and arrows and things these slides display. So far this just gives you a graph-like structure.
The "category laws" ensure coherence of the category and state that (compose(f, id(x)) = f) when defined, (compose(id(x), g) = g) when defined, and that compose is associative. From an abstract algebraic POV this is almost like saying that A is a monoid which ought to (correctly) suggest that most of the interesting structure of a category is carried by the arrows.
Now, if you want to talk about specific categories you can do what you were doing. For instance, the category of sets, Set, is the category where you take O to be the proper class of all sets and A to be the functions between them. Immediately, you'll find that dom(.)/cod(.) are the domain and codomain of your functions, id(.) locates the identity function on a set, and compose(.,.) composes functions.
As a more interesting example you could consider Grp the category where O is all groups and A is all group homomorphisms. This is a subcategory of Set obviously and it also comes with much more interesting structure. For instance, an important category theoretic statement about Grp is that Grp has a "zero object", which is to say that (a) there exists an object init such that there is a unique arrow from init to any other object, (b) there exists an object fin such that there is a unique arrow from any other object to fin, and (c) init = fin.
The objects here are not necessarily sets, and the arrows are not necessarily functions -- this is actually one of the points of category theory, to abstract the notion of morphism away from set theory. This becomes necessary, when in your regular mathematical life you encounter morphisms which are not strictly functions, but nevertheless in many ways behave as such. Best example would be the homotopy classes of maps between topological spaces. Homotopy classes do not map points from domain space to codomain space, but nevertheless you can compose them, there's a homotopy class of identity, which acts as an identity on composition, sometimes there are homotopy classes that are inverses and so on.
If this sounds complicated and unnatural, that's because it is: it is pointless to learn category theory before learning where and how it is useful. This is completely opposite order than in which it was conceived, and totally misses the purpose the category theory, which is to make everything clearer, to reduce the number of notions, to make it easier to notice analogous behavior between separate concepts, to reduce number of repeating arguments. Learning what a morphism or functor or natural transformation is, without having tens of examples of these notions, only increases the number of concepts without a corresponding increase in understanding.
My advice is, if you want to learn category theory, learn algebraic topology first, or at least abstract algebra (groups, rings, modules, fields). Otherwise, you'll see very little purpose, and very little use.
While not strictly necessary, learning a bit of category theory makes FP abstractions such as functors and monoids a bit more accessible.
I can't disagree with the fact that learning category for that sole purpose sounds like a lot of work for too little benefit, though.
A category that captures the notion of sets and maps can be described in terms of arrows, objects and some semantic rules about which arrows (here interpreted as maps) connect which objects (here interpreted as sets).
Wiki on the "Category of sets [and maps]" -> http://en.wikipedia.org/wiki/Category_of_sets
Other rules about arrows between objects describe categories that capture other mathematical concepts.
I'm no expert, but from my understanding, there is nothing more to be said (other than stating the composition / identity laws): you're at a level of abstraction where you cannot say anything more. Objects. Arrows. An arrow goes from an object to another.
If it's any help, you can think of them as mathematical functions, where the origin point is the function's domain and its destination point the function's range (called co-domain in category theory, because why not).
Bear in mind that while this example is correct, that's all it is: a concrete example of an abstract notion.
If it feels simplistic, that's because it is. Arrows are a trivial notion. It gets more complicated when you study different kinds of arrows (homomorphism, isomorphism, whateverism), or arrows in "concrete" categories (functors are arrows in the category of categories, natural transformations are arrows between functors...).
In the book "Conceptual Mathematics" the concrete example is finite sets and mapping between finite sets. That is way more understandable than 'objects' and 'how to go from one object to another'. It's just too abstract for a general audience I believe.
Conceptual Mathematics needs concrete example to explain the algebra of function composition, and more importantly to prove certain properties and theorems. This presentation's goals are far more modest and the abstract approach allows it to not take up 700 slides.
That being said, I don't think I'd have been able to go through this presentation in its entirety if I hadn't had some previous exposure to the field. So while I disagree with you for discussion's sake, I secretly think you're right.
The point of these instructional methods is to build an 'intuitive sense' or "system 1" knowledge of category theory. Having a lot of easy to grasp examples to help you start forming the theory in your head i find quite valuable.
Moreover for every object A, there is an identity arrow. Composition with that does yield the original arrow.
The point of those axioms is that they are satisfied by lots of different mathematical structures and idealized physical situations as well (Feynman diagrams, Chemical reaction networks, Knot-/Braid diagrams etc.).
For how this relates to computation, you can look at http://math.ucr.edu/home/baez/qg-fall2006/index.html#computa... for example. It is a bit more subtle than one would think at first, as in functional programming languages with "first class" functions, those are not not actually arrows, but objects. More precisely the type (A -> B) in Haskell, or (A=>B) in Scala, is a notation for an internal hom object.
The more interesting ideas arise when you then study how different such categories relate to each other, you then come up with Functors and how Functors between Categories are related to each other, those are called Natural Transformations. The original motivation for the invention of category theory was the study of natural transformations in homological algebra and algebraic topology. In the preceding years people had come up with several alternative functors (Cohomology / Homology on certain topological spaces) and they needed a way to talk about in what way those constructions were equivalent to each other.
The air is thinner near the top of the abstraction ladder and more or less unbreathable for people who don't spend considerable time in the Ivory Tower.
For example, in a category of "types", each object could be a type (e.g.: int, float, list(int), etc.), and each arrow could be a function between those types.
With that example, just think of all the arrows between, say, string -> int! There's "length()", "md5()", "to_i()", etc. And don't even get me started on the "identity" arrows of string back to itself (upcase, downcase, strip, etc). We're talking gazillions of arrows.
f:B->A and g:A->C
(P1) id . f = f and (P2) g . id = g, in particular it is unique, since if id':A->A had the same property, then
id' = id . id' = id,
where the first equality follows by (P1) and the second by (P2').
It groups functional operations into kinds that you can make assertions about after a selection of the operations have been performed.
Haskell does -
add :: Integer -> Integer -> Integer
so the compiler can check all the branches of code to ensure that statement is invariant.
Definition: A group is a category with a single object, all of whose morphisms are both epic[1] and monic[2].
In particular, if you drop the epic and monic requirements, a category that has only one object can be viewed as a monoid[3] under morphism composition.
[1]: http://en.wikipedia.org/wiki/Epimorphism
I don't have a math background, but write a lot of Scala anyway. These slides filled in the blanks in a lot of places for me though largely because I could relate to how I've written code.
This is an excellent resource and its piqued my interest in learning more about category theory.
[1] http://bartoszmilewski.com/2014/10/28/category-theory-for-pr...
(I'm very new to this topic, but I have an applied math background.)
I don't think anything in this definition allows us to conclude that there can only be one such f between A and B. Indeed, if A and B are sets of identical cardinality, I'm pretty sure you can create n! isomorphims between the two (where n=|A|). Drawing a picture of of two sets with two elements each should let you see it.
One thing to remember is that each slide had a lot of verbal explanation around it, so I'm not surprised that it's confusing by itself!
We took a video, so hopefully it turns out OK so we can put it online.
I know what map does and I know what a functor is, but I don't know scala, so I can't understand what the slides are saying.
Functor[F[_]] to the right of the name indicate that the type Functor is paramterized across a "higher kinded type" (ie it is generic and the thing it is generic against is in turn generic). For this definition we will refer to that higher kinded type as F[_].
def defines a method on the type. So def map means that the type Functor has a method map on it. map[A, B] means that the function map is generic across 2 different types and we will label them A & B. Map takes 2 parameters the first is the higher kinded type F parameterized to A (F of A) and the second is a function that transforms any A to a B. Map returns F parameterized to B.
Slide 92 defines it slightly differently. Map is a function with no parameters that returns a function with the first (and only parameter) is a function from A to B and it returns a function from F[A] to F[B].
The return type is at the end of the function definition, preceded by : . It's optional if there is an implementation provided, as Scala can do type inference.
The => is a shorthand for defining a function type. String => Int is a function that takes a String, and returns an Int.
[A,B] is saying that the function is a generic function, with some generic types named A and B, that will be resolved at compile time. Not unlike generics in many other languages.
so def map[A,B] (fa: F[A], f: A=>B) : F[B] means that we are defining a function map, that takes a Functor of A fa, and a function from A to B, and returns a functor of type F[B].
Slide 92 writes it differently:
def map[A,B] : (A=>B) => (F[A] => F[B])
Here, map returns a function that takes a function from A to B, and returns another function, that turns a Functor of A into a functor of B.
Now, knowing functors and scala, I don't find those slides that illuminating anyway. I did not think that I'd ever say this about anything, but here it goes. I think Scalaz's implementation is easier to understand.
Slide 90 is straightforward: Functor is a trait (sort of like an abstract class) that takes a type parameter F, where F is a type constructor that takes one type parameter.
Examples of such type constructors are List (used to create List[Int], List[String], ...), Set (Set[Int]...), Option (Option[String])...
The Functor trait declares a map method that, for any two types A and B, take an instance of F[A], a function from A to B and returns an instance of F[B].
A concrete example: F is List, A is String and B is Int. map takes a list of strings, applies a function that turns strings to ints (say, strlen), and returns a list of ints - the Functor instance for List replaces each of its elements by applying the specified function to it.
A functor in FP really is an endofunctor in the category of types, in which:
- objects are concrete types
- arrows are unary functions
That is, a functor in FP must map:
- concrete types to concrete types
- unary functions to unary functions.
In slide 91, you see that map maps instances of concrete type F[A] to concrete type F[B] - List[String] to List[Int], for example.
In slide 92, you "see" that map maps functions from A to B to functions from F[A] to F[B] - it lifts strlen into a function that takes a List[String] and returns a List[Int].
I'm assuming that slide 92 is meant to show partial application of map, but it really could be made clearer. The author probably explains things more while giving the presentation, but the shift from slide 91 to 92 really is a bit handwavy and magical.
Hope this clarified things a bit, but feel free to ask for more if not, I'd be happy to expand on / correct the parts that you still find obscure.
Just one question to check my understanding. That definition of a Functor is not completely general right? Since it always takes an object _ to an object F[_].
Like one functor could be to compose an arrow with addition of 0.5 . And that would map X->int arrows to X->double arrows, right? But that would not be compatibe with the Functor trait?
First, a functor doesn't go from A to F[B] but from F[A] to F[B]. A to F[B] looks suspiciously like something a monad does, a topic we don't want to get into.
Your example is a functor that maps unary functions to unary functions by composing them. It's a good if slightly complicated example: unary functions have two type parameters (A and B in A => B), while the slide's Functor only takes one. That is, you want to write a Functor[A => B], but you cannot, or at least not directly.
What you do is fix one of the parameters. You don't write a Functor for all unary functions, but a Functor for all unary functions whose parameter type is C (for concrete): Functor[C => A], where C is a concrete type and A the functor's type parameter.
This functor's map method takes an instance of (C => A), a function f: A => B, and yields a function C => B. The only non-pathological implementation of this is composition: C => A => B
What I just wrote makes it sound like you need to write a Functor implementation for all possible parameter types, but that luckily isn't true: writing a function that yields a Functor[C => A] for any given type parameter C is trivial. I'll put the code here just to show it is, but you don't really need to understand it:
// I know the C => ? isn't standard Scala, I'm using kind-projector syntax to make this readable. implicit def functionFunctor[C] = new Functor[C => ?] { override def map[A, B](fa: C => A)(f: A => B): C => B = f compose fa }
To go back to your concrete example: you just need to get functionFunctor[X] and call map on (x => x * 0.5) to get your function from X to double. Note that some technical details are skipped (partial application, calling the binary function map with a single parameter), but I arbitrarily deem them irrelevant to my point.
I used the word "object" like it is used in slide 55. Functors map objects to objects and arrows to arrows. I.e. arrow is the (co)domain of the functor, and object is the (co)domain of the (co)domain of the functor.