1. 11
  1.  

  2. 7

    In short, without canonical instances (not only from the programmer’s POV, but also from the type system’s POV), type classes don’t work.

    An alternative that doesn’t require canonical instances is ML-style modules, which Scala can encode to some extent. But, for some reason, this alternative hasn’t been extensively explored.

    1. 4

      for some reason, this alternative hasn’t been extensively explored.

      They’re inconvenient when most times people just want overloading with canonicity. ML modules need a lot of support from the compiler to be convenient. I’ve only seen oddball SML dialects do this convincingly.

      IMO, they solve orthogonal problems even if the implementation has some overlap and in an ideal world I would have both.

      1. 4

        What I actually want is coherence, e.g., the following two instances shouldn’t be available in the same module:

        instance Applicative [] where
          pure = repeat
          (<*>) = zipWith ($)
        
        instance Monad [] where
          (>>=) = flip concatMap
        

        But I’m perfectly fine with these instances being available in different modules.

        Canonicity is just one particular way to obtain coherence. Canonicity has both benefits (simplified reasoning about instance availability) and drawbacks (loss of modularity, need for a newtype mechanism), and I reckon that, as programs grow larger, the latter become more prominent than the former.

        With ML-style modules, there are other ways to obtain coherence:

        (0) Put all related instances in the same module. Put unrelated instances in different modules.

        (1) Parameterize abstract types (like Heap, Map, etc.) by entire algebraic/relational structures, rather than just their carrier types. Functors (in the ML sense) naturally lend themselves to this style:

        signature ORDERED =
        sig
          type key
          val compare : key * key -> order
        end
        
        functor OrderedMap (Key : ORDERED) : MAP =
        struct
          type key = Key.key
          type 'a entry = key * 'a
        
          datatype 'a map
            = Empty
            | R of 'a map * 'a entry * 'a map
            | B of 'a map * 'a entry * 'a map
        
          (* red-black tree implementation... *)
        end
        
        structure Map1 = OrderedMap (Int)
        structure Map2 = OrderedMap (Backwards (Int))
        
        (* Map1.map and Map2.map are different abstract types! *)
        
        1. 3

          Coherence ain’t good enough. Canonicity is what gives you refactor-safety. If I have to be afraid of changing my imports, then I need to write a compiler that has typeclasses. I’d prefer it if GHC enforced this more rigorously (Rust already does).

          Let typeclasses be typeclasses and modules be modules. Don’t try to convince people to break one so you can pretend you have the other. You can have both in the same language but nobody wants to do the work.

          1. 3

            You only need canonicity to prevent the problems caused by overloading, and this comes at the expense of modularity. The alternative is to just say no to overloading.

            1. 3

              and this comes at the expense of modularity.

              Someday I will write an examination of modularity fetishism from a critical perspective, but until that day…

              It doesn’t matter. In unifying them with proper implementations of each, you’ll be giving up the abstraction of typeclass instance scope…and that’s appropriate because that’s what typeclasses are for.

            2. 2

              Coherence ain’t good enough. Canonicity is what gives you refactor-safety. If I have to be afraid of changing my imports, then I need to write a compiler that has typeclasses. I’d prefer it if GHC enforced this more rigorously (Rust already does).

              Can you clarify this? I can’t see what you mean.

              1. 2

                Of course, I’m not bitemyapp, but in most likelihood, he’s talking about the following problem. Consider the type Map k v. This type is meant to be used with an Ord k instance. If you could define two different Ord k instances in separate modules, then you could create multiple values of the same type (Map k v), whose elements are sorted differently internally, which is a violation of the Map abstraction. This is (part of) what I meant at the root of the thread, when I said “type classes don’t work without canonicity”.

                ML’s solution is different, and IMO better. For starters, you don’t define a type Map k v. You define a functor which maps the entire Ord k instance (not just the type k) to a unary type constructor (parameterized by v). If you apply the functor to two different Ord instances, you get two different unary type constructors (enforced by the type system), even if both Ord instances have the same underlying carrier type k.

      2. 4

        On a related note: I’ve tackled the problem of overly verbose type class inheritance encoding in Scala by building a type class syntax using macros. https://github.com/maxaf/dandy

        My conclusion was the same: one type class can build upon another not by subtyping but by injecting an instance of the other type class.

        1. 2

          This is cool. What are the non-goals you mention at the end? Would projects that use Simulacrum such as Cats miss them?

          1. 4

            I’m specifically not quite enchanted by the chase after ops syntax (i.e. implementing operations such as |+| exposed by semigroups). Likewise, Simulacrum is not after reducing type class syntax boilerplate in general. They’ve been mostly focused on operators, which I personally see as secondary.

            My README doesn’t make very clear the intent to data model the hell out of type classes, then expose a concise syntax for instantiating the underlying model. In such an arrangement it would be possible to implement any arbitrary set of type class features.