12 ms·

The category design pattern

246 points by joubert 11y ago

tyre 11y ago
This is wonderful, and correct, theory. As the Futurama joke goes, "you are technically correct; the best kind of correct." What the Haskell community keeps running into is that most people don't think in theories. Trying to prove the theory to be practical has a poor success rate. They need to implement useful things that people love, then show how the theory got them there naturally. Sentences like this: > Category theory codifies this compositional style into a design pattern, the category. To the average person, a theory codifying a style into a pattern just isn't useful. What does that do? Monads are a common joke to this effect. They are wonderfully useful but poorly understood by most developers. It isn't being right that matters if few understand you. Why was Rails successful? Sure Ruby is nice, but Python is very similar (and it wasn't the `do...end` blocks.) It's because Rails could be used to easily build functional CRUD apps — Whoops! it works — that made difficult easy. Sandy Metz doesn't get heard if DHH isn't building Basecamp. As a philosopher, it pains me to know people don't think that way, but if you aren't changing people's lives then all the theory is just mental masturbation.
- huuu 11y ago
  Some time ago there was a post about this (I can't find it). People don't understand what monads are because they don't know what problem they solve. This article has the same problem. It doesn't explain what problem categories solve. Well it does but the average reader doesn't understand the problem exists.
  - agumonkey 11y ago
    It's like explaining Iterable interface out of the blue.
  - mbrock 11y ago
    I think they also don't understand monads because they have confused notions about the kind of concept "monad" is on the meta level. Their criteria for understanding and their methods of learning are unsuitable for becoming competent with the use of algebraic concepts. They are trying to think their way to a type of "intuition" that simply is not possible, kind of like trying to learn to ride a bike by "understanding" bikes, comparing bikes to various other things, or spamming the internet with complaints about how bikes are strange and difficult. (What's the problem with just taking the bus?!) If Haskell's "Monad" type class were instead called "AbstractComputationFactory" or some other such intimidating technobabble, then when someone looks up what is the superclass of IO they might just think "oh, that's some weird detail, whatever, I might learn about that later." Since instead the name "Monad" is vaguely funny and appealing, people want to master that concept in principle before they even get "Hello, world!" to run in GHCi. Of course people are free to focus on whatever they want, and we can talk about the possibility of improving the pedagogical aspects of Haskell, and probably university teachers have interesting things to say about that. But there is no magic way to explain an algebraic concept that will suddenly make it intuitive and easy. If people want to understand them, they'll have to study. If people want to use them without understanding them on the conceptual level, that is eminently possible. I myself don't understand monads and I've been using Haskell since 2005. I'm just not good at abstract algebra (flunked that class) and PDFs terrify me. However, even though if a mathematician asked me to explain monads I would be embarrassed, I can still use them and even define my own. That's because I've tinkered with them and acquired a know-how feel for the structure and what they are good for and how the patterns work—which is exactly how I've learned every other concept in programming. Since most concepts in programming are ad-hoc, informal, and specified by hand waving, there is not even a possibility of understanding them at the level of mathematical rigor. What is an object? What is a class? Nobody knows. They just use them.
    - icebraining 11y ago
      More than people trying to learn Monads, I see people trying to teach them. Few people write introductory guides to the "AbstractComputationFactories" of other languages, but it seems like everyone who gets (or thinks they get) monads feels the need to write a guide on them. It's inevitable that newcomers to the language will stumble upon them early on.
      - mbrock 11y ago
        True enough. That has to do with the allure of jargon, I think. It's become a meme in itself. Nowadays on the Haskell subreddit, what I see most upvoted are tutorials that involve creating software that does something concrete. If that happens to involve a clever but not overwrought use of cool type system features, all the better. If anyone reading is yearning for some internet points, go write a Haskell tutorial that's useful, concise, and mostly shies away from the rabbit hole of abstract explanations. Even if it's merely about how to run a regexp or do a POST request.
  - userbinator 11y ago
    People don't understand what monads are because they don't know what problem they solve. Or for that matter, the fact that it even is a problem, because it's easy to see that there are plenty of other programming languages with which people can do lots of productive things without ever thinking of the term "monad".
- deleted 11y ago
  [deleted]
- cristianpascu 11y ago
  Reading this article I had the same feeling I had when I was a physics student in math classes: Why the haskel do I need this? Like every time some abstract math concepts were introduced with no connection to reality whatsoever.
  - bordercases 11y ago
    For me, learning mathematics is a way of priming my imagination with patterns and tools that may or may not be relevant, but with the qualification that almost everything can find use if you look hard enough. I'm curious and like to think so having a library of abstractions is always satisfying. Just sitting down to figure out how math can apply to some simple object of meditation is usually fruitful. You can get away speaking English with a relatively compact vocabulary. But reading broadly to enrich your vocabulary with new words and idioms allows you to describe events more fluidly, and perhaps in a way which inspires you into better ways of describing the same thing you could have described less poetry in the compact vocab set. In that way words let you change your perspective by affecting how you frame your sense-data. Mathematics is the same way. If you want to work in a variety of domains, you're going to have to be agnostic ahead of time as to what tools might be useful, which is to say, have many tools.
    - seanmcdirmid 11y ago
      You don't learn an English vocabulary by reading the dictionary, you read literature and see how those words are used in context. Learning in a vacuum is hard for all but the most abstract thinkers.
      - johncolanduoni 11y ago
        I don't think I've ever read a math book that just went "Here is a list of definitions and the statement of some theorems. Have fun!" The problem is that math is usually built on top of more math. So the motivating examples given are often examples in mathematics, just in a different area. For example, most category theory books talk a lot about the categories of abstract algebraic structures to get you an idea of what the things they're describing look like in "the wild." If you've never done any abstract algebra, it's like trying to use the Rosetta stone when you don't know Egyptian or Greek.
- smadge 11y ago
  > To the average person, a theory codifying a style into a pattern just isn't useful I think the average OO programmer recognizes the value of design patterns, eg the Gang of Four book.
  - danieldk 11y ago
    Only after realising what 'problem' a pattern solves, perhaps by experiencing the problem over and over. I think this is why design patterns in OO are commonly abused (overused) - people learn about them without understanding the problem.
    - smadge 11y ago
      Sure, I agree. Novice programmers are not going to instantly understand what a category is, or how to utilize compositional programming without a bunch of experience and examples. However, I think for programming to progress we need to develop theory.
      - Swizec 11y ago
        The proof is in the pudding. You know why we have JavaScript? Because someone went and built it. Once it was built, it existed and people used it. All the theories about what a scripting language for the web should look like fell out the window the moment someone went and put one in their browser. De facto standards beat de jure standards. Every time. Theory is great. It makes for amazing and stimulating conversation. But in the real world the only thing that counts is building shit. PS: this is also why English is the global language of trade and not Esperanto. Even though English is both harder to learn, has a terrible "API", and inconsistent semantics and grammar and syntax. Esperanto is clean and well designed and and learnable in 150 hours and not used by anyone.
        smadge 11y ago
        Well, presumably an advance will eventually provide a competitive advantage. For example, before the Copernican revolution, we had a model for the cosmos that made decent predictions. The heliocentric model actually made worse predictions for a long time until it was evolutionary improved. However, to the early scientists who adopted it, the heliocentric model "felt right." Maybe right now programming in a shitty language like javascript with no regard to program structure is better at "getting shit done" than programming in a functional language using universal abstractions like composition. To people who study and think about it, though, it "feels right." Perhaps if they stick with it and perfect the art, it will eventually provide such a competitive advantage that it will be universally adopted.
- fsloth 11y ago
  I terms of usability this seems to me up there with the set theoretic formulation of relational model. I.e. not as something everybody needs to do but offering an efficient descriptive model for complex systems. When designing programs or datastructures I prefer to use pen and paper and some simple set theoretic ad hoc notation system. I write code for production daily and without this higher level design model my code would be uk terrible shape and very slow to modify. "As a philosopher, it pains me to know people don't think that way, but if you aren't changing people's lives then all the theory is just mental masturbation." Basically really good programmers seem to see the optimal structure for a specific problem out of practice. I need to have some sort of theoretic framework which to use to compose my program logic. I've not had the time to look into category theory but this post succeeded in convincing me it's a practical mental tool to help in program composition. So, based on my personal preferences, I disagree this would not have practical benefits.
- T-R 11y ago
  The theory is for getting consistent/composable APIs, and trust in the code - trust that you can optimize it, parallelize it, or just that it behaves the way it's supposed to, without having to read every line of it. You don't need to think in theory to benefit from that. While it's certainly cute that I can `gem install` a CMS, the Ruby ecosystem is infamous for its magical, non-composable, monolithic frameworks. The functional ecosystems are working toward fixing the all-too-familiar problem where you have to either start over, or hack apart some giant stateful mess anytime your exact usecase hasn't already been built as a library. It's easy to throw a nice looking house together with Lincoln Logs, but I'd take Lego instead any day. Edit: Also, just because someone hasn't built the tallest building in your neighborhood yet doesn't mean they're not building anything. JP Morgan, Kapersky, Facebook, and IMVU are hiring Haskell devs, just off the top of my head.
  - virtualwhys 11y ago
    Agreed on popularity of language/framework not being an indicator of success (wrt to software evolution), quite the opposite seems to happen in the mainstream. Worth noting that finance industry heavyweights such as JP Morgan and Standard Chartered (largest Haskell shop in the world) are laying off more than they're hiring these days[0][1], though unlikely this trend would directly affect tech hires (current batch of layoffs seem to be a trimming of management tier). On a somewhat related note: were Standard Chartered to open source their fork of GHC many Haskellers not sold on lazy-by-default would rejoice; from Scala side of the fence my interest in Haskell would increase 10X were that to happen, line numbered stack traces alone, who woulda "thunk" it ;-) Moving forward Haskell's probably going to continue to be pilfered of its theoretical gems by other languages that leap frog it in terms of adoption. Not a bad thing if we take SPJ's "avoid success at all costs" at face value. [0] http://www.bloomberg.com/news/articles/2015-05-28/jpmorgan-said-to-plan-thousands-of-job-cuts-as-bank-pares-costs http://www.bloomberg.com/news/articles/2015-05-28/jpmorgan-s... [1] http://www.bloomberg.com/news/articles/2015-07-20/standard-chartered-s-ceo-boosts-direct-control-in-overhaul http://www.bloomberg.com/news/articles/2015-07-20/standard-c...
    - tome 11y ago
      > Worth noting that finance industry heavyweights such as JP Morgan and Standard Chartered (largest Haskell shop in the world) are laying off more than they're hiring these days[0][1], though unlikely this trend would directly affect tech hires (current batch of layoffs seem to be a trimming of management tier). Indeed. Hiring of Haskellers continues apace at SC: https://twitter.com/donsbot/status/654630194519646208 https://twitter.com/donsbot/status/654630194519646208 > were Standard Chartered to open source their fork of GHC many Haskellers not sold on lazy-by-default would rejoice It's not a fork of GHC. It's an entirely new compiler, called Mu.
- gaius 11y ago
  Monads are a common joke to this effect. So much so that I wonder if the popular monad tutorial involving spacesuits and burritos wasn't actually made as a pisstake (but I am 99% sure the author was serious).
  - danidiaz 11y ago
    You might be interested in the inverse burrito-monad tutorial: http://www.cs.cmu.edu/~edmo/silliness/burrito_monads.pdf http://www.cs.cmu.edu/~edmo/silliness/burrito_monads.pdf
- mbrock 11y ago
  Haskell isn't designed for "average people" or "most people" and why should it be? Real human beings use Haskell every day and love it. Real human beings are capable of learning about teh scary maths and abstract theories. You studied philosophy? Are you aware that most people don't understand anything about philosophical theories other than The Secret? Have you thought about how maybe those theories can change people's lives even though they're not aimed at a lowest common denominator? E.g. by being influential in the long run, and also by being intellectually stimulating to people who do bother to learn about it? Rails-style success is not the goal for Haskell. It is an explicit anti-goal: the motto is "avoid success at all costs." Terse and rude counterpoint to your thesis: Average people are lazy idiots and designing your language to appeal to them will result in a very popular incoherent mess, like Java and Ruby, and Dijkstra will make pointed remarks at you from his grave. http://www.paulgraham.com/avg.html http://www.paulgraham.com/avg.html
  - Numberwang 11y ago
    So the goal is for Haskell to be the Ithkuil of the programming world? That's a noble idea. Knowing this also makes it easier for me to chose to avoid reading articles about it.
    - mbrock 11y ago
      No. The goal is to be useful in both research and industry by means of principled design based on mathematics and engineering. If that scares you, fine, you don't have to be interested in everything. If you think everything that's not designed to appeal to some notion of an "average programmer" is necessarily obfuscated and impossibly difficult, that's on you. Go ahead and avoid it.
      - Numberwang 11y ago
        That sure does sound like a yes, not a no.
        stingraycharles 11y ago
- david_ar 11y ago
  Replace the word "theory" with "abstraction" or "interface" then. All the article is saying is that there's a bunch of common things (Unix pipes, function composition, procedure sequencing) that all follow a few simple rules (a "contract" if you like). This means you can reason about them together without having to think about the individual "implementation details".
- porker 11y ago
  > Sandy Metz doesn't get heard if DHH isn't building Basecamp. Eh? Are you saying Sandy Metz isn't good, and needs DHH to provide a platform? Disclosure: I have read POODR and am not sure what to make of it, as it's pragmatic but says the opposite of other OOP books I've read
- avz 11y ago
  > Why was Rails successful? I don't think Haskell aims for this kind of success. Abstractions can be useful and they can be beautiful. If your goal is to "easily build functional CRUD apps" you need the former. If you do research in computing science or would like to further your understanding or simply seek to appreciate the elegance and beauty in computation, you need the latter. Admittedly, the latter goals (except research) are self-directed (they may make you a better or at least a happier programmer) and they don't directly contribute value to your customers, so I understand why you just called them "mental masturbation". However, I strongly disagree with that label. There is a long-term value in learning and general self-improvement.
  - mbrock 11y ago
    Unfortunately I don't know of much research in formalizing CRUD apps, but maybe it's out there. The long-term wish as I see it would be for us as an engineering discipline to develop a really clear understanding of the domain, enough to be able to build these CRUD apps in composable ways that can be reasoned about with clear language. Guiding vague questions might include: What is the essence of a CRUD app? How could you define a CRUD app in terms of sets, functions, and categories? What kinds of laws apply in the general CRUD domain? How can we statically verify correctness properties for real-world CRUD systems? That hope has nothing to do with mental masturbation and everything to do with wanting to concretely improve the state of civilization. And of course to reduce the amount of time spent making and debugging the same kind of thing over and over again.
    - catnaroek 11y ago
      I am by no means a researcher, but, as a programmer who writes said CRUD apps for a living, I can guarantee that I derive most of my understanding of a complex business domain from the structure of the relational database backing it. And what is a relational database? A (time-evolving) subcategory of the category of finite sets! Primitive types (as sets of values) and tables (as sets of primary key values) are objects. Fields (as functions of primary keys) are morphisms. Chained foreign key traversal is morphism composition. I find this way of reasoning incredibly powerful, because it tells me quickly what kind of transactions make sense in a business domain. Of course, this is contingent on the database being well designed. It is exactly the same as with Haskell types - if you can leverage the (type system) schema to encode interesting logical properties of your (problem) business domain, then (type checking) checking a query against the schema in itself becomes a lightweight form of formal verification. One thing that must be remarked, however, is that, sadly, SQL lacks analogues of sum and product types, that is, tables whose cardinality (number of rows) is the sum or product of the cardinalities of other tables. This addition would make SQL even more powerful, but it would require a move to a more category-theory-based foundation for databases. (The relational model is based on first-order logic.)
- throwawayignt 11y ago
  >> Category theory codifies this compositional style into a design pattern, the category. >To the average person, a theory codifying a style into a pattern just isn't useful But you don't mean "the average person", you mean "the average competent programmer." For example I'm not an "average person" and I don't understand the sentence you linked (the one I quote at the top of this comment.) It's just gobbledegook to me, the way a bit mask is to someone who doesn't know what bits are exactly, they're just, like, 1's and 0's in the computer right? You have to explain a lot before they would even understand what you're talking about. They might not know what a power of 2 has to do with anything. This is an analogy. It's the same - average competent programmers don't have this mental infrastructure. I and most competent programmers have no idea what a category is.
  - omginternets 11y ago
    >I and most competent programmers have no idea what a category is. By your own admission, you have no idea whether or not category theory is useful to you. Take pride in your ignorance if you like, but at least don't claim to know what you're talking about in the same breath.
- ecthiender 11y ago
  This is utterly wrong. Theory is not any mental masturbation. On the contrary, theory helps in understanding a problem with sparkling clarity and often offers a general approach or solution to the problem. The above is a problem with people who thinks everything in the world is black and white; or they themselves don't understand theories, maybe even being right in the circle which theorizes theories day and night (read academic circles). The key is to understand that all of us theorize all the time. Being programmers, whenever we see a problem, we do try to approach it scientifically. Basing parts of the problem on already established knowledge (read theory). See what we are doing here? We are theorizing a problem. It may not be any formal theory but informal theory is still theory. The point is theory is not just intellectual mumbo jumbo, sure it stimulates few of us to the point of orgasm, but theory is a very humble practice which helps us understand things better.
panic 11y ago
Note that Haskell functions, when considered as values, do not actually form a category: https://wiki.haskell.org/Hask https://wiki.haskell.org/Hask
- dkbrk 11y ago
  I believe that any such problems are due to non-totality and/or non-strict semantics, and generally aren't important in practice. For example, from the abstract for "Fast and Loose Reasoning is Morally Correct" (http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fast+loose.pdf http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fast+loos...): Two languages are defined, one total and one partial, with identical syntax. The semantics of the partial language includes partial and infinite values, and all types are lifted, including the function spaces. A partial equivalence relation (PER) is then defined, the domain of which is the total subset of the partial language. For types not containing function spaces the PER relates equal values, and functions are related if they map related values to related values. It is proved that if two closed terms have the same semantics in the total language, then they have related semantics in the partial language. It is also shown that the PER gives rise to a bicartesian closed category which can be used to reason about values in the domain of the relation.
lmm 11y ago
An abstraction is only useful if you can use it. What sold me on applicatives was being able to write "traverse", and similar operations, that would be m * n if you had to write them for each (traversable, applicative) pair but can be m + n instead ( http://m50d.github.io/2013/01/16/generic-contexts.html http://m50d.github.io/2013/01/16/generic-contexts.html ). That's a very concrete code saving. Having three examples of things that form categories is great - but can we show a real-world function that we can write that takes a generic category, that does something useful with each of these three examples? That would demonstrate that we're getting real value (i.e. a code saving) out of the abstraction.
- userbinator 11y ago
  We want to call them one after another, and return a failure if any of them fails, success if they're all succesful I didn't find that example particularly motivating since I can easily think of a simpler solution: exceptions. (Alternatively, if I was using C, it'd be setjmp()/longjmp(), which perform a very similar style of control flow.)
  - lmm 11y ago
    Exceptions are a more complex solution. They're much harder to reason about, and you can't abstract over them because they're special-cased in the language. I've literally seen Java libraries offer an interface something like this: <T> T doSomething(Callback<T> callback) <T, E extends Exception> T doSomethingThrow(CallbackThrow<T, E> callback) throws E and even that doesn't properly cover the cases, because ideally you'd like to be able to pass a callback that throws two or more unrelated exceptions as well. Setjmp/longjmp is "simple" like goto is simple; if you want to refactor a function that uses them you have to think very carefully. If we have \/, the possibly-error is just a value. We can use it with generic functions in the normal way. We can refactor them in the obvious way and it will just work correctly, and the type system can assure us we've done it right.
    - userbinator 11y ago
      Exceptions are a more complex solution. Are they really? I'd like to see the actual code which gets generated from that ultra-abstract solution, since I already know what creating an exception frame or setjmp/longjmp turns into. If we have \/, the possibly-error is just a value. If you use pointers, then an error can also be signified with a value (0), and there's also this very simple but possibly slightly less efficient way (in the success case): ret = (v1 = func1(v0)) && (v2 = func2(v1)) && ...
spooningtamarin 11y ago
Or in other words. Mathematicians have been thinking of ways to solve problems much longer than anyone else, they have formalized it, they developed amazingly general methods. There's a lot to learn from them.
- qcoh 11y ago
  But just using the definitions is cargo cult and using abstractions for the sake of using abstractions is not necessarily good mathematics. Currently it looks like "use this design pattern because mathematics".
  - spooningtamarin 11y ago
    category theory is excellent mathematics useful in various areas of physics (if you're looking for proof of application) why wouldn't it be useful in programming?
    - deleted 11y ago
      [deleted]
    - qcoh 11y ago
      It's useful because it's a generic design pattern not because of the mathematics behind it (of which virtually nothing is actually used, at least in everyday programming).
      - spooningtamarin 11y ago
        Yeah, generic design pattern which is minimal, compact and simple. Yeah, why would I use mathematics in programming.
        qcoh 11y ago
        > Yeah, generic design pattern which is minimal, compact and simple. A good argument for monads. Much better than the dishonest appeal to mathematics.
cousin_it 11y ago
Function composition and its generalizations are cool, but let's not blind ourselves and claim that they're the key ingredient for good programming. We should be looking for more ideas that make programming better with minimal learning cost. Examples of such ideas that were wildly successful in the past: garbage collection, modules and imports, Unicode strings. Each of those was justified by practice rather than theory.
auvrw 11y ago
i once had a conversation that ended with "i don't know enough category theory to be good at haskell." after learning a (little) more category theory and a (very little) more haskell, i think that assessment was inaccurate, and i wouldn't want anyone else to think the same thing. haskell is strictly-typed, sugared lambda calculus. if you want to learnyouahaskell, think about types and type classes. learn how to desugar wheres, lets, guards, etc. don't worry about functors, much less monads.
- tome 11y ago
  > i once had a conversation that ended with "i don't know enough category theory to be good at haskell." > after learning a (little) more category theory and a (very little) more haskell, i think that assessment was inaccurate, and i wouldn't want anyone else to think the same thing. Indeed. I work with some of the most highly-regarded Haskellers that exist. Few of them would claim they know much (or any?) category theory, nor do they care about category theory.
  - nbouscal 11y ago
    I don't know who the Haskellers you refer to are, or who they're regarded highly by, but all of the core members of the Haskell community that I know do care about category theory, and do know some amount of it. It's too useful to ignore. You absolutely do not need to know category theory to use Haskell effectively and productively. Once you've been using it for a while, though, you pretty much inevitably start learning (and caring about) the mathematics that underlies it.
    - tome 11y ago
      I'm pretty sure most of the following would say they don't know much (or any) category theory: Simon PJ, Simon Marlow, BoS, Lennart Augustsson, Don Stewart, Duncan Coutts, Neil Mitchell, Roman Leshchinsky That hasn't stopped them producing masses of great Haskell. I would welcome correction or clarification by any of the above luminaries!
      - 11y ago
ToJans 11y ago
For me this has been really useful. While I somewhat have a noob understanding of Haskell, and some experience with monads, the parallels between composing functions (i.e. "id" & (.) ) and composing monads i.e. "return" & (<=<) never really occurred to me. Now that I've seen this, I'll probably start looking for similar patterns in other places. This has been what made Haskell click for me: the minute you start doing something that is slightly repetitive, like a for loop including a continue/break, parallelizing code or using if error/null all the time, there's a pattern there. Haskellers recognize these patterns, and implement them once, so you can reuse them and avoid making mistakes by implementing something similar yourself every single time. Having this opportunity makes your code more shorter and concise, and instead of implementing something yourself, you can use these battle-tested implementations to model your code. (And thus avoid those annoying not-null/if error bugs for example.) Even though Haskell might not be suitable for every problem domain, I found out it really shines by it's explicitness. You model your domain using types for intermediate states, and the exercise of converting one type to another is rather trivial. (f.e. a sudoku solver [3]). The biggest problem for me personally has been my inability to speak the category theory language, but I'm learning... I also believe that the basic Haskell libs need examples next to their descriptions, because most of us learn by example. [1] If I can see what a maybe monad is for, I can start using it without properly understanding monads. After a while you'll have seen enough different types of monads to understand their use case. IMO one language implementer that understood this extremely well is José Valim, just take a look at the Elixir docs for data.list. [2] Because Haskell has been mostly implemented by mathematicians and computer scientists, they assume basic upfront knowledge. This is what makes it hard for beginners. What we really need in the Haskell world is some cognitive bias mitigation. YMMV. * [1]: https://www.reddit.com/r/haskell/comments/3rhpyq/as_a_haskell_noob_i_think_docs_need_more_examples/ https://www.reddit.com/r/haskell/comments/3rhpyq/as_a_haskel... * [2]: http://elixir-lang.org/docs/stable/elixir/List.html#functions http://elixir-lang.org/docs/stable/elixir/List.html#function... * [3]: https://github.com/ToJans/learninghaskell/blob/master/0003%20Sudoku.hs https://github.com/ToJans/learninghaskell/blob/master/0003%2...
anon4 11y ago
So this is a bit ranty and I hope it doesn't come off as too rude, but here goes: Let's talk about functions. Why is id . f = f . id = f? id . f is a function which takes some argument, pushes it on the stack, calls f, pushes the result from f on the stack and calls id. This is two function calls and you go two stack levels deep. Just f is one function call and one stack level deep. If f and id are real functions executing on real hardware, then id . f is not strictly equal to f due to unavoidable side effects even if id and f are both pure functions, e.g. you may have not enough stack space to execute id . f, but you could execute just f. Real functions executing on real hardware aren't exactly the same like the pure mathematical notion of a function. If Haskell is a language for writing computer programs executing on actual computers, then id . f ≠ f; and if it isn't, then it's not very useful. Abstractions are well and good, but I must be able to reason how the machine will work while executing my program. Take the official Python implementation - CPython for example. It's nowhere near as fast as C if you write your code naively, but there is very little surprising about it. Or take C. If you write e.g. int id(int x) { return x; } int f(int x) { return 2*x; } int id_f(int x) { return id(f(x)); } Then the compiler is free to compile id to a noop and id_f to be exactly the same as f, but it is not required. Most people won't write a program which requires that behaviour by the compiler in order to work correctly. If the Haskell compiler is required to perform such optimisations, then I would concede id . f = f; just like tail recursion optimisation is required in Scheme, so tail recursion is actually equivalent to loops, rather than being just mathematically equivalent. The broader point I want to make is that a computer programming language is inescapably tied to the reality of how hardware executes instructions and one must have some guarantees on how what is written will translate to machine execution. Another thing is that once you reach a certain level of abstraction, you lose your ability to reason about the concrete things in that class. I'll illustrate what I mean. Let's construct the set of Handleds. A handled is a thing that has a handle, and a handle is a cylindrical protrusion affixed to the object, that can be grasped by an average adult human hand and pushed or pulled along an axis perpendicular to the cylinder's height. So, a TNT detonation device is a handled, since you have a handle on the plunger you press to detonate the TNT. A door also has a handle. Your laptop bag has a handle. A table leg also technically counts as a handle and you can use it to move the table. The thing is, while you would have a theory on how to make handles, such that they would be easily operated by people, the fact that an object has a handle tells you nothing of the object, other than it can be manipulated with a hand. Pretty much the same goes for a category. Yes, you can compose two elements of the category into a third. So... what does it do? You don't know. The problem is, the two lumps of fat that sit in your skull need to affix some concrete properties on the object in order to think about it. Functions are series of instructions that transform values. Or maybe they're relations, if you're a mathematician. But the essence of a function isn't in its composability (at least for programmers), it's in its usage as a unit of execution. Maybe also in its usage as a way to organise your source code. There's no point in explaining something as "it's a category" any more than in a car salesman starting out by pointing all the handles on the car and how the bumpers can be grabbed as ersatz handles in case you need to get a handle on the situation. Saying something is a category is a deferred meaning that you can only understand once you know what that something is, so it's more of a mental burden than an explanation of anything. Category properties may be simple, but their relation to the actual execution of a program is anything but. If you want to explain Haskell, maybe start off with the simple parts. Like how what you write executes on the actual machine and work your way up.
calhoun137 11y ago
I have been studying Category theory recently, on the surface, its merely a theory about dots that are connected by arrows. For some reason, category theorists often claim that category theory is "more fundamental" than set theory, whatever that means. It's especially bizarre since many category theory books begin by saying they will define categories without using sets, and then proceed to say "let A be a collection of dots, and B a collection of arrows" but only God knows what the difference between a collection and a set is, from what I can tell...
- zeckalpha 11y ago
  Sets are more than a collection. They have axioms that are not needed to define categories.
  - calhoun137 11y ago
    Mathematicians used the "naive" concept of a set as "a collection of objects" for thousands of years, and it led to a major crisis in the foundations of mathematics that was only resolved by establishing a rigorous system of axiom's that define what a set is. So I disagree that a "set is more than a collection", with the qualification that the concept of a "collection" that is not associated with any axioms whatsoever, is meaningless. Why do I say "meaningless"? Because this "naive" concept of a collection leads to a number of logical paradox's that can only be resolved by using a system of axioms to define these collections. So it's true that you can define sets by various axiom systems that are not the same, but these systems all exist under the umbrella of "set theory". Using the "naive" concept of a collection is fair enough, since we all "know what you mean", but only as long as your point isn't that category theory is more fundamental than set theory.
    - zeckalpha 11y ago
      Actually, it didn't resolve the crisis. In fact, categories, computability theory, and most mathematical findings of the last 150 years are a direct result of stepping around the crisis, namely Russell's paradox. My point is not that category theory is more fundamental than set theory (though set theory can be described in terms of categories), but rather that it isn't derivative. You don't need the formalisms of set theory to have category theory.
dkural 11y ago
The ironic thing about this post is, no actual category theory is used. Defining functions and functional composition laws is done (and is a perfectly natural thing to do), at the beginning of any undergrad math class. The definition of functions and composition laws was done more than a full century before category theory. Category theory was invented for a deeper reason - to have a rigorous definition of a natural transformation, to enable a precise language to translate back and forth between algebra and topology. Note that this is not a comment about the usefulness of category theory in theory of programming languages, it is about the uselessness of the linked article in talking about it. As another commenter pointed out, in practice Haskell functions as values don't even form a category. This actually matters as illustrating the practical difficulties involved. As a mathematician, I'd say most practicing computer scientists have a very skewed/warped understanding of category theory, and in their ignorance of other theoretical concepts, tend to misunderstand what they do think they know about. In general defining what you're trying to solve, tethered to a real, meaty problem, and then judging theoretical formulations for succeeding at these use cases is a good way to not get stuck in 'empty abstractions'. New mathematics gets invented (and judged) as a way of solving problems. The chain of reasoning might be long but it's there. People don't invent new terminology for no reason (and even if they did, and it didn't help for understanding a problem, it'd get no traction)
- tome 11y ago
  A couple of comments: Correct, it is not category "theory". The terminology "category theory" here is used analogously to how database people say relational algebra is based on "set theory". It sounds a bit silly to mathematical ears. On the other hand, the article is about much more than composing functions. In fact the section headings are "The function category", "The Kleisli category", and "The Pipe category". The rudimentary structure of a category is useful for putting disparate concepts on common ground.
- Tekmo 11y ago
  Did you read the entire post? Functions were only the first example to introduce the reader to the basic idea of associativity and identity. The post then discusses the Kleisli category and the category of coroutine pipelines.
draw_down 11y ago
As I expected, I can follow it until it gets to monads. The thing about explaining monads isn't even a joke anymore, it's just become mundane reality It says that (.) is the same thing as (>=>). Fine, but then why are we talking about (<=<) and (=<<) instead of (id) and (.) now?
- tome 11y ago
  The point of the article is that even though function composition and monadic composition are made out of different things ((.) and id versus (<=<) and return respectively) they have the same underlying structure: associative composition with identity.
arnia 11y ago
If people are interested in reading more about how category theory can be used to help define the structure of software, there are two excellent books I can recommend. The first, 'Computational Category Theory' by Rydeheard and Burstall, builds a library (in Standard ML) that allows one to construct objects that satisfy properties you care about (defined in category theory terms). For example, you could define a rules system in a fuzzy logic and have the right code be automatically generated using the library. The second is less concrete, but probably more eyeopening. 'Category Theory for Computing Science' by Barr and Wells starts from the basic axioms of a category and ends with defining all sorts of interesting patterns for software modularity based on diagrammatic reasoning (a common tool in category theory for proving properties through simple pictures). The ideas here have helped me simplify and think more clearly about code I've been writing (in languages like Java, Python, and Ruby), even if the code isn't (ostensibly) categorical.

246 points by joubert 11y ago

tyre 11y ago

This is wonderful, and correct, theory. As the Futurama joke goes, "you are technically correct; the best kind of correct." What the Haskell community keeps running into is that most people don't think in theories. Trying to prove the theory to be practical has a poor success rate. They need to implement useful things that people love, then show how the theory got them there naturally. Sentences like this: > Category theory codifies this compositional style into a design pattern, the category. To the average person, a theory codifying a style into a pattern just isn't useful. What does that do? Monads are a common joke to this effect. They are wonderfully useful but poorly understood by most developers. It isn't being right that matters if few understand you. Why was Rails successful? Sure Ruby is nice, but Python is very similar (and it wasn't the `do...end` blocks.) It's because Rails could be used to easily build functional CRUD apps — Whoops! it works — that made difficult easy. Sandy Metz doesn't get heard if DHH isn't building Basecamp. As a philosopher, it pains me to know people don't think that way, but if you aren't changing people's lives then all the theory is just mental masturbation.

huuu 11y ago
Some time ago there was a post about this (I can't find it). People don't understand what monads are because they don't know what problem they solve. This article has the same problem. It doesn't explain what problem categories solve. Well it does but the average reader doesn't understand the problem exists.
- agumonkey 11y ago
  It's like explaining Iterable interface out of the blue.
- mbrock 11y ago
  I think they also don't understand monads because they have confused notions about the kind of concept "monad" is on the meta level. Their criteria for understanding and their methods of learning are unsuitable for becoming competent with the use of algebraic concepts. They are trying to think their way to a type of "intuition" that simply is not possible, kind of like trying to learn to ride a bike by "understanding" bikes, comparing bikes to various other things, or spamming the internet with complaints about how bikes are strange and difficult. (What's the problem with just taking the bus?!) If Haskell's "Monad" type class were instead called "AbstractComputationFactory" or some other such intimidating technobabble, then when someone looks up what is the superclass of IO they might just think "oh, that's some weird detail, whatever, I might learn about that later." Since instead the name "Monad" is vaguely funny and appealing, people want to master that concept in principle before they even get "Hello, world!" to run in GHCi. Of course people are free to focus on whatever they want, and we can talk about the possibility of improving the pedagogical aspects of Haskell, and probably university teachers have interesting things to say about that. But there is no magic way to explain an algebraic concept that will suddenly make it intuitive and easy. If people want to understand them, they'll have to study. If people want to use them without understanding them on the conceptual level, that is eminently possible. I myself don't understand monads and I've been using Haskell since 2005. I'm just not good at abstract algebra (flunked that class) and PDFs terrify me. However, even though if a mathematician asked me to explain monads I would be embarrassed, I can still use them and even define my own. That's because I've tinkered with them and acquired a know-how feel for the structure and what they are good for and how the patterns work—which is exactly how I've learned every other concept in programming. Since most concepts in programming are ad-hoc, informal, and specified by hand waving, there is not even a possibility of understanding them at the level of mathematical rigor. What is an object? What is a class? Nobody knows. They just use them.
  - icebraining 11y ago
    More than people trying to learn Monads, I see people trying to teach them. Few people write introductory guides to the "AbstractComputationFactories" of other languages, but it seems like everyone who gets (or thinks they get) monads feels the need to write a guide on them. It's inevitable that newcomers to the language will stumble upon them early on.
    - mbrock 11y ago
      True enough. That has to do with the allure of jargon, I think. It's become a meme in itself. Nowadays on the Haskell subreddit, what I see most upvoted are tutorials that involve creating software that does something concrete. If that happens to involve a clever but not overwrought use of cool type system features, all the better. If anyone reading is yearning for some internet points, go write a Haskell tutorial that's useful, concise, and mostly shies away from the rabbit hole of abstract explanations. Even if it's merely about how to run a regexp or do a POST request.
- userbinator 11y ago
  People don't understand what monads are because they don't know what problem they solve. Or for that matter, the fact that it even is a problem, because it's easy to see that there are plenty of other programming languages with which people can do lots of productive things without ever thinking of the term "monad".
deleted 11y ago
[deleted]
cristianpascu 11y ago
Reading this article I had the same feeling I had when I was a physics student in math classes: Why the haskel do I need this? Like every time some abstract math concepts were introduced with no connection to reality whatsoever.
- bordercases 11y ago
  For me, learning mathematics is a way of priming my imagination with patterns and tools that may or may not be relevant, but with the qualification that almost everything can find use if you look hard enough. I'm curious and like to think so having a library of abstractions is always satisfying. Just sitting down to figure out how math can apply to some simple object of meditation is usually fruitful. You can get away speaking English with a relatively compact vocabulary. But reading broadly to enrich your vocabulary with new words and idioms allows you to describe events more fluidly, and perhaps in a way which inspires you into better ways of describing the same thing you could have described less poetry in the compact vocab set. In that way words let you change your perspective by affecting how you frame your sense-data. Mathematics is the same way. If you want to work in a variety of domains, you're going to have to be agnostic ahead of time as to what tools might be useful, which is to say, have many tools.
  - seanmcdirmid 11y ago
    You don't learn an English vocabulary by reading the dictionary, you read literature and see how those words are used in context. Learning in a vacuum is hard for all but the most abstract thinkers.
    - johncolanduoni 11y ago
      I don't think I've ever read a math book that just went "Here is a list of definitions and the statement of some theorems. Have fun!" The problem is that math is usually built on top of more math. So the motivating examples given are often examples in mathematics, just in a different area. For example, most category theory books talk a lot about the categories of abstract algebraic structures to get you an idea of what the things they're describing look like in "the wild." If you've never done any abstract algebra, it's like trying to use the Rosetta stone when you don't know Egyptian or Greek.
smadge 11y ago
> To the average person, a theory codifying a style into a pattern just isn't useful I think the average OO programmer recognizes the value of design patterns, eg the Gang of Four book.
- danieldk 11y ago
  Only after realising what 'problem' a pattern solves, perhaps by experiencing the problem over and over. I think this is why design patterns in OO are commonly abused (overused) - people learn about them without understanding the problem.
  - smadge 11y ago
    Sure, I agree. Novice programmers are not going to instantly understand what a category is, or how to utilize compositional programming without a bunch of experience and examples. However, I think for programming to progress we need to develop theory.
    - Swizec 11y ago
      The proof is in the pudding. You know why we have JavaScript? Because someone went and built it. Once it was built, it existed and people used it. All the theories about what a scripting language for the web should look like fell out the window the moment someone went and put one in their browser. De facto standards beat de jure standards. Every time. Theory is great. It makes for amazing and stimulating conversation. But in the real world the only thing that counts is building shit. PS: this is also why English is the global language of trade and not Esperanto. Even though English is both harder to learn, has a terrible "API", and inconsistent semantics and grammar and syntax. Esperanto is clean and well designed and and learnable in 150 hours and not used by anyone.
      - smadge 11y ago
        Well, presumably an advance will eventually provide a competitive advantage. For example, before the Copernican revolution, we had a model for the cosmos that made decent predictions. The heliocentric model actually made worse predictions for a long time until it was evolutionary improved. However, to the early scientists who adopted it, the heliocentric model "felt right." Maybe right now programming in a shitty language like javascript with no regard to program structure is better at "getting shit done" than programming in a functional language using universal abstractions like composition. To people who study and think about it, though, it "feels right." Perhaps if they stick with it and perfect the art, it will eventually provide such a competitive advantage that it will be universally adopted.
fsloth 11y ago
I terms of usability this seems to me up there with the set theoretic formulation of relational model. I.e. not as something everybody needs to do but offering an efficient descriptive model for complex systems. When designing programs or datastructures I prefer to use pen and paper and some simple set theoretic ad hoc notation system. I write code for production daily and without this higher level design model my code would be uk terrible shape and very slow to modify. "As a philosopher, it pains me to know people don't think that way, but if you aren't changing people's lives then all the theory is just mental masturbation." Basically really good programmers seem to see the optimal structure for a specific problem out of practice. I need to have some sort of theoretic framework which to use to compose my program logic. I've not had the time to look into category theory but this post succeeded in convincing me it's a practical mental tool to help in program composition. So, based on my personal preferences, I disagree this would not have practical benefits.
T-R 11y ago
The theory is for getting consistent/composable APIs, and trust in the code - trust that you can optimize it, parallelize it, or just that it behaves the way it's supposed to, without having to read every line of it. You don't need to think in theory to benefit from that. While it's certainly cute that I can `gem install` a CMS, the Ruby ecosystem is infamous for its magical, non-composable, monolithic frameworks. The functional ecosystems are working toward fixing the all-too-familiar problem where you have to either start over, or hack apart some giant stateful mess anytime your exact usecase hasn't already been built as a library. It's easy to throw a nice looking house together with Lincoln Logs, but I'd take Lego instead any day. Edit: Also, just because someone hasn't built the tallest building in your neighborhood yet doesn't mean they're not building anything. JP Morgan, Kapersky, Facebook, and IMVU are hiring Haskell devs, just off the top of my head.
- virtualwhys 11y ago
  Agreed on popularity of language/framework not being an indicator of success (wrt to software evolution), quite the opposite seems to happen in the mainstream. Worth noting that finance industry heavyweights such as JP Morgan and Standard Chartered (largest Haskell shop in the world) are laying off more than they're hiring these days[0][1], though unlikely this trend would directly affect tech hires (current batch of layoffs seem to be a trimming of management tier). On a somewhat related note: were Standard Chartered to open source their fork of GHC many Haskellers not sold on lazy-by-default would rejoice; from Scala side of the fence my interest in Haskell would increase 10X were that to happen, line numbered stack traces alone, who woulda "thunk" it ;-) Moving forward Haskell's probably going to continue to be pilfered of its theoretical gems by other languages that leap frog it in terms of adoption. Not a bad thing if we take SPJ's "avoid success at all costs" at face value. [0] http://www.bloomberg.com/news/articles/2015-05-28/jpmorgan-said-to-plan-thousands-of-job-cuts-as-bank-pares-costs http://www.bloomberg.com/news/articles/2015-05-28/jpmorgan-s... [1] http://www.bloomberg.com/news/articles/2015-07-20/standard-chartered-s-ceo-boosts-direct-control-in-overhaul http://www.bloomberg.com/news/articles/2015-07-20/standard-c...
  - tome 11y ago
    > Worth noting that finance industry heavyweights such as JP Morgan and Standard Chartered (largest Haskell shop in the world) are laying off more than they're hiring these days[0][1], though unlikely this trend would directly affect tech hires (current batch of layoffs seem to be a trimming of management tier). Indeed. Hiring of Haskellers continues apace at SC: https://twitter.com/donsbot/status/654630194519646208 https://twitter.com/donsbot/status/654630194519646208 > were Standard Chartered to open source their fork of GHC many Haskellers not sold on lazy-by-default would rejoice It's not a fork of GHC. It's an entirely new compiler, called Mu.
gaius 11y ago
Monads are a common joke to this effect. So much so that I wonder if the popular monad tutorial involving spacesuits and burritos wasn't actually made as a pisstake (but I am 99% sure the author was serious).
- danidiaz 11y ago
  You might be interested in the inverse burrito-monad tutorial: http://www.cs.cmu.edu/~edmo/silliness/burrito_monads.pdf http://www.cs.cmu.edu/~edmo/silliness/burrito_monads.pdf
mbrock 11y ago
Haskell isn't designed for "average people" or "most people" and why should it be? Real human beings use Haskell every day and love it. Real human beings are capable of learning about teh scary maths and abstract theories. You studied philosophy? Are you aware that most people don't understand anything about philosophical theories other than The Secret? Have you thought about how maybe those theories can change people's lives even though they're not aimed at a lowest common denominator? E.g. by being influential in the long run, and also by being intellectually stimulating to people who do bother to learn about it? Rails-style success is not the goal for Haskell. It is an explicit anti-goal: the motto is "avoid success at all costs." Terse and rude counterpoint to your thesis: Average people are lazy idiots and designing your language to appeal to them will result in a very popular incoherent mess, like Java and Ruby, and Dijkstra will make pointed remarks at you from his grave. http://www.paulgraham.com/avg.html http://www.paulgraham.com/avg.html
- Numberwang 11y ago
  So the goal is for Haskell to be the Ithkuil of the programming world? That's a noble idea. Knowing this also makes it easier for me to chose to avoid reading articles about it.
  - mbrock 11y ago
    No. The goal is to be useful in both research and industry by means of principled design based on mathematics and engineering. If that scares you, fine, you don't have to be interested in everything. If you think everything that's not designed to appeal to some notion of an "average programmer" is necessarily obfuscated and impossibly difficult, that's on you. Go ahead and avoid it.
    - Numberwang 11y ago
      That sure does sound like a yes, not a no.
      - stingraycharles 11y ago
david_ar 11y ago
Replace the word "theory" with "abstraction" or "interface" then. All the article is saying is that there's a bunch of common things (Unix pipes, function composition, procedure sequencing) that all follow a few simple rules (a "contract" if you like). This means you can reason about them together without having to think about the individual "implementation details".
porker 11y ago
> Sandy Metz doesn't get heard if DHH isn't building Basecamp. Eh? Are you saying Sandy Metz isn't good, and needs DHH to provide a platform? Disclosure: I have read POODR and am not sure what to make of it, as it's pragmatic but says the opposite of other OOP books I've read
avz 11y ago
> Why was Rails successful? I don't think Haskell aims for this kind of success. Abstractions can be useful and they can be beautiful. If your goal is to "easily build functional CRUD apps" you need the former. If you do research in computing science or would like to further your understanding or simply seek to appreciate the elegance and beauty in computation, you need the latter. Admittedly, the latter goals (except research) are self-directed (they may make you a better or at least a happier programmer) and they don't directly contribute value to your customers, so I understand why you just called them "mental masturbation". However, I strongly disagree with that label. There is a long-term value in learning and general self-improvement.
- mbrock 11y ago
  Unfortunately I don't know of much research in formalizing CRUD apps, but maybe it's out there. The long-term wish as I see it would be for us as an engineering discipline to develop a really clear understanding of the domain, enough to be able to build these CRUD apps in composable ways that can be reasoned about with clear language. Guiding vague questions might include: What is the essence of a CRUD app? How could you define a CRUD app in terms of sets, functions, and categories? What kinds of laws apply in the general CRUD domain? How can we statically verify correctness properties for real-world CRUD systems? That hope has nothing to do with mental masturbation and everything to do with wanting to concretely improve the state of civilization. And of course to reduce the amount of time spent making and debugging the same kind of thing over and over again.
  - catnaroek 11y ago
    I am by no means a researcher, but, as a programmer who writes said CRUD apps for a living, I can guarantee that I derive most of my understanding of a complex business domain from the structure of the relational database backing it. And what is a relational database? A (time-evolving) subcategory of the category of finite sets! Primitive types (as sets of values) and tables (as sets of primary key values) are objects. Fields (as functions of primary keys) are morphisms. Chained foreign key traversal is morphism composition. I find this way of reasoning incredibly powerful, because it tells me quickly what kind of transactions make sense in a business domain. Of course, this is contingent on the database being well designed. It is exactly the same as with Haskell types - if you can leverage the (type system) schema to encode interesting logical properties of your (problem) business domain, then (type checking) checking a query against the schema in itself becomes a lightweight form of formal verification. One thing that must be remarked, however, is that, sadly, SQL lacks analogues of sum and product types, that is, tables whose cardinality (number of rows) is the sum or product of the cardinalities of other tables. This addition would make SQL even more powerful, but it would require a move to a more category-theory-based foundation for databases. (The relational model is based on first-order logic.)
throwawayignt 11y ago
>> Category theory codifies this compositional style into a design pattern, the category. >To the average person, a theory codifying a style into a pattern just isn't useful But you don't mean "the average person", you mean "the average competent programmer." For example I'm not an "average person" and I don't understand the sentence you linked (the one I quote at the top of this comment.) It's just gobbledegook to me, the way a bit mask is to someone who doesn't know what bits are exactly, they're just, like, 1's and 0's in the computer right? You have to explain a lot before they would even understand what you're talking about. They might not know what a power of 2 has to do with anything. This is an analogy. It's the same - average competent programmers don't have this mental infrastructure. I and most competent programmers have no idea what a category is.
- omginternets 11y ago
  >I and most competent programmers have no idea what a category is. By your own admission, you have no idea whether or not category theory is useful to you. Take pride in your ignorance if you like, but at least don't claim to know what you're talking about in the same breath.
ecthiender 11y ago
This is utterly wrong. Theory is not any mental masturbation. On the contrary, theory helps in understanding a problem with sparkling clarity and often offers a general approach or solution to the problem. The above is a problem with people who thinks everything in the world is black and white; or they themselves don't understand theories, maybe even being right in the circle which theorizes theories day and night (read academic circles). The key is to understand that all of us theorize all the time. Being programmers, whenever we see a problem, we do try to approach it scientifically. Basing parts of the problem on already established knowledge (read theory). See what we are doing here? We are theorizing a problem. It may not be any formal theory but informal theory is still theory. The point is theory is not just intellectual mumbo jumbo, sure it stimulates few of us to the point of orgasm, but theory is a very humble practice which helps us understand things better.

panic 11y ago

Note that Haskell functions, when considered as values, do not actually form a category: https://wiki.haskell.org/Hask https://wiki.haskell.org/Hask

dkbrk 11y ago
I believe that any such problems are due to non-totality and/or non-strict semantics, and generally aren't important in practice. For example, from the abstract for "Fast and Loose Reasoning is Morally Correct" (http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fast+loose.pdf http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fast+loos...): Two languages are defined, one total and one partial, with identical syntax. The semantics of the partial language includes partial and infinite values, and all types are lifted, including the function spaces. A partial equivalence relation (PER) is then defined, the domain of which is the total subset of the partial language. For types not containing function spaces the PER relates equal values, and functions are related if they map related values to related values. It is proved that if two closed terms have the same semantics in the total language, then they have related semantics in the partial language. It is also shown that the PER gives rise to a bicartesian closed category which can be used to reason about values in the domain of the relation.

lmm 11y ago

An abstraction is only useful if you can use it. What sold me on applicatives was being able to write "traverse", and similar operations, that would be m * n if you had to write them for each (traversable, applicative) pair but can be m + n instead ( http://m50d.github.io/2013/01/16/generic-contexts.html http://m50d.github.io/2013/01/16/generic-contexts.html ). That's a very concrete code saving. Having three examples of things that form categories is great - but can we show a real-world function that we can write that takes a generic category, that does something useful with each of these three examples? That would demonstrate that we're getting real value (i.e. a code saving) out of the abstraction.

userbinator 11y ago
We want to call them one after another, and return a failure if any of them fails, success if they're all succesful I didn't find that example particularly motivating since I can easily think of a simpler solution: exceptions. (Alternatively, if I was using C, it'd be setjmp()/longjmp(), which perform a very similar style of control flow.)
- lmm 11y ago
  Exceptions are a more complex solution. They're much harder to reason about, and you can't abstract over them because they're special-cased in the language. I've literally seen Java libraries offer an interface something like this: <T> T doSomething(Callback<T> callback) <T, E extends Exception> T doSomethingThrow(CallbackThrow<T, E> callback) throws E and even that doesn't properly cover the cases, because ideally you'd like to be able to pass a callback that throws two or more unrelated exceptions as well. Setjmp/longjmp is "simple" like goto is simple; if you want to refactor a function that uses them you have to think very carefully. If we have \/, the possibly-error is just a value. We can use it with generic functions in the normal way. We can refactor them in the obvious way and it will just work correctly, and the type system can assure us we've done it right.
  - userbinator 11y ago
    Exceptions are a more complex solution. Are they really? I'd like to see the actual code which gets generated from that ultra-abstract solution, since I already know what creating an exception frame or setjmp/longjmp turns into. If we have \/, the possibly-error is just a value. If you use pointers, then an error can also be signified with a value (0), and there's also this very simple but possibly slightly less efficient way (in the success case): ret = (v1 = func1(v0)) && (v2 = func2(v1)) && ...

spooningtamarin 11y ago

Or in other words. Mathematicians have been thinking of ways to solve problems much longer than anyone else, they have formalized it, they developed amazingly general methods. There's a lot to learn from them.

qcoh 11y ago
But just using the definitions is cargo cult and using abstractions for the sake of using abstractions is not necessarily good mathematics. Currently it looks like "use this design pattern because mathematics".
- spooningtamarin 11y ago
  category theory is excellent mathematics useful in various areas of physics (if you're looking for proof of application) why wouldn't it be useful in programming?
  - deleted 11y ago
    [deleted]
  - qcoh 11y ago
    It's useful because it's a generic design pattern not because of the mathematics behind it (of which virtually nothing is actually used, at least in everyday programming).
    - spooningtamarin 11y ago
      Yeah, generic design pattern which is minimal, compact and simple. Yeah, why would I use mathematics in programming.
      - qcoh 11y ago
        > Yeah, generic design pattern which is minimal, compact and simple. A good argument for monads. Much better than the dishonest appeal to mathematics.

cousin_it 11y ago

Function composition and its generalizations are cool, but let's not blind ourselves and claim that they're the key ingredient for good programming. We should be looking for more ideas that make programming better with minimal learning cost. Examples of such ideas that were wildly successful in the past: garbage collection, modules and imports, Unicode strings. Each of those was justified by practice rather than theory.

auvrw 11y ago

i once had a conversation that ended with "i don't know enough category theory to be good at haskell." after learning a (little) more category theory and a (very little) more haskell, i think that assessment was inaccurate, and i wouldn't want anyone else to think the same thing. haskell is strictly-typed, sugared lambda calculus. if you want to learnyouahaskell, think about types and type classes. learn how to desugar wheres, lets, guards, etc. don't worry about functors, much less monads.

tome 11y ago
> i once had a conversation that ended with "i don't know enough category theory to be good at haskell." > after learning a (little) more category theory and a (very little) more haskell, i think that assessment was inaccurate, and i wouldn't want anyone else to think the same thing. Indeed. I work with some of the most highly-regarded Haskellers that exist. Few of them would claim they know much (or any?) category theory, nor do they care about category theory.
- nbouscal 11y ago
  I don't know who the Haskellers you refer to are, or who they're regarded highly by, but all of the core members of the Haskell community that I know do care about category theory, and do know some amount of it. It's too useful to ignore. You absolutely do not need to know category theory to use Haskell effectively and productively. Once you've been using it for a while, though, you pretty much inevitably start learning (and caring about) the mathematics that underlies it.
  - tome 11y ago
    I'm pretty sure most of the following would say they don't know much (or any) category theory: Simon PJ, Simon Marlow, BoS, Lennart Augustsson, Don Stewart, Duncan Coutts, Neil Mitchell, Roman Leshchinsky That hasn't stopped them producing masses of great Haskell. I would welcome correction or clarification by any of the above luminaries!
    - 11y ago

ToJans 11y ago

For me this has been really useful. While I somewhat have a noob understanding of Haskell, and some experience with monads, the parallels between composing functions (i.e. "id" & (.) ) and composing monads i.e. "return" & (<=<) never really occurred to me. Now that I've seen this, I'll probably start looking for similar patterns in other places. This has been what made Haskell click for me: the minute you start doing something that is slightly repetitive, like a for loop including a continue/break, parallelizing code or using if error/null all the time, there's a pattern there. Haskellers recognize these patterns, and implement them once, so you can reuse them and avoid making mistakes by implementing something similar yourself every single time. Having this opportunity makes your code more shorter and concise, and instead of implementing something yourself, you can use these battle-tested implementations to model your code. (And thus avoid those annoying not-null/if error bugs for example.) Even though Haskell might not be suitable for every problem domain, I found out it really shines by it's explicitness. You model your domain using types for intermediate states, and the exercise of converting one type to another is rather trivial. (f.e. a sudoku solver [3]). The biggest problem for me personally has been my inability to speak the category theory language, but I'm learning... I also believe that the basic Haskell libs need examples next to their descriptions, because most of us learn by example. [1] If I can see what a maybe monad is for, I can start using it without properly understanding monads. After a while you'll have seen enough different types of monads to understand their use case. IMO one language implementer that understood this extremely well is José Valim, just take a look at the Elixir docs for data.list. [2] Because Haskell has been mostly implemented by mathematicians and computer scientists, they assume basic upfront knowledge. This is what makes it hard for beginners. What we really need in the Haskell world is some cognitive bias mitigation. YMMV. * [1]: https://www.reddit.com/r/haskell/comments/3rhpyq/as_a_haskell_noob_i_think_docs_need_more_examples/ https://www.reddit.com/r/haskell/comments/3rhpyq/as_a_haskel... * [2]: http://elixir-lang.org/docs/stable/elixir/List.html#functions http://elixir-lang.org/docs/stable/elixir/List.html#function... * [3]: https://github.com/ToJans/learninghaskell/blob/master/0003%20Sudoku.hs https://github.com/ToJans/learninghaskell/blob/master/0003%2...

anon4 11y ago

So this is a bit ranty and I hope it doesn't come off as too rude, but here goes: Let's talk about functions. Why is id . f = f . id = f? id . f is a function which takes some argument, pushes it on the stack, calls f, pushes the result from f on the stack and calls id. This is two function calls and you go two stack levels deep. Just f is one function call and one stack level deep. If f and id are real functions executing on real hardware, then id . f is not strictly equal to f due to unavoidable side effects even if id and f are both pure functions, e.g. you may have not enough stack space to execute id . f, but you could execute just f. Real functions executing on real hardware aren't exactly the same like the pure mathematical notion of a function. If Haskell is a language for writing computer programs executing on actual computers, then id . f ≠ f; and if it isn't, then it's not very useful. Abstractions are well and good, but I must be able to reason how the machine will work while executing my program. Take the official Python implementation - CPython for example. It's nowhere near as fast as C if you write your code naively, but there is very little surprising about it. Or take C. If you write e.g. int id(int x) { return x; } int f(int x) { return 2*x; } int id_f(int x) { return id(f(x)); } Then the compiler is free to compile id to a noop and id_f to be exactly the same as f, but it is not required. Most people won't write a program which requires that behaviour by the compiler in order to work correctly. If the Haskell compiler is required to perform such optimisations, then I would concede id . f = f; just like tail recursion optimisation is required in Scheme, so tail recursion is actually equivalent to loops, rather than being just mathematically equivalent. The broader point I want to make is that a computer programming language is inescapably tied to the reality of how hardware executes instructions and one must have some guarantees on how what is written will translate to machine execution. Another thing is that once you reach a certain level of abstraction, you lose your ability to reason about the concrete things in that class. I'll illustrate what I mean. Let's construct the set of Handleds. A handled is a thing that has a handle, and a handle is a cylindrical protrusion affixed to the object, that can be grasped by an average adult human hand and pushed or pulled along an axis perpendicular to the cylinder's height. So, a TNT detonation device is a handled, since you have a handle on the plunger you press to detonate the TNT. A door also has a handle. Your laptop bag has a handle. A table leg also technically counts as a handle and you can use it to move the table. The thing is, while you would have a theory on how to make handles, such that they would be easily operated by people, the fact that an object has a handle tells you nothing of the object, other than it can be manipulated with a hand. Pretty much the same goes for a category. Yes, you can compose two elements of the category into a third. So... what does it do? You don't know. The problem is, the two lumps of fat that sit in your skull need to affix some concrete properties on the object in order to think about it. Functions are series of instructions that transform values. Or maybe they're relations, if you're a mathematician. But the essence of a function isn't in its composability (at least for programmers), it's in its usage as a unit of execution. Maybe also in its usage as a way to organise your source code. There's no point in explaining something as "it's a category" any more than in a car salesman starting out by pointing all the handles on the car and how the bumpers can be grabbed as ersatz handles in case you need to get a handle on the situation. Saying something is a category is a deferred meaning that you can only understand once you know what that something is, so it's more of a mental burden than an explanation of anything. Category properties may be simple, but their relation to the actual execution of a program is anything but. If you want to explain Haskell, maybe start off with the simple parts. Like how what you write executes on the actual machine and work your way up.

calhoun137 11y ago

I have been studying Category theory recently, on the surface, its merely a theory about dots that are connected by arrows. For some reason, category theorists often claim that category theory is "more fundamental" than set theory, whatever that means. It's especially bizarre since many category theory books begin by saying they will define categories without using sets, and then proceed to say "let A be a collection of dots, and B a collection of arrows" but only God knows what the difference between a collection and a set is, from what I can tell...

zeckalpha 11y ago
Sets are more than a collection. They have axioms that are not needed to define categories.
- calhoun137 11y ago
  Mathematicians used the "naive" concept of a set as "a collection of objects" for thousands of years, and it led to a major crisis in the foundations of mathematics that was only resolved by establishing a rigorous system of axiom's that define what a set is. So I disagree that a "set is more than a collection", with the qualification that the concept of a "collection" that is not associated with any axioms whatsoever, is meaningless. Why do I say "meaningless"? Because this "naive" concept of a collection leads to a number of logical paradox's that can only be resolved by using a system of axioms to define these collections. So it's true that you can define sets by various axiom systems that are not the same, but these systems all exist under the umbrella of "set theory". Using the "naive" concept of a collection is fair enough, since we all "know what you mean", but only as long as your point isn't that category theory is more fundamental than set theory.
  - zeckalpha 11y ago
    Actually, it didn't resolve the crisis. In fact, categories, computability theory, and most mathematical findings of the last 150 years are a direct result of stepping around the crisis, namely Russell's paradox. My point is not that category theory is more fundamental than set theory (though set theory can be described in terms of categories), but rather that it isn't derivative. You don't need the formalisms of set theory to have category theory.

dkural 11y ago

The ironic thing about this post is, no actual category theory is used. Defining functions and functional composition laws is done (and is a perfectly natural thing to do), at the beginning of any undergrad math class. The definition of functions and composition laws was done more than a full century before category theory. Category theory was invented for a deeper reason - to have a rigorous definition of a natural transformation, to enable a precise language to translate back and forth between algebra and topology. Note that this is not a comment about the usefulness of category theory in theory of programming languages, it is about the uselessness of the linked article in talking about it. As another commenter pointed out, in practice Haskell functions as values don't even form a category. This actually matters as illustrating the practical difficulties involved. As a mathematician, I'd say most practicing computer scientists have a very skewed/warped understanding of category theory, and in their ignorance of other theoretical concepts, tend to misunderstand what they do think they know about. In general defining what you're trying to solve, tethered to a real, meaty problem, and then judging theoretical formulations for succeeding at these use cases is a good way to not get stuck in 'empty abstractions'. New mathematics gets invented (and judged) as a way of solving problems. The chain of reasoning might be long but it's there. People don't invent new terminology for no reason (and even if they did, and it didn't help for understanding a problem, it'd get no traction)

tome 11y ago
A couple of comments: Correct, it is not category "theory". The terminology "category theory" here is used analogously to how database people say relational algebra is based on "set theory". It sounds a bit silly to mathematical ears. On the other hand, the article is about much more than composing functions. In fact the section headings are "The function category", "The Kleisli category", and "The Pipe category". The rudimentary structure of a category is useful for putting disparate concepts on common ground.
Tekmo 11y ago
Did you read the entire post? Functions were only the first example to introduce the reader to the basic idea of associativity and identity. The post then discusses the Kleisli category and the category of coroutine pipelines.

draw_down 11y ago

As I expected, I can follow it until it gets to monads. The thing about explaining monads isn't even a joke anymore, it's just become mundane reality It says that (.) is the same thing as (>=>). Fine, but then why are we talking about (<=<) and (=<<) instead of (id) and (.) now?

tome 11y ago
The point of the article is that even though function composition and monadic composition are made out of different things ((.) and id versus (<=<) and return respectively) they have the same underlying structure: associative composition with identity.

arnia 11y ago

If people are interested in reading more about how category theory can be used to help define the structure of software, there are two excellent books I can recommend. The first, 'Computational Category Theory' by Rydeheard and Burstall, builds a library (in Standard ML) that allows one to construct objects that satisfy properties you care about (defined in category theory terms). For example, you could define a rules system in a fuzzy logic and have the right code be automatically generated using the library. The second is less concrete, but probably more eyeopening. 'Category Theory for Computing Science' by Barr and Wells starts from the basic axioms of a category and ends with defining all sorts of interesting patterns for software modularity based on diagrammatic reasoning (a common tool in category theory for proving properties through simple pictures). The ideas here have helped me simplify and think more clearly about code I've been writing (in languages like Java, Python, and Ruby), even if the code isn't (ostensibly) categorical.