Why Traversable/Foldable should not be in the Prelude

Summary: For GHC 7.10, Traversable and Foldable are going to be in the Prelude. I missed the original discussion, but I suspect it's a bad idea.

Types are how Haskell programmers communicate their intentions to each other. Currently, the Haskell Prelude contains:

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

As of GHC 7.10, as part of something known as the Burning Bridges Proposal (ticket, discussion, I can't actually find a full proposal...), that will become:

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

Surely that's a good thing? Aren't more general types always better? Isn't the Prelude an archaic beast from the time before? I'd argue functions which are highly polymorphic are hard to use, and hard to think about, especially for beginners. I'd also argue the Prelude is remarkably well designed, not perfect, but quite an impressive feat.

What makes a type signature complex?

I've been thinking recently about what makes type signatures complex, both to practitioners, and to relative beginners. My rough metric is:

• Fully concrete types are usually simple, as long as they aren't too long. The longer a type gets, the more complex it gets.
• Types with functions in them aren't too bad (order-1 types), but as you go up to order-2 types things start to get more complex.
• Fully polymorphic functions can be simpler than concrete functions, since they declare what you don't need to worry about.
• Functions with type classes are more complex, since you need to read the type signature while looking at the context, and need to know each class being used.
• Simple type classes (Eq, Show) aren't too bad, but custom type classes impose more of a burden.
• As you add more type classes, the complexity grows faster than linearly. Three type classes are not three times as complex as one, but quite a bit harder.
• Higher kinded type classes are significantly more complex than kind * type classes, e.g. Monad, Functor. The reason is that instead of having a hole you fill in, you now have a hole which itself has a hole.
• The higher-kinded type classes Monad and Functor aren't as bad as the others, since Functor is really the "simplest" higher-kinded type class, and Monad is required knowledge for IO.
• As you have more higher kinded type classes, the complexity burden grows even worse than for kind * type classes. Two is significantly more complex than one.

By that metric, the old mapM isn't too bad, but the new mapM is quite complex. It has two higher-kinded type classes, and one of them is not one of the common ones. I appreciate that making Foldable and Traversable key to Haskell will probably lead to them being more used, but now all beginners are going to have to wade through the Monad tutorial, their Foldable tutorial and their Traversable tutorial before they start programming (or just give up).

Why generality hurts

There are two main reasons why generality hurts:

Reading type signatures becomes difficult/impossible. We already have that problem with the Control.Arrow module, which (as far as most people use it), is just a pile of tuple combinators. But unlike other tuple combinators, these are ones whose type signature can't be understood. When I want to use &&& or *** I just pick randomly, see if it type checks, then try again. When other people I know what to use these functions they just use an explicit lambda. No one thinks of referring to the documentation, since the documentation presents a unification problem (which most of the people I know could solve), not an intuition.

Reading code becomes difficult. Haskell is brilliant for letting you write a composable pipeline of code that takes some input, does some processing, and produces some output. But that only works if you have enough concrete pieces in each function to read each piece in isolation. As an example:

test = foo . mapM baz . bar

Using the current mapM definition I can, in a fraction of a second, know the approximate shape of what foo consumes, and what bar produces. With the new mapM I don't, and have to keep more context in my head to reason about the code.

Who it hurts

Generality of this nature tends to hurt two types of people:

Beginners are hurt because they need to know more concepts just to get going. As a beginner I read through Data.List regularly to build up weapons in my arsenal to attack larger problems. The new Data.List will be generalised, and reading it won't give the insights I enjoyed. Maybe the beginner can instantiate all Foldable things to [], but that adds a mental burden to exactly those people who can bear it least.

Practitioners, those who are paid to code for a living, will have greater problems with maintenance. This isn't an unsubstantiated guess... I have taken over a project which made extensive use of the generalised traverse and sequence functions. Yes, the code was concise, but it was read-only, and even then, required me to "trust" that the compiler and libraries snapped together properly.

Who it benefits

The benefit probably comes from those who are already using the Applicative/Traversable classes regularly. For these people, they can probably avoid an import Prelude(). I am not against ever changing the Prelude, but I do think that for changes of this magnitude the ideas should probably be prototyped as a separate package, widely accepted, and only then should significant surgery be attempted on the Prelude. The classy-prelude work has gone in that direction, and I wish them luck, but the significant changes they've already iterated through suggest the design space is quite large.

Concluding remarks

I realise that I got to this discussion late, perhaps too late to expect my viewpoint to count. But I'd like to leave by reproducing Henning Thielemann's email on the subject:

David Luposchainsky wrote:

+1. I think the Prelude should be a general module of the most commonly
needed functions, which (generalized) folds and traversals are certainly
part of; right now it feels more like a beginner module at times.

It is certainly a kind of beginner module, but that's good. Experts know
how to import. Putting the most general functions into Prelude does not
work because:

1. There are often multiple sensible generalizations of a Prelude
function.

2. You have to add more type annotations since types cannot be infered
from the functions.

There is simply no need to change Prelude and all packages that rely on
specific types. Just don't be lazy and import the stuff you need!

I should change my vote to:

-10

British Telecom and Evil Sales Tactics

Not a Haskell post, just a rant about how evil British Telecom (BT) are.

When I got home this Christmas I was welcomed with a router sitting near the computer, and asked to "install it". This perplexed me - when I left my parents left I had already set up broadband, with a wireless router, and it was all working perfectly. I chose to go with BT for my parents, because BT should be the simplest choice - they already have a BT bill, and a BT line, so adding a broadband should be simple. Also, if anything goes wrong, then it has to be a problem with BT.

The package I signed my parents up to came with a really rubbish little USB modem, which I replaced with a nice wireless router with 4 wired ports from Ebuyer. It also had a 20Gb/month limit, with warnings if we went over the limit. Based on talking to my brother (who still lives at home, and is the largest internet user), I suspect we transfer around 15Gb/month.

However, while I was away at Uni, someone from BT phoned up the house. Unfortunately, my Dad answered. My Dad is not qualified to deal with computers. If he wants to "visit" a website he writes down the address on a post-it note and places it near the computer, to be printed out. The person on the end of the phone told my Dad that in we could upgrade our package, making it 4 times faster and £6/month cheaper, and not changing anything else. He agreed, and entered into an 18 month contract with this new plan.

As part of this new plan, we got a wireless router, which is currently sitting in a cupboard somewhere (its inferior to the £40 one from ebuyer in every way). We also got upgraded from 2Mb/s to 8Mb/s, a "significant increase in speed". However, in practice, that makes absolutely no difference. I tried explaining this to people at BT, and they resolutely claimed it was 4 times faster. The real kick in the teeth though is that this new package is limited to 8Gb/month, and any additional usage is charged. This is particularly dangerous: if for example a trojan ends up on the machine, it could run up expensive bills. An 8Gb limit is most definitely not "the same" as our original plan, which was chosen based on what we actually needed.

Over Christmas I had the fun job of trying to sort this out. I rang up BT several times, spent a lot of time listening to bad music and got repeatedly transferred between departments. If the largest telecom company in Britain can't run a call centre, who can? If someone lies to you while selling broadband do you want complaints, broadband, or sales? The answer turned out to be broadband technical support. In the end, after explaining what happened, I got told that they would review the sales call and check if the person selling the contract had lied.

A week later, they phoned back and admitted that we had been completely missold the package. We are now back on the 20Gb/month quota, with a £3/month cost reduction. I had originally chosen to go with BT to keep things "simple". Had I realised that actually trying to get through to anyone sensible was a nightmare, and that they would phone up my parents and lie to them, I would have chosen differently! It's too much effort to change now, but I strongly recommend that anyone else chooses an alternative provider. BT is not cheapest, does not provide the best service, and is not the simplest. There is absolutely no reason to go with BT.

My personal choice of internet provider is Eclipse. If you do choose to go with them, and use the referral code "NMITCHELL" I get some money off my bill, but I strongly recommend them even if you don't use that code. Compared to my parents, I pay half the cost. I have a limit of 20Gb/month, but only counting between 6pm and midnight - sensibly encouraging people to perform massive downloads at off-peak times. If I go over the quota, I get a few warnings, then they start throttling the service, never charging me money or cutting me off. Of course, at such a large quota active only at certain times, it would be a challenge to exceed it. The email support is fantastic, and the web interface is excellent - while setting up an account you get hourly updates on each aspect. I was able to transfer my broadband from one house to another, on a laptop I borrowed for 2 minutes, while in Germany. It isn't the absolute cheapest, but for only a few extra pounds per month, you get a superb service.