8 ms·

Type classes are useful but can be overly restrictive as implemented in languages such as Haskell. In particular, Haskell prevents multiple implementations of a

Type classes are useful but can be overly restrictive as implemented in languages such as Haskell. In particular, Haskell prevents multiple implementations of a type class for a particular type (a property called canonicity). But there are lots of situations where there are many reasonable implementations of a type class for a particular type. I hadn't seen a great type-safe way to support ad hoc polymorphism until I read about [modular implicits][1] in OCaml. In situations where there is a reasonable module that satisfies a specified signature for the type of an argument, the module can be inferred. [1]: https://arxiv.org/pdf/1512.01895.pdf https://arxiv.org/pdf/1512.01895.pdf

nerdponx 5y ago
Idris 2 solves the problem by letting you define "named implementations" of interfaces: http://docs.idris-lang.org/en/latest/tutorial/interfaces.html http://docs.idris-lang.org/en/latest/tutorial/interfaces.htm...
wereHamster 5y ago
In Haskell you typically work around this by using newtype to wrap your type so that you can give the new type specific implementations of type classes.
kccqzy 5y ago
What's wrong with newtypes? Even Rust is using them, see for example Wrapping: https://doc.rust-lang.org/std/num/struct.Wrapping.html https://doc.rust-lang.org/std/num/struct.Wrapping.html > I hadn't seen a great type-safe way to support ad hoc polymorphism This is an oxymoron. Type classes were invented to create type-safe ad hoc polymorphism (as opposed to parametric polymorphism). You should check out the original paper that introduces type classes back in 1989—it literally had a title of "How to make ad-hoc polymorphism less ad hoc" by Wadler (who else?) I only skimmed that paper about modular implicits, but it does seem inspired by Scala implicits, yet another earlier work to make ad hoc polymorphism useful.
- joppy 5y ago
  What's wrong with newtypes is that if you want to define "the monoid of integers under addition" and "the monoid of integers under multiplication" (or similar, the second isn't really a monoid because of zero), then an expression like a*x+b becomes some kind of newtype hell: toAdditive ((toMultiplicative a) <> (toMultiplicative x)) <> toAdditive b or something similar. This is of course an insane way to program, and so really what is done is that we define two entirely different operations of addition and multiplication so that they can be used without newtypes. What would be cool is if operations could ad-hoc be bound to instances of typeclasses, for instance you could accumulate a list of integers inside the (0, +) monoid, or inside the (1, *) monoid. Of course this is basically what the fold functions in Haskell do, but you could imagine being able to formalise this pattern at the type level in a less newtype-hellish way.
  - gugagore 5y ago
    I don't know why the Wikipedia article says otherwise, but 0 poses no problem for the integers to be a monoid under multiplication. Right? You just need an identity and associativity, not inverses.
    - joppy 5y ago
      Yeah you're totally right, my bad.
  - greydius 5y ago
    > toAdditive ((toMultiplicative a) <> (toMultiplicative x)) <> toAdditive b > This is of course an insane way to program If you have a set with two binary operations, then a monoid isn't the correct abstraction. How would you propose to define <> so that a<>x<>b means ax+b and not e.g. a+xb. And how would your proposal be materially different from newtype conversions?
    - joppy 5y ago
      > If you have a set with two binary operations, then a monoid isn't the correct abstraction. I guess my point is that even if I used "the correct abstraction" here, meaning a ring or something, then the whole newtype setup still makes it annoying for me to split off one operation and feed it into a function expecting a monoid: the way that fold and friends work is much more natural, just taking a starting value 1 and an operation * for example, rather than some kind of "Multiplicative" newtype or whatever. In general I see a lot of the abstract algebra type towers in Haskell and Purescript as being unhelpful, and making a huge assumption that (for example) there will rarely be two monoid instances on a type. In reality in abstract algebra we use tons of different operations on the same objects all the time, and I really just want to define those operations and then be able to use them.
curtisf 5y ago
Having canonical implementations is a feature, not a bug, of type-classes. For example, consider the type `Data.MaxHeap a`, which is a persistent max-priority heap. Max-heaps can be combined in logarithmic time, as long as they are ordered internally by the same ordering. Haskell provides `Data.Heap.union :: Ord a => MaxHeap a -> MaxHeap a -> MaxHeap a`. This is only possible because the type guarantees that the ordering of the two MaxHeaps is the same (the one single implementation of `Ord a`). It also means that you don't have to store any v-table within the `MaxHeap` value, making lookup just a bit faster and making optimizations like monomorphization easier. If you didn't have canonical implementations, you would have to give up being able to write safe & efficient data-structures like this. You would need to be able to dynamically store orderings (wasting space), dynamically compare orderings (wasting time), and have redundant failure paths only for the extremely uncommon and undesirable case where you try to `union` two MaxHeaps with different internal orderings (MaxHeap a -> MaxHeap a -> Maybe (MaxHeap a)). ----- An alternative might be dependent types, where you can instead insist that the ordering _values_ within the two heaps are compatible, gaining the efficiency (by using "ghost" variables) and safety of canonical implementations while avoiding the , but this is more complicated to use, and Haskell doesn't have proper dependent types (yet?). ---- However, in most situations where you might want to try violating canonical instances, defining a newtype is a perfectly satisfactory way to do it.
- jules 5y ago
  If you compare it with how you'd implement such a data structure using ML modules, it becomes very clear that the bug here is the definition of Data.Heap.Union, not the non-canonicity of type classes. With ML modules you'd define a Heap module that is parameterised by an Ord module. Different instantiations of the Heap module for the same type `a` but different instances of `Ord a` are different: heaps with Ord1 are of a different type than heaps of Ord2. From this point of view, passing the Ord instance into each individual heap function call (such as union) is clearly not the right setup. The canonicity of type classes is merely a bandaid for that problem.
  - tel 5y ago
    Generative functors indeed fixes the issue, but it’s kind of interesting because they’re similar in a way to newtypes. In each case, you generate a new type, distinct from the others, which holds a new implementation of the same interfaces. It comes down to ergonomics where OCaml’s approach tends to make local reasoning easier and Haskell’s approach makes it a little easier to transform structurally isomorphic types into one another by wrapping/unwrapping.
reikonomusha 5y ago
What do you think about most object-oriented languages only allowing one definition of a method per class?
- lmm 5y ago
  It's infuriating when it means you can't implement the same interface in two ways.
  - Joker_vD 5y ago
    Well, how do you chose which implementation will get picked? In my experience, explicit wrappers is the cleanest way ― but then again, I also find explicit casts/conversions (which essentially are the same thing) to be the cleanest way too.
    - lmm 5y ago
      If it would be ambiguous then you would have to specify yes. But for the cases where the required type means there's only one implementation that could work, I don't see the value in having to specify.
      - Joker_vD 5y ago
        Uh, how would such an interface look? The one that can be implemented in two ways, and yet "the required type means there's only one implementation that could work"?
        lmm 5y ago
        I'm mainly thinking of parameterized interfaces, like `Comparable` or some kind of "Keyed<T>". Another example would be datastructures that can be iterated in multiple ways, e.g. a multidimensional array that can implement both `Iterable<Int>` and `Iterable<Row<Int>>` or something like that. You could have cases where you're passing that to a function that expects Iterable<Int> so it's obvious which implementation you want, and cases where you would have to disambiguate.
whateveracct 5y ago
Canonicity has value tho..to frame it as a design flaw is just wrongheaded.
4ad 5y ago
See instance arguments in Agda: https://dl.acm.org/doi/abs/10.1145/2034574.2034796 https://dl.acm.org/doi/abs/10.1145/2034574.2034796 https://agda.readthedocs.io/en/v2.6.2.1/language/instance-arguments.html https://agda.readthedocs.io/en/v2.6.2.1/language/instance-ar...
remexre 5y ago
My 2c is that it makes a lot of sense to have a single unnamed instance of a typeclass, and have that follow the orphan rules, but to allow other _named_ ones that don't follow those rules. Then, add syntax (possibly reuse TypeApplications' @ prefix?) to explicitly specify a typeclass when referencing a name. Possibly also have some lexically-scoped construct to make the instance that instance search will find be a particular named instance too?

nerdponx 5y ago

Idris 2 solves the problem by letting you define "named implementations" of interfaces: http://docs.idris-lang.org/en/latest/tutorial/interfaces.html http://docs.idris-lang.org/en/latest/tutorial/interfaces.htm...

wereHamster 5y ago

In Haskell you typically work around this by using newtype to wrap your type so that you can give the new type specific implementations of type classes.

kccqzy 5y ago

What's wrong with newtypes? Even Rust is using them, see for example Wrapping: https://doc.rust-lang.org/std/num/struct.Wrapping.html https://doc.rust-lang.org/std/num/struct.Wrapping.html > I hadn't seen a great type-safe way to support ad hoc polymorphism This is an oxymoron. Type classes were invented to create type-safe ad hoc polymorphism (as opposed to parametric polymorphism). You should check out the original paper that introduces type classes back in 1989—it literally had a title of "How to make ad-hoc polymorphism less ad hoc" by Wadler (who else?) I only skimmed that paper about modular implicits, but it does seem inspired by Scala implicits, yet another earlier work to make ad hoc polymorphism useful.

joppy 5y ago
What's wrong with newtypes is that if you want to define "the monoid of integers under addition" and "the monoid of integers under multiplication" (or similar, the second isn't really a monoid because of zero), then an expression like a*x+b becomes some kind of newtype hell: toAdditive ((toMultiplicative a) <> (toMultiplicative x)) <> toAdditive b or something similar. This is of course an insane way to program, and so really what is done is that we define two entirely different operations of addition and multiplication so that they can be used without newtypes. What would be cool is if operations could ad-hoc be bound to instances of typeclasses, for instance you could accumulate a list of integers inside the (0, +) monoid, or inside the (1, *) monoid. Of course this is basically what the fold functions in Haskell do, but you could imagine being able to formalise this pattern at the type level in a less newtype-hellish way.
- gugagore 5y ago
  I don't know why the Wikipedia article says otherwise, but 0 poses no problem for the integers to be a monoid under multiplication. Right? You just need an identity and associativity, not inverses.
  - joppy 5y ago
    Yeah you're totally right, my bad.
- greydius 5y ago
  > toAdditive ((toMultiplicative a) <> (toMultiplicative x)) <> toAdditive b > This is of course an insane way to program If you have a set with two binary operations, then a monoid isn't the correct abstraction. How would you propose to define <> so that a<>x<>b means ax+b and not e.g. a+xb. And how would your proposal be materially different from newtype conversions?
  - joppy 5y ago
    > If you have a set with two binary operations, then a monoid isn't the correct abstraction. I guess my point is that even if I used "the correct abstraction" here, meaning a ring or something, then the whole newtype setup still makes it annoying for me to split off one operation and feed it into a function expecting a monoid: the way that fold and friends work is much more natural, just taking a starting value 1 and an operation * for example, rather than some kind of "Multiplicative" newtype or whatever. In general I see a lot of the abstract algebra type towers in Haskell and Purescript as being unhelpful, and making a huge assumption that (for example) there will rarely be two monoid instances on a type. In reality in abstract algebra we use tons of different operations on the same objects all the time, and I really just want to define those operations and then be able to use them.

curtisf 5y ago

Having canonical implementations is a feature, not a bug, of type-classes. For example, consider the type `Data.MaxHeap a`, which is a persistent max-priority heap. Max-heaps can be combined in logarithmic time, as long as they are ordered internally by the same ordering. Haskell provides `Data.Heap.union :: Ord a => MaxHeap a -> MaxHeap a -> MaxHeap a`. This is only possible because the type guarantees that the ordering of the two MaxHeaps is the same (the one single implementation of `Ord a`). It also means that you don't have to store any v-table within the `MaxHeap` value, making lookup just a bit faster and making optimizations like monomorphization easier. If you didn't have canonical implementations, you would have to give up being able to write safe & efficient data-structures like this. You would need to be able to dynamically store orderings (wasting space), dynamically compare orderings (wasting time), and have redundant failure paths only for the extremely uncommon and undesirable case where you try to `union` two MaxHeaps with different internal orderings (MaxHeap a -> MaxHeap a -> Maybe (MaxHeap a)). ----- An alternative might be dependent types, where you can instead insist that the ordering _values_ within the two heaps are compatible, gaining the efficiency (by using "ghost" variables) and safety of canonical implementations while avoiding the , but this is more complicated to use, and Haskell doesn't have proper dependent types (yet?). ---- However, in most situations where you might want to try violating canonical instances, defining a newtype is a perfectly satisfactory way to do it.

jules 5y ago
If you compare it with how you'd implement such a data structure using ML modules, it becomes very clear that the bug here is the definition of Data.Heap.Union, not the non-canonicity of type classes. With ML modules you'd define a Heap module that is parameterised by an Ord module. Different instantiations of the Heap module for the same type `a` but different instances of `Ord a` are different: heaps with Ord1 are of a different type than heaps of Ord2. From this point of view, passing the Ord instance into each individual heap function call (such as union) is clearly not the right setup. The canonicity of type classes is merely a bandaid for that problem.
- tel 5y ago
  Generative functors indeed fixes the issue, but it’s kind of interesting because they’re similar in a way to newtypes. In each case, you generate a new type, distinct from the others, which holds a new implementation of the same interfaces. It comes down to ergonomics where OCaml’s approach tends to make local reasoning easier and Haskell’s approach makes it a little easier to transform structurally isomorphic types into one another by wrapping/unwrapping.

reikonomusha 5y ago

What do you think about most object-oriented languages only allowing one definition of a method per class?

lmm 5y ago
It's infuriating when it means you can't implement the same interface in two ways.
- Joker_vD 5y ago
  Well, how do you chose which implementation will get picked? In my experience, explicit wrappers is the cleanest way ― but then again, I also find explicit casts/conversions (which essentially are the same thing) to be the cleanest way too.
  - lmm 5y ago
    If it would be ambiguous then you would have to specify yes. But for the cases where the required type means there's only one implementation that could work, I don't see the value in having to specify.
    - Joker_vD 5y ago
      Uh, how would such an interface look? The one that can be implemented in two ways, and yet "the required type means there's only one implementation that could work"?
      - lmm 5y ago
        I'm mainly thinking of parameterized interfaces, like `Comparable` or some kind of "Keyed<T>". Another example would be datastructures that can be iterated in multiple ways, e.g. a multidimensional array that can implement both `Iterable<Int>` and `Iterable<Row<Int>>` or something like that. You could have cases where you're passing that to a function that expects Iterable<Int> so it's obvious which implementation you want, and cases where you would have to disambiguate.

whateveracct 5y ago

Canonicity has value tho..to frame it as a design flaw is just wrongheaded.

4ad 5y ago

See instance arguments in Agda: https://dl.acm.org/doi/abs/10.1145/2034574.2034796 https://dl.acm.org/doi/abs/10.1145/2034574.2034796 https://agda.readthedocs.io/en/v2.6.2.1/language/instance-arguments.html https://agda.readthedocs.io/en/v2.6.2.1/language/instance-ar...

remexre 5y ago

My 2c is that it makes a lot of sense to have a single unnamed instance of a typeclass, and have that follow the orphan rules, but to allow other _named_ ones that don't follow those rules. Then, add syntax (possibly reuse TypeApplications' @ prefix?) to explicitly specify a typeclass when referencing a name. Possibly also have some lexically-scoped construct to make the instance that instance search will find be a particular named instance too?