Right, so can someone explain what the hell these slides mean? I studied a lot of abstract mathematics at uni but I wasn't exposed to category theory, and these slides aren't helpful.
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.
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.
Ah, the joys of learning math from slides without the talk the slides were helpers to.
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.
They are arrows. Arrows and objects are the primitives of category theory, just like sets and set membership are the primitives of set theories (well most of them anyway).
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).
I think it's "explained" when you go from slide 6 to 7.
Slide 6: objects are points in space.
Slide 7: arrows are ways of transforming objects into other objects.
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...).
But is this the best pedagogical approach to teaching this area?
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.
It's the only one that does not require knowledge of other fields - not everyone knows set theory (although yes, almost everyone here probably knows enough).
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.
I found the 'requirement' of set theory in the book is very 'common sense' and doesnt really use any advanced knowledge. It depends greatly on finite sets, which is easily and intuitively drawable.
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.
All you really know about arrows, is that you can compose them if the tip of the first arrow fits into the tail of the second arrow, that is the first arrow is from A to B and the second from B to C, in a way that is associative, which means that if you have three arrows, it doesn't matter in which way you compose compose them.
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.
This is a top-down approach starting with CT fundamentals and connecting them to CS concepts/patterns after 150 slides.
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.
I think if I were attempting to make it more accessible for beginners, I would start with a concrete example of a category (like Set) and introduce the concepts in what is, for most people (programmers in particular) familiar territory, and then attempt to show how abstracting those concepts is useful and applicable in other situations.
I scanned through the first 50 slides or so. I've read and drawn out the first few chapters to myself of "Categories for the Working Mathematician", so for me - this was a very nice presentation that graphically illustrated the key forms and key semantics.
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.
These slides do the same misleading thing all the other slides I've looked at do: show examples where there are only an arrow or two between objects. I still don't really understand category theory, but one breakthrough I had was when I realized that two objects can (and often do) have LOTS (or even infinite) arrow between them.
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.
So, on slide 33, the "+1" and "bestFriend" arrows are identities of Int and Person? On slide 35 it says that identity is associated with the identity function, but to me that means a function that returns what you give it, rather than "+1", which gives you the next number. So the identity of Person just means any function with the type signature Person->Person?
I just sort of abstract over the specifics of the implementation of arrows and assume there is an arrow that denotes the 'kind' of arrow. Does it express a monotonic function (order preserving), does it express a non monotonic function (permutation of elements, ordering of computation of 'typical' threads).
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.
There's an old mathematical wive's tale about the professor who, on the beginning of the first day of an abstract algebra course, writes the following definition down on the board:
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.
A trait is a (possibly abstract) type definition. So trait Functor is defining a type definition for something called Functor.
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.
Well, they're a bit weird. I'm not sure why the signature of map magically changes between slide 91 and 92 and find it very confusing.
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?
I'll be using pseudo code and skip over some technical details that are entirely irrelevant to this conversation in my answer. I hope I understood your question correctly and not answering something else entirely.
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.
You misunderstand my question. I realize in hindsight how it was ambiguous.
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.
If I didn't have a couple years of shipping Scala code into production I'm not certain I'd understand the slides by themselves. (Having audio and/or video to go along with the slides would be a great help!)
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.
The best exposition I've found for demystifying category theory is the first few chapters of Paolo Aluffi's Algebra: Chapter 0 [1]. The central emphasis is on universal properties, which I see most treatments for beginners de-emphasize or ignore (as these slides do). From my experience, universal properties are the main tool for unifying and abstracting concepts into the language of categories. Aluffi uses category theory to unify the treatment of groups, rings, modules, linear algebra, and then goes on to more abstract category theory. I have also written a bit on this [2], regrettably choosing ML as the language of implementation.
Nothing in principle (I wrote the articles, after all). I just found it to be clunky. In particular, the signature and structure system made it needlessly difficult to express what I thought were simple things. And it was difficult to find resources due to standard ML not being widely used.
I found "Categories and Computer Science" by R. F. C. Walters to be the perfect complement to Chapter 0 as it's almost entirely proof and example driven.
From my experience, if you don't work through those proofs that are "left as exercise for reader" then you won't ever really come to understand the material. It's working on proofs that gives you the mastery.
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.
I was going through your stuff [2] today and developed a much better intuition for the universal property and initial/final-ness than I had previously (from the beginning of Awodey, Mac Lane, etc), so thanks!
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.
That's half of it. If you have another functor going the other way, with some properties on how the two functors relate, then you get what's called an equivalence of categories. [1] Basically, you need both ways to compose the two functors to be "equivalent" to the identity functor in each category (equivalent as shown by a reversible natural transformation).
This is an ok introduction, but for a much much better introduction check out the book "Conceptual Mathematics". It does a little better than using abstract words like 'objects' (which has a particular connotation for programmers).
I am a bit confused, I had thought there could not be multiple isomorphisms from object A to object B. I thought an Iso was an epi and mono, doesn't that mean the arrows must all be the same? Thanks in advance if someone wants to go through all the ways I'm misunderstanding. :)
if f is an isomorphism between A and B, it simply means that there exists f-1 such that f(f-1) = idB and f-1(f) = idA.
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.
A group is a category with a single object and whose morphisms are all isomorphisms. There are plenty of groups, so you can't be right :). A morphisms can however have at most one inverse.
A serious question, and one not meant to cause offense: why is category theory being pushed so aggressively? I've seen numerous "Category Theory for Dummies"-style posts here over the years that all imply CT is somehow extremely relevant to working programmers in ways that other branches of mathematics like analysis or abstract algebra apparently aren't. Considering that most programmers have never rigorously studied even formal logic or set theory, both of which are directly applicable to formal methods, electrical engineering, and relational database theory, wouldn't those subjects be better studied first?
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:
Its riding the haskell bandwagon to some degree. By borrowing ideas from category theory they have some really nice abstractions in practical code. But then it gets more confusing so you want to loop back and see what the actual definition of a "monoid" is, or understand "functors". Even if haskell's idea of functor isn't 1 to 1 with category theory's.
> 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.
I agree. Working programmers who want something to apply would be better off studying approximation algorithms, combinatorial optimization, mechanism design, computational geometry, or the many other topics that get little space on HN.
I went into more verbal detail in the actual presentation; the argument is something like:
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.
I believe it is part of the gradual realization in the commercial software development community that object oriented programming is a dead end on one hand and the fact that category theory captures abstractly patterns of composition, which with enough reflection yield elegant and efficient software designs.
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.
The biggest confusion for me is why people try to switch from set theory to category theory.
Like sure, I could start calling my functions arrows instead. And my higher order functions - functors, natural transformations or what ever. But what is the gain from doing this?
As thankful as I am that this was made and published, I find only slides with no talk very difficult to try to learn from. I kinda wish slideshare wasn't a thing :/
66 comments
[ 3.2 ms ] story [ 127 ms ] threadThey 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.
http://en.wikipedia.org/wiki/Zero_object_%28algebra%29
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.
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.
[1] http://bartoszmilewski.com/2014/10/28/category-theory-for-pr...
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
[2]: http://en.wikipedia.org/wiki/Monomorphism
[3]: http://en.wikipedia.org/wiki/Monoid
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.
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://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'm very new to this topic, but I have an applied math background.)
[1]: http://en.wikipedia.org/wiki/Equivalence_of_categories
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.
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
http://i.stanford.edu/~ullman/focs.html
http://www.people.vcu.edu/~rhammack/BookOfProof/
> 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.
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.