Towards understanding Haskell’s monomorphism restriction

Haskell has a very mysterious feature – it’s not a bug :) – called the monomorphism restriction. Every Haskell programmer will sooner or later hear about its existence, but most likely will not stumble upon it in practice. The explanations of the restriction that I’ve found so far were either unclear, imprecise or inaccessible to a beginner. Page on Haskell Wiki doesn’t really explain much but instead turns into discussion between people that don’t fully understand the restriction1. Definition of monomorphism restriction in Haskell 2010 report is not accessible to a beginner. It relies on knowledge of Haskell standard (bindings in particular) and some theory behind type inference. The restriction is also mentioned in chapter 6 of Real World Haskell, but the book doesn’t even attempt to explain it. Only recently, while reading “A history of Haskell: Being lazy with class”, I managed to partially understand what monomorphism restriction is about. Here’s an explanation that is suited for beginners. This is however not a complete treatment of the subject – I still see some aspects of monomorphism restriction that are unclear to me.

Let’s begin by explaining what is monomorphism and what is polymorphism. If you come from object-oriented programming community then no doubt you’ve heard about polymorphism. That’s bad, cause this term means a different thing in Haskell, as most other terms do. A term in Haskell is called polymorphic if it can be instantiated to values of different types, depending on the context in which it is used. A good example is genericLength function from the Data.List module. Its type signature is:

genericLength :: Num a => [b] -> a

which means that genericLength returns value of type a that can be any type which is an instance of Num type class. Hence, the return value of genericLength is polymorphic. Here’s an example:

ghci> genericLength [1,2,3] :: Int
3
ghci> genericLength [1,2,3] :: Double
3.0

Monomorphism, as you probably guess, is the opposite of polymorphism. A term is monomorphic when it has a value of concrete type and this type doesn’t depend on term’s context.

The term monomorphism restriction means restricting polymorphic terms to a single type, hence making them monomorphic. Why would anyone like to do that? Consider this example2:

f xs = (len, len)
       where len = genericLength xs

From this code it looks that len will be computed only once. This would be true if the expected return type of f would be (Int,Int) or (Double,Double). However, note that the result of genericLength is polymorphic and hence it would be reasonable for someone to expect return type of f to be (Int,Double). This would however force the value of len to be computed twice (no type casting in Haskell!). Let me to quote from section 6.2 of “A History of Haskell”:

Hughes argued strongly that it was unacceptable to silently duplicate computation in this way. His argument was motivated by a program he had written that ran exponentially slower than he expected. (This was admittedly with a very simple compiler, but we were reluctant to make performance differences as big as this dependent on compiler optimisations.)

Following much debate, the committee adopted the now-notorious monomorphism restriction. Stated briefly, it says that a definition that does not look like a function (i.e. has no arguments on the left-hand side) should be monomorphic in any overloaded type variables. In this example, the rule forces len to be used at the same type at both its occurrences, which solves the performance problem. The programmer can supply an explicit type signature for len if polymorphic behaviour is required.

And so len becomes monomorphic, because it does not look like a function (takes no parameters) and it is reasonable to expect that it has a concrete type that doesn’t change depending on the context.

Let’s play with the f function a little bit. We begin by checking it’s type signature inferred by the compiler:

ghci> :t f
f :: Num t => [b] -> (t, t)

You can notice that both components of the result tuple must be of the same type t that is an instance of Num type class. That’s how it works in practice:

ghci> f [1,2,3] :: (Int,Int)
(3,3)
ghci> f [1,2,3] :: (Double,Double)
(3.0,3.0)

Attempt to force a polymorphic return type results in an error:

ghci> f [1,2,3] :: (Int,Double)
 
<interactive>:1:1:
 Couldn't match expected type `Double' with actual type `Int'
      Expected type: (Int, Double)
        Actual type: (Int, Int)
 In the return type of a call of `f'
 In the expression: f [1, 2, 3] :: (Int, Double)

The compiler inferred the t to be Int, because the first element of a tuple is declared to be an Int, and expects that the second element will also have type Int. When it realizes that it’s actually a Double it complains. This does not result with an error message that says anything about monomorphism restriction, but if I understand correctly – and I could be wrong with this one – it’s the monomorphism restriction that underlies this behaviour. Let’s supply a type signature for f that explicitly allows elements of the resulting tuple to be of different types:

f :: (Num b, Num c) => [a] -> (b, c)
f xs = (len, len)
       where len = genericLength xs

This definition will not compile producing a horrible error message:

Could not deduce (b ~ c)
from the context (Num b, Num c)
bound by the type signature for
      f :: (Num b, Num c) => [a] -> (b, c)
  at restriction.hs:(4,1)-(5,32)
  `b' is a rigid type variable bound by
      the type signature for f :: (Num b, Num c) => [a] -> (b, c)
      at restriction.hs:4:1
  `c' is a rigid type variable bound by
      the type signature for f :: (Num b, Num c) => [a] -> (b, c)
      at restriction.hs:4:1

The (b ~ c) means that b and c must be of the same type and the rigid type variables means that the programmer supplied a concrete type annotation with the given type variable3. The monomorphism restriction can be disabled using LANGUAGE pragma. Here’s the full code:

{-# LANGUAGE NoMonomorphismRestriction #-}
import Data.List
f :: (Num b, Num c) => [a] -> (b, c)
f xs = (len, len)
       where len = genericLength xs

This allows len to be polymorphic:

ghci> f [1,2,3] :: (Int,Double)
(3,3.0)

And that’s about it. We forced the len function to be computed twice.

As I said in the beginning, I still don’t understand everything about the restriction. In particular I don’t understand all the nuances that are in the Haskell Report. If you take a look at the Haskell Wiki page mentioned earlier, you’ll see some examples of code where you actually get an error message about the monomorphism restriction:

-- This is allowed
f1 x = show x
 
-- This is not allowed
f2 = \x -> show x
 
-- ...but this is allowed
f3 :: (Show a) => a -> String
f3 = \x -> show x
 
-- This is not allowed
f4 = show
 
-- ...but this is allowed
f5 :: (Show a) => a -> String
f5 = show

This is of course consistent with the Haskell Report, which says:

Anything defined with function syntax usually generalizes as a function is expected to. (…) However, the same function defined with pattern syntax requires a type signature if f is to be fully overloaded.

It is not yet clear to my whether the avoidance of duplicate computation was the only motivation behind introducing the restriction. I’m definitely not the only one that is confused with the monomorphism restriction and I think that this is somewhat controversial feature:

The monomorphism restriction is manifestly a wart on the language. It seems to bite every new Haskell programmer by giving rise to an unexpected or obscure error message. There has been much discussion of alternatives. (…) But in all this time, no truly satisfactory alternative has evolved. (from “A History of Haskell”)

The consensus within the Haskell community is that it doesn’t arise often; it is tricky to explain; it provides almost no practical benefit; and so it mostly serves to trip people up. (from “Real World Haskell”)

As a general rule, supplying explicit type signature will always allow to avoid the restriction. It may be tricky to supply type signature in some cases, e.g. functions defined locally within the where clause may require lexically scoped type variables (see here).

UPDATE (01/06/2012): Someone people at reddit correctly pointed out that instead of enabling language extension it would be more natural to deal with the restriction by giving type annotation to f (as said in the last paragraph of the post). Here’s the code that works without language extension:

f xs = (len, len)
    where
      len :: (Num a) => a
      len = genericLength xs
  1. Just to make things clear – I don’t claim to fully understand it either. []
  2. You have to import Data.List module for this to compile []
  3. See: Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Geoffrey Washburn. Simple unification-based type inference for GADTs. In ICFP, pages 50–61, (2006). []

Haskell IDEs, Part 4: Emacs revisited and Summary

In the previous parts of this post I reviewed three different development environments for Haskell: Emacs, EclipseFP and Leksah. This is the last part in which I plan to write about Emacs once again and then summarize all the reviews.

My main problem with Emacs was inconvenience when working with multiple files, mostly because I found switching between buffers (i.e. opened files) annoying. After posting the review there were comments that recommended extensions that could solve these problems.  Here’s the list of extensions that, after some testing, I decided to use:

  • IDO mode. IDO stands for Interactively Do Things and it greatly improves file opening and switching between buffers. When opening a file it shows the list of files and directories in a current directory, allows to navigate the directory tree in an easy manner, provides intuitive filtering capabilities and allows to select a file easily by selecting its name using arrow keys. Similar behaviour is provided when switching between opened buffers. A nice introductory tutorial to IDO can be found here.
  • NumberedWindows improves switching between multiple windows by pressing the Meta key and a number of a window1. This is much easier to type then C-x o.
  • CycleBuffer allows switching to next/previous buffer using F9/F10 keys. That’s an alternative to IDO-enhanced C-x b command.

These three extensions are a huge win. They greatly improve overall Emacs experience. There’s plenty of other window- and buffer-enhancing extensions that I haven’t mentioned – you can take a look at them on Emacs Wiki here and here.

Right now I’m missing two things in Emacs: a bit tighter integration with GHC/GHCi and a possibility to browse through the source tree. First problem should theoretically not be a problem, since haskell-mode and ghc-mod both offer good integration features but, as I mentioned in my review, some of these features didn’t work as the should or at all. I hope this could be resolved with a small effort. As for the source tree browsing, there are of course extensions. One of them is ECB, but I haven’t tried it yet.

Summary

This series was meant to give you a rough idea of what three Haskell IDEs – Emacs, EclipseFP and Leksah – have to offer.  As you’ve seen I was enthusiastic about EclipseFP and Emacs, but very critical about Leksah. I would however suggest not to rely solely on my opinion and test each of these environments on your own. I’ve seen people on #haskell praising Leksah, so perhaps that project is not a lost cause (as my post could have suggested). I also made one omission – vim. There are Haskell modes for vim as well, but I’ve never been proficient in it so when I was faced with improving my vim skills or learning Emacs from scratch, I chose the latter (I think the key factor was the fact that I was learning Scheme at the same time). As a general thought, I have to say that there is no Haskell IDE that would boost my efficiency as a programmer the way Eclipse boosted my Java programming efficiency. I don’t know if such IDE will ever be created, but it would be nice to have at least any kind of refactoring capabilities. At the moment none of the IDEs has such and the programmer has to manually perform repetitious tasks like renaming variables. I’m definitely waiting for this to improve.

  1. Don’t get confused by Emacs’ terminology. A window in Emacs is an area that displays the context of the buffer within a frame. You can split editing area horizontally or vertically and each of these areas is called a window. Term frame is equivalent to what is normally referred to as a window in modern GUIs []

Haskell IDEs, Part 3: Leksah

In the previous parts of this series I presented two development environments for Haskell: Emacs and EclipseFP. It’s time to finish presentation of IDEs with the last one, Leksah – a Haskell IDE written in Haskell.

Leksah was the first Haskell IDE I tried when I started learning the language. I was a total newbie back then (not that I know much more now) and the installation process was very tough going for me. I had all the GHC packages installed from openSUSE repositories, but it turned out that Leksah is not in the repo. This meant that I had to install it using cabal and I wasn’t very keen on idea of having GHC installation managed both by zypper1 and cabal. I described the full story in one of the previous posts, but long story short I removed GHC packages installed from the repo, downloaded pre-compiled GHC binaries and then installed Leksah using cabal. Previously I said that installation of EclipseFP can be tedious, but I should have reserved that word for Leksah. First of all, it’s not easy to find any sort of installation instructions for Leksah. There is a page on Haskell wiki and a user’s manual but both are outdated, manual by about 2 years, wiki even more. Luckily cabal is a smart tool and can manage the installation process quite well by automatically downloading, compiling and installing required dependencies. Since my GHC package repository was bare and Leksah needs a lot of additional dependencies (and I really mean a lot), the whole installation process took Very Long Time. Unfortunately not everything went as smoothly as it should. I recall having some problems with gtksourceview, but #haskell channel came to the rescue and after about 2 hours of struggling with installation (and 3 hours of installing GHC…) I was ready to finally start the IDE. Before we go into details about using Leksah I have to add that upgrading Leksah to newer version was much easier and faster since the dependencies were already present.

When Leksah starts for the first time it needs to collect information about packages available in the system. This, again, takes Very Long Time, so you can get yourself a cup of tea or possibly take a walk. Be prepared to rebuild this database after installing any new packages or upgrading Leksah. The latter doesn’t happen very often, but we’ll get to that later. After drinking your cup of tea (possibly a few) or coming back from the walk – depending which option you chose – you’re finally ready to work with Leksah. Here’s what you get:

List of major features includes:

  • Syntax highlighting. No surprise here. Well, almost. You can’t define your own colours for the editor and you’re limited to a few predefined settings. These colour themes are nice but I don’t see why the user can’t customize them. I also noticed that for some of available settings spaces are not the same width as other characters, which breaks the layout of haddock comments – see the screenshot above. Aside from that the capabilities of Leksah in syntax highlighting are similar to EclipseFP, but the latter gives you customization options and doesn’t have glitches. Anyway, I still think that Emacs wins as far as syntax highlighting is concerned.
  • Cabal file editor. While EclipseFP offers a nice, non-intrusive editor, Leksah will demolish your hand-crafted cabal file. It will insert hundreds of unused sections and completely rearrange an layout you’ve made. Definitely a point for EclipseFP.
  • Automatic compilation and error detection. There is an error pane that shows current compilation errors. Nevertheless, another point goes to EclipseFP since it is able to mark the errors directly in the source code and it can also display HLint warnings. UPDATE: Leksah can also underline errors directly in the code. My mistake here. Nevertheless EclipseFP still has the advantage of HLint integration.
  • Debugging. I still haven’t learned how to use Haskell’s debugger so I really can’t tell how this works.
  • Package browser. It allows you to browse through available packages or packages in your project, but it’s so clumsy that I don’t consider it useful in any way. EclipseFP wins once again.
  • Autocompletion. This is the only thing that seems to work better in Leksah than in EclipseFP. It is more reliable, uses syntax highlighting to display completion suggestions and displays information about package from which a function is imported. A point for Leksah.

Generally, Leksah is extremely clumsy and not really convenient to work with. Interface is cluttered, full of bugs and glitches: text labels aren’t displayed properly, it’s hard to manage panes layout (not impossible, but hard), some panes don’t show up although they should, some commands from menus and context menus don’t work. The graphical interface is really more of problem in Leksah than actual aid for the programmer. Just to give you the idea of how poor an IDE Leksah is: only in the recent version 0.12 (released in March 2012) was the pane displaying the files in the project added. It is a very simple tree widget with no icons of any kind, no drag-and-drop features and no context menus that would allow you to manipulate layout of the project in any way. I couldn’t also find a way to increase the size of the editor in any reasonable way. There’s an option to disable the toolbar and editor tabs, but that’s all. No way to work in the full screen2, no way to get rid of two status bars.

My attempts to develop code in Leksah were really painful and honestly speaking I can’t find a good reason why should anyone choose it as a Haskell IDE. Leksah is buggy, inconvenient, annoying and lacks features. I don’t expect this to change quickly, ’cause the development process is very slow. The previous stable version 0.10 was released in April 2011, the current one in March 2012. That’s eleven months of waiting only to get some minor features that definitely don’t solve Leksah’s problems as a whole. Considering what was said above my advice is simple: if you want a graphical IDE, use EclipseFP.

The only thing that’s left in this series of posts is a general summary and a small addendum about Emacs. Be on the lookout for part 4.

  1. zypper is openSUSE’s RPM package manager []
  2. Don’t get mislead by the screenshot I provided. There’s no window decoration on it, but Leksah is really working in a window, not fullscreen. []

Staypressed theme by Themocracy