Hacker News new | past | comments | ask | show | jobs | submit login

Do you know of an example that shows category theory being applied to solving a CS problem ?

From what little I've seen of it category theory seems to be more abstract than conventional abstract algebra and I've rarely heard of even group theory used in the development of an algorithm




I think it depends how broadly or narrowly you conceptualise computer science. I doubt category theory is much use for developing algorithms, but it's been an important influence on type systems for programming languages, especially modern functional languages but also more mainstream things like generic types in Java.

Taking your question literally (“category theory being applied to solving a CS problem”), I'd say the full abstraction problem for PCF is a good example of a problem in computer science whose solution leant heavily on category theory.


http://cseweb.ucsd.edu/~rtate/publications/proofgen/

"Generating optimizations from proofs"

They developed main algorithm using category theory.


I thought group theory was the easy part. Indeed, that's pretty much what crypto is based on. Many other security applications in CS also rely on group-theoretic notions. Consider homomorphic encryption; the idea that one can develop an encryption algorithm that allows an untrusted source to work with your sensitive data without discovering your data itself, due to the fact that there exist 'one-way' functions from plaintext to gibberish that actually preserve certain operations you care about; i.e., if

encrypt(x) = x' encrypt(y) = y' encrypt(z) = z'

and x + y = z, homomorphic encryption for (+) gives you that x' + y' = z'.

Farther away from completely direct applications like these are algebraic ways of viewing a CS problem. Consider vectorizing a for loop that does in-place update of a variable with +=. We know that this can be turned into a parallel reduction, where if N is the length of the list over which the for loop is iterating, the parallel reduction will take O(log N) time. But what other operations does it work with? Associative ones? What can we do if it's not associative, or the return type of the in-place update is different? And so on.

That's pretty much the tip of the iceberg when it comes to abstract algebra being used in CS.

Now on to category theory. I'm still very, very new to it, but I've been seeing tons of connections anyway. I figure I can view the higher level of abstractness two different ways; that it's going to be hard and impractical to make any connection to anything concrete; or, that excitingly many things admit a categorical view precisely because of how general the theory is.

Let's start with the category-theoretic notion of functors; functions taking functions to functions. Never going to see these outside of functional programming, right? You've worked with functors if you've ever spent any significant time in a Unix shell.

Here's a nice blog post on the connection:

http://conway.rutgers.edu/~ccshan/wiki/blog/posts/Higher-ord...

Indeed, 'sudo' can be seen as a functor, taking commands (handwavingly, morphisms from the set of user-privilege states to itself) to higher-privileged commands. Let's check the idea with respect to the functor laws. Does sudo <cmd1>; sudo <cmd2> behave the same as sudo cmd3; (where cmd3 is a script that does <cmd1>;<cmd2>). What is sudo sudo cmd? Now think of any Unix command modifier you would care to write. How would it satisfying the functor laws make it an easier command modifier to use?

Also important is the notion of initial objects in the context of proving properties about the behavior of any algorithm on any data structure (including an interpreter, on a programming language!). It generalizes the notion of a 'starting object' in the context of a set of objects related to each other by transformations; like the empty list in the set of lists related by concatenation. What's useful about this? Proving things on structures that do come from initial objects admit easy proofs by induction. Moreover, if you can come up with the proper set + transformations, you can come up with very 'useful' initial objects for whatever you're trying to prove.

More on that here:

http://en.wikipedia.org/wiki/Initial_and_terminal_objects




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: