28

According to Harper (https://existentialtype.wordpress.com/2011/04/16/modules-matter-most/), it seems that Type Classes simply do not offer the same level of abstraction that Modules offer and I'm having a hard time exactly figuring out why. And there are no examples in that link, so it's hard for me to see the key differences. There are also other papers on how to translate between Modules and Type Classes (http://www.cse.unsw.edu.au/~chak/papers/modules-classes.pdf), but this doesn't really have anything to do with the implementation in the programmer's perspective (it just says that there isn't something one can do that the other can't emulate).

Specifically, in the first link:

The first is that they insist that a type can implement a type class in exactly one way. For example, according to the philosophy of type classes, the integers can be ordered in precisely one way (the usual ordering), but obviously there are many orderings (say, by divisibility) of interest. The second is that they confound two separate issues: specifying how a type implements a type class and specifying when such a specification should be used during type inference.

I don't understand either. A type can implement a type class in more than 1 way in ML? How would you have the integers ordered by divisibility by example without creating a new type? In Haskell, you would have to do something like use data and have the instance Ord to offer an alternative ordering.

And the second one, aren't the two are distinct in Haskell? Specifying "when such a specification should be used during type inference" can be done by something like this:

blah :: BlahType b => ...

where BlahType is the class being used during the type inference and NOT the implementing class. Whereas, "how a type implements a type class" is done using instance.

Can some one explain what the link is really trying to say? I'm just not quite understanding why Modules would be less restrictive than Type Classes.

Cactus
  • 27,075
  • 9
  • 69
  • 149
Rahul Manne
  • 1,229
  • 10
  • 20
  • Both links here are restricted access. This is very weird, to be honest. – Noein Feb 08 '19 at 20:45
  • 1
    For the second link, https://web.archive.org/web/20180720210646/http://www.cse.unsw.edu.au/~chak/papers/modules-classes.pdf – bshanks Jul 05 '19 at 00:37

1 Answers1

25

To understand what the article is saying, take a moment to consider the Monoid typeclass in Haskell. A monoid is any type, T, which has a function mappend :: T -> T -> T and identity element mempty :: T for which the following holds.

a `mappend` (b `mappend` c) == (a `mappend` b) `mappend` c
a `mappend` mempty == mempty `mappend` a == a

There are many Haskell types which fit this definition. One example that springs immediately to mind are the integers, for which we can define the following.

instance Monoid Integer where
    mappend = (+)
    mempty = 0

You can confirm that all of the requirements hold.

a + (b + c) == (a + b) + c
a + 0 == 0 + a == a

Indeed, the those conditions hold for all numbers over addition, so we can define the following as well.

instance Num a => Monoid a where
    mappend = (+)
    mempty = 0

So now, in GHCi, we can do the following.

> mappend 3 5
8
> mempty
0

Particularly observant readers (or those with a background in mathemetics) will probably have noticed by now that we can also define a Monoid instance for numbers over multiplication.

instance Num a => Monoid a where
    mappend = (*)
    mempty = 1

a * (b * c) == (a * b) * c
a * 1 == 1 * a == a

But now the compiler encounters a problem. Which definiton of mappend should it use for numbers? Does mappend 3 5 equal 8 or 15? There is no way for it to decide. This is why Haskell does not allow multiple instances of a single typeclass. However, the issue still stands. Which Monoid instance of Num should we use? Both are perfectly valid and make sense for certain circumstances. The solution is to use neither. If you look Monoid in Hackage, you will see that there is no Monoid instance of Num, or Integer, Int, Float, or Double for that matter. Instead, there are Monoid instances of Sum and Product. Sum and Product are defined as follows.

newtype Sum a = Sum { getSum :: a }
newtype Product a = Product { getProduct :: a }

instance Num a => Monoid (Sum a) where
    mappend (Sum a) (Sum b) = Sum $ a + b
    mempty = Sum 0

instance Num a => Monoid (Product a) where
    mappend (Product a) (Product b) = Product $ a * b
    mempty = Product 1

Now, if you want to use a number as a Monoid you have to wrap it in either a Sum or Product type. Which type you use determines which Monoid instance is used. This is the essence of what the article was trying to describe. There is no system built into Haskell's typeclass system which allows you to choose between multiple intances. Instead you have to jump through hoops by wrapping and unwrapping them in skeleton types. Now whether or not you consider this a problem is a large part of what determines whether you prefer Haskell or ML.

ML gets around this by allowing multiple "instances" of the same class and type to be defined in different modules. Then, which module you import determines which "instance" you use. (Strictly speaking, ML doesn't have classes and instances, but it does have signatures and structures, which can act almost the same. For amore in depth comparison, read this paper).

rob mayoff
  • 375,296
  • 67
  • 796
  • 848
Kwarrtz
  • 2,693
  • 15
  • 24
  • 2
    How does ML solve this ambiguity? Yes, in Haskell you will end up having to wrap it in another type. But how does ML deal with it? "A type can implement a type class in more than 1 way in ML? How would you have the integers ordered by divisibility by example without creating a new type?" isn't really answered by this. – Rahul Manne Apr 29 '16 at 00:30
  • 1
    @RahulManne Not an ML programmer *at all*, but I believe it essentially allows you to to name "instances" and specifically choose which one to bring into scope (by using first-class modules for this purpose rather than type classes). – Ben Apr 29 '16 at 00:53
  • @Ben if that's the case, I wonder, is it possible to do a similar thing where you define the instance in a different file, and importing that file will use only that instance? I'll try it out. – Rahul Manne Apr 29 '16 at 01:13
  • @RahulManne You sort-of can. Haskell's rules around overlapping instances try to make it impossible for two such modules to be used in the same program, so it doesn't give you the ability to have code that picks and chooses which instance to use, only to be able to "configure" your program (at compile time) by which instance to use. And you'd usually need orphan instances, which are frowned upon by the compiler and by most practitioners. – Ben Apr 29 '16 at 01:32
  • @Ben So in ML, you can configure this at run time? In other words, ML allows you to do this by switching on a flag that is not computable at compile-time? Oh and also, I did get Haskell to be able to import in the "correct" instance, named by its module, at compile time. So I'm still not convinced about the other reason Haskell's Type Classes are restrictive (unless of course, picking during runtime is allowed in ML). – Rahul Manne Apr 29 '16 at 01:34
  • @RahulManne I'm getting beyond my certain knowledge here, but my understanding is that different scopes in the same program can opt to use different definitions of the ordering for integers. Haskell deliberately tries to make that impossible; it's a design decision, not an accidental weakness. The compiler (and many libraries) actually use that property. There are pros and cons to each approach, so it's a trade-off. (Exploring what are the benefits and drawbacks for each approach would be a topic for another question, if it hasn't already been answered here) – Ben Apr 29 '16 at 01:39
  • 3
    While this may be true for that `Monoid` class, it is quite easy to make a multi-parameter type class that has a "tag" parameter that specifies which instance you want. You would have to specify it, typically, but this would be analogous to using a qualified module name. In the referenced paper, the encoding uses associated type families instead of multi-parameter type classes but the idea is the same. – Derek Elkins left SE Apr 29 '16 at 03:41
  • 5
    Currently, there's a misfeature in a Haskell extension (OverlappingInstances) which incidentally does allow one to specify in some cases more instances for a type, and which one to choose in a case by case fashion. This is considered a bug, though. In Agda, instead, class dictionaries are implicit parameters, which can be specified at every call, if wanted. So, in Agda we can have multiple instances for the same type (at the price of having to choose which instance to use at every call). http://stackoverflow.com/questions/29504107/which-dictionary-does-ghc-choose-when-more-than-one-is-in-scope – chi Apr 29 '16 at 08:58
  • ...and it's the same in [Scala](http://www.casualmiracles.com/2012/05/03/a-small-example-of-the-typeclass-pattern-in-scala/), where it is common style to choose the needed implementation by importing different implicit declarations (or even defining them just locally). – phipsgabler Apr 29 '16 at 09:53
  • @RahulManne I expanded on my answer somewhat to explain ML's solution to instance overloading. – Kwarrtz Apr 29 '16 at 19:44
  • @Kwarrtz in hindsight, yeah, this actually also somewhat answers my second question "they confound two separate issues: specifying how a type implements a type class and specifying when such a specification should be used during type inference.". I don't think this statement is a DIFFERENT issue than the first, but I think it follows, with both being the case that ML's way of importing instances as modules is far less awkward. It's possible I think, but it's very awkward. – Rahul Manne Apr 29 '16 at 20:51
  • The code for `Product` instance is wrong: you're using non-existent type variable `b`, and `Sum` constructors instead of `Product`. I suggested an edit but it got rejected; one of the reviewers suggested to write a comment instead. – Alexander Batischev Dec 14 '16 at 12:17
  • @AlexanderBatischev, thanks! I wrote this a while ago, but as far as I can tell it was a simple typo. It should be fixed now. – Kwarrtz Dec 15 '16 at 07:14
  • @Kwarrtz There's still a typo: you're returning a `Sum` from `mappend` ;) – Alexander Batischev Dec 15 '16 at 12:15
  • @AlexanderBatischev Sure enough! NOW it should be fixed. – Kwarrtz Dec 18 '16 at 01:03
  • But ML apart from encoding type classes, ML modules can do a lot of other things also, can't they? I am under the impression that they are a much more general concept that Haskell type classes. – Lii Sep 10 '17 at 18:04
  • @Lii That is entirely possible. My knowledge of ML is actually rather limited, and there is a lot about ML modules that I don't know. If you have a specific feature that you believe is relevant to the discussion feel free to suggest an edit or post another comment. However, to me it seems that the question was primarily about the difference between ML and Haskell's approach to instance disambiguation, for which many of the other features of modules are not relevant. – Kwarrtz Sep 15 '17 at 04:19
  • I wouldn't really think of using newtypes to select an instance as "hoops". Using newtypes this way is precisely what we do in academic Mathematics, where we use various functors when we need to take an object of the category of rings and get a corresponding object in the category of monoids. The ring and the monoid aren't the same thing. how could they be? they're in different categories! – Fried Brice Feb 13 '21 at 01:33