I have just submitted a draft article for inclusion in the Monad.Reader entitled “The Typeclassopedia”. I will let the abstract speak for itself:
The standard Haskell libraries feature a number of type classes with algebraic or categorical underpinnings. Becoming a fluent Haskell hacker requires intimate familiarity with them all, yet acquiring this familiarity often involves combing through a mountain of tutorials, blog posts, mailing list archives, and IRC logs.
The goal of this article is to serve as a starting point for the student of Haskell wishing to gain a firm grasp of its standard type classes. The essentials of each type class are introduced, with examples, commentary, and extensive references for further reading.
I would love feedback from anyone, from the newest newb to the expertest expert, who would be kind enough to take a look. Particular types of feedback I would appreciate include:
- Are there parts that are confusing or could be worded more clearly?
- Are there parts that are stated incorrectly?
- Do you know of any additional references that could be included?
I am looking for more references for Foldable, Traversable, and Comonad in particular, so if you know of any good resources/examples/papers related to any of those, please let me know.
At 48 pages and 110 citations, the article is rather hefty, so I certainly don’t expect most people to read through all of it anytime soon—but even if you only take a look at a section or two about which you are particularly interested and/or knowledgeable, your feedback would be greatly appreciated! I hope that this can become a valuable reference for the Haskell community.
Edit, 16 March 2009: a revised and updated version of the Typeclassopedia has now been published in the Monad.Reader.
blog :: Brent -> [String] 
I have started reading through it, and my first impressions are that this is exactly the sort of thing that I need!
In particular, the quote “Hmm, it doesn’t compile.
. .maybe I’ll stick in an fmap here…nope, let’s see…maybe I need another (.) somewhere? …umm…” rings all too true. Although, it is usually liftM rather than fmap, although having just looked them up on Hoogle, they are actually very similar.
Anyway, just giving you some positive feedback to reassure you that this (mammoth!) undertaking is definitely appreciated.
As you say, there is no substitute for experience, and I do find that as I write more and larger Haskell programs, the intuition does slowly come. And it’s all good fun too.
Good stuff!
The last sentence on (>>) ends abruptly (p. 13).
I have been a haskell lurker for many a year, but have not yet actually _done_ anything. As you say, there are reflexes that must be acquired. Your article does seem to fill a gap; I particularly like the references to other papers – they look both comprehensive and interesting.
I’m still getting lost in various parts, but thats just down to low-wattage in the brain department, I think.
Great work! I hope my criticism below doesn’t come across too negatively.
Personally, I find the wealth of footnotes slightly hampers the article’s readability, and I’d prefer the short listings to be inlined where they occur. This is particularly noticable at the bottom of page 3, where the functor listing is not in view. Hard problem, I know.
I haven’t gotten too far yet. The identity functor as “tainted” values was new to me (very nice!), and I’m wondering whether the concept doesn’t fit Applicative even better than Monad? At least, the example computations all fit into applicative, and it’s not clear to me why you should be able to fold doubly tainted values to just tainted values (join).
Cheers
Rob
Hi!
On page 13, the note about “_ >> m” is incomplete.
Thanks for the text!
Also on page 18 (>>=) is written as (>>=.
Pingback: Haskell resource: Typeclassopedia | Colin Ross
Great article! A few issues (so far):
is used way before it is defined – first used in Listing 8 (ZipList), not defined until two pages later, just after Listing 10 (Applicative law).
Pointed should indeed have a law in my opinion. You need some kind of separability – like injectivity. Otherwise, const Nothing qualifies as a valid pure for Maybe, for example. I’m not sure what the correct law is though – ask the CT people.
-Yitz
s/Data.Applicative/Control.Applicative/
RE: footnote #2
Typeclass can be one word, as evidenced by your title, with the ‘t’ capitalized and the -opedia suffix appended. ;)
Great paper. A Haskell neophyte thanks you. More later.
Some text is missing at the end of the second paragraph
after Listing 11 (Monad type class).
Very nice! Several comments:
(1) the arrowhead in Fig 1 from Monoid to Foldable crosses in a confusing way the arrow from Applicative to Monad (not to be confused with an Arrow from an Applicative to a Monad…)
(2) You’re missing parens around <$ on page 11.
(3) Page 15: there is no puts (at least, not in the mtl I have)
(4) Page 19: y is bound to the result of c.
(5) On page 21 when you say that StateT s Maybe a loses its state upon failure, it might be helpful to give the types of runStateT and runMaybeT, since (at least in my mind) the statements seem backwards at first glance.
You lost me at ArrowLoop – I called up GHCi and tried to figure out what it means to have a variable on both sides of the = in a let (eg. let x=x*x in x) but was never able to get anything other than an error… But the first 37 pages are certainly very thorough!
This might not be worth the effort, but I wonder if it would be helpful for each section (say, Monad) to start with a mini version of Figure 1 showing just the local neighbourhood for the particular typeclass? (so we would just have Applicative pointing to Monad, pointing to MonadFix, etc).
Great work! I already had the chance to acquire some intuition for many of the type classes you describe. However, seeing them nicely assembled helped me reorder this intuition…freeing room for more cool Haskell stuff :P
Furthermore, I’d like to reference your typeclassopedia from the Haskell links for the University Course (http://www.infsec.ethz.ch/education/ss09/fmfp/haskell_links) I’m doing the exercise classes for. Thus I’m looking forward to the announcement of the final version or at least a stable link.
On page 26, “discussion monoids” (across two lines) should be “discussion of monoids”.
There’s a missing ) on page 29 after Traversable.
The reason I’m okay with the fail method is for one and only one reason: the Maybe monad, where fail _ = Nothing. This has the effect that any failed pattern match in the Maybe monad simply returns Nothing, which is a seriously useful side effect, especially when combined with MaybeT…
One additional thing: a lot of my intuition on Arrows comes from the idea that an arrow that isn’t a monad is precisely an arrow that cannot implement ArrowApply, meaning that you cannot, in general, “get the output” of an arrow within another arrow save by composing it with other arrows. This makes it much clearer to me why such seemingly useless methods such as first are required: every piece of data in use by an arrow must be passed through the arrow to the other end, because there’s no other way to bring it through to future computation, because we can’t apply arrows to little bits of our data and get their output. Does this make sense?
Also, Uustalu’s name is misspelled on page 40.
Louis: We have the MonadPlus class for this :)
> mzero :: m a
Great stuff, great read!
Small comment: “But fmap doesn’t give us the tools to do anything with a function which is itself in a context.” doesn’t seem to be fully correct:
> fmap ($ True) :: Functor F => F (Bool -> a) -> F a
does something with a function with context. Maybe you need to say “But fmap doesn’t give us the tools to do work with a function in a context and a value in another context.”?
Great article and idea! I think this really fills a gap.
But it would be really fantastic if it were in the form of HTML with images rather than a PDF, maybe even as a part of the wiki on Haskell.org. That would make it much easier to find for beginning-to-intermediate Haskell coders.
Fantastic work!
This should be required reading for any haskell beginner.
Thanks for the effort, I wanted something like this for sooooo long.
Wow. Very excellent prose, and the bibliography is amazing. I learned a bit, and it brought together a lot of ideas I knew a little bit about but hadn’t thought of how they were interconnected. I really liked the simpler presentation of the monad laws in terms of fish. I also like the introduction to new classes not yet in the base libs I have. I really wish this document was around when I was learning these ideas.
“a value of type Arrow a => a b c can be thought of as a computation which takes values of type a as input and produces values of type c as output.” Should read “takes values of type b as input”.
I kind of expected to see the fish operator in the discussion of the Kleisli arrow.
I thought you should have mentioned liftM when discussing the monad law relating monads to functors. (The last law says that fmap = liftM, no? This seems like a much simpler way to state it than xs >>= return . f).
I’m yearning for more on comonads. I guess I’ll have to chase the biblio.
Thanks for the coverage of foldable and traverse. These are subjects I havent studied enough of yet and hopefully your paper will motivate me to start using them.
Oh, I forgot to mention, I really like your explanation of join in terms of trying to implement bind using just Applicative primitives. This is the first description of “join” that really gelled for me.
Instances of each class that are not instances of more specific classes would be useful. Such as: something that’s a Functor but not Pointed, something that’s a Pointed but not Applicative, etc.
“Pointed has no associated laws to worry about.”
Actually I think Pointed instances must satisfy
fmap ab (pure a) = pure (ab a)
Hmm. ((,) a) is a Functor that probably shouldn’t be made a Pointed.
Page 33:
“Arrow a => a b c can
be thought of as a computation which takes values of type a as input, and produces
values of type c as output”
Should be takes values of type _b_ ?
I agree with David, I would much rather see this in a wiki.
Wow! Looks terrific so far. Until when will suggestions be helpful?
One request so far: use “(~>)” instead of “a” for the type constructor parameter to Category and Arrow. For instance:
class Category (~>) => Arrow (~>) where
arr :: (a -> b) -> (a ~> b)
first :: (a ~> b) -> (a,c) ~> (b,c)
second :: (a ~> b) -> (c,a) ~> (c,b)
(***) :: (a ~> b) -> (a’ ~> b’) -> ((a,a’) ~> (b,b’)
(&&&) :: (a ~> b) -> (a ~> b’) -> (a ~> (b,b’)
> Hmm. ((,) a) is a Functor that probably shouldn’t be made a Pointed.
I’d hope ((,) a) would be made a Pointed, consistently with its Applicative. Ashley — please say more about your preference not to have a pair Pointed.
Oops — lost code formatting in my (~>) example. Is there to enter code and keep the formatting?
Pingback: Typeclassopedia — a generic response « blog :: Brent -> [String]
Outstanding work. This is high quality material that fills an important gap. It was as if you were writing straight to me. I think the bibliography alone would have been a valuable reference for me. IMO this is a valuable companion to Real World Haskell. I do have one suggestion. In several places you mention things that are left as an exercise for the reader. It would be nice for me if you had answers to all of these exercises. I’m sure they’re out there already, but having them all in one place would be convenient.
Joachim’s comment (https://byorgey.wordpress.com/2009/02/16/the-typeclassopedia-request-for-feedback/#comment-1093) is especially poignant, but hopefully no new user will feel betrayed to discover the existence of the loeb function…
loeb :: (Functor f) => f (f b) -> f b
loeb xs = fmap ($ loeb xs ) xs
Hmm, maybe it’s all because of that suspicious “fmap ($…)” construction.
((,) a) is not an Applicative actually. For instance, ((,) Char) is not an Applicative. This is because there’s no good value for “pure 3 :: (Char, Int)”.
It looks like “Monoid a => (,) a” is Applicative
BMeph, surely loeb should have a type more like “f (f b -> b) -> f b” (with some constraint on f)?
@Ashley Yakeley (and newsham): Yes, my mistake, I should have written:
loeb :: (Functor f) => f (f b -> b) -> b
However, I still stand by my suspicion of the trouble that comes from the “fmap ($ … )” construction.
Page 23 states that the [a] instance of Monoid defines mconcat = concat, and footnote 14 says this illustrates a case where mconcat is defined as something more efficient than the default.
However, lambdabot says concat’s definition is simply foldr (++) [], which is the same thing as mconcat’s default definition. In addition, Data/Monoid.hs in the ghc 6.10.1 source doesn’t even define mconcat in the Monoid [a] instance.
“So it would not make sense to say instance Functor Integer, but it could make sense to say instance Functor Maybe.”
Typo?
Hi. This article certainly clarified several things for me. However, I think it still leaves the reader unclear about the motivation behind some of the abstractions, notably Applicative, Arrow and Comonad. Obviously, with so much material to cover, you’re going to have to leave a lot to the further reading. However, I think it would be nice if for each of the abstractions, you at least discussed when it would be appropriate to use it. (For example, you could explain *why* the Haskell XML toolkit uses Arrows).
Great stuff — I’m definitely in the target audience.
p. 10: You use <$> in the “more idiomatically” section, but doesn’t get described until p. 11. (And on p. 11, again it is used before it is properly introduced near the bottom of the page.)
This is really great! Thanks for doing this. But a couple of noob questions:
Is ‘pure’ is just another kind of ‘lift’? The article suggests that fmap lifts but ‘pure’ seems to do essentially the same thing without first applying a function. If I can why is ‘pure’ necessary since ‘fmap’ already exists?
Thanks …
deech
Pardon the grammatical errors above. It’s what happens when you cut-and-paste while rephrasing. Blogging software with some sort of grammar compiler would be nice.
@mightybyte. Ditto!
Amazing piece of work, Brent. I wish I’d read this years ago. Reading this has elevated my perspective over the Haskell landscape; understanding these concepts is crucial for anyone to become a fluent Haskeller instead of just a dabbler. The order of presentation makes this happen.
I wish this were an appendix in RWH because it also helps RWH make much more sense. Maybe I’ll print it out and paste it in there. Typeclassopedia should be mandatory reading for all Haskellers.
The only problem is: how do we abbreviate the name with a snappy acronym like “RWH”?
“Tcop”?
on page thirteen, end of the fourth paragraph from the bottom, there is a sentence i’m dying to read the end of but can’t. because it’s not there. =P
In the section about monoids, you mention that monads can actually be viewed as a monoid: there it would be nice to mention that this is not the monoid instance typically defined for library monads (like Maybe). Also, I think you should at least mention Writer or WriterT somewhere in that section.
(Also, I find it ironic how the section about Monad talks about intuition, after your previous blog post on monad tutorials. I didn’t even dare to read that section in case it would clash with my intuition about monads.)
IO monad is described incorrectly. See http://www.haskell.org/haskellwiki/IO_inside and http://mailman.science.ru.nl/pipermail/clean-list/1999/001036.html
The latter is from Clean mail list, but it helps to understand what exactly the RealWorld from the first article means.
The IO Monad is not magical. There’s nothing which makes it unique. Implementation of any function can be different in different compilers, this is true even for basic functions such as Prelude.foldr.
All monads are pure, and none of them require special compiler support. There are no functions with side effects in Haskell — everything, including IO, is pure.
I also spotted the issue found by Kevin Ballard, regarding the mappend’s definition for lists.
Sorry, I meant mconcat.
Pingback: Monad.Reader #13 is out! « blog :: Brent -> [String]
Hi,
is there a standalone version of the article in the Monad.Reader, maybe as HTML? I keep looking at the typeclassopedia a lot and it’s annoying having to scroll to it in the Monad.Reader PDF all the time. :)
Good question, unfortunately there isn’t one currently. However, I do have plans to put out a standalone second edition with a few updates and such.
In the meantime, I’ve posted a standalone PDF reprint of Version 1 of the Typeclassopedia:
Click to access typeclassopedia.pdf
Hope this helps,
Yitz
Thanks Yitz!