Constraints and overlapping instances

[rhendric]

class Foo a
instance equatableFoo :: (Eq a) => Foo a

data Bar = Bar
instance barFoo :: Foo Bar

Given that there is no Eq Bar instance, should these two instances be allowed? PureScript 0.12.4 complains of overlapping instances.

I know instance chains would be one workaround for this minimized example, but suppose Foo and equatableFoo are put in one file, and Bar and barFoo in another—then instance chains wouldn't help, but provided that no Eq Bar instance is defined in Bar's file, I think the compiler should still be able to determine that barFoo doesn't overlap with equatableFoo, right?

(I didn't find an exact duplicate for what I want, but #3120 seems related—that enhancement asks for constraints to be treated as guards in instance chains, with first-to-match semantics; and this asks for constraints to be treated as sort of like guards in overlapping instance sets, with exactly-one-match semantics.)

[garyb]

If by "should" you mean in an ideal world, then maybe 😄

But as things are, it is right that they are not allowed - instance resolutions works by looking at the instead head (type part) only, and then only afterward are constraints checked. So a and Foo are considered to be overlapping, since a includes all types.

[hdgarrood]

It's perhaps worth noting that GHC also rejects this as overlapping, although you only get an error when you attempt to use the instance:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
module Main where

class Foo a where
  foo :: a -> Bool

instance (Eq a) => Foo a where
  foo _ = True

data Bar = Bar

instance Foo Bar where
  foo _ = False

main = putStrLn $ show $ foo Bar

produces

Main.hs:16:26: error:
    • Overlapping instances for Foo Bar arising from a use of ‘foo’
      Matching instances:
        instance Eq a => Foo a -- Defined at Main.hs:8:10
        instance Foo Bar -- Defined at Main.hs:13:10
    • In the second argument of ‘($)’, namely ‘foo Bar’
      In the second argument of ‘($)’, namely ‘show $ foo Bar’
      In the expression: putStrLn $ show $ foo Bar
   |
16 | main = putStrLn $ show $ foo Bar
   |             

I'm not particularly familiar with the tradeoffs here, but I think I can at least say that having contexts affect resolution could make instance resolution quite a bit more complicated to follow, as well as complicating the implementation quite a bit, so I'd suggest not implementing this.

[rhendric]

GHC is not as strict about orphan instances as PureScript is, and orphan instances would make my proposed behavior much more non-local, so I wouldn't suggest this for GHC, but maybe it makes sense for PureScript?

I'm not very familiar with the tradeoffs here either, although it's clear that this would change constraint solving from being a relatively deterministic, constraint-to-instance-to-more-constraints process to something that might involve some backtracking (but not in a way that slows down compiling any existing code, due to PureScript's current restrictions). I'm (perhaps naively) optimistic about the code for that being pretty easy to follow, and I'd be happy to risk the implementation time trying it to see if you like it—but if the idea is a no-go at the conceptual level that would be silly.

To be clear, I don't think I'm suggesting the compiler should do anything more complicated than handling the specific case where for a pair of instances, one instance's head is an unknown but with constraints, and the other instance's head is known; and handling that case entails trying to solve the constraints for the known instance head. (The code might get more complicated than that, because let's not do the work to solve those constraints twice and all—but conceptually, that's the request.)

If the value of this feature is unclear and practical use cases would swing the balance, I can offer more words about my real-world motivations.

[garyb]

I think that proposal to restrict it to work "guard style" for instance chains is intended as a way of keeping things local. I don't know if anyone has the consequences of doing this kind of thing really, it seems like there should be something out there though, as it is an "obvious" thing to want.

[hdgarrood]

I’ve thought about this a bit more and I’m pretty certain that I don’t want us to implement this, for a few reasons:

1. It removes existing guarantees. If I write instance barArray :: Foo a => Bar (Array a) then I know that Array a only has a Bar instance when a has a Foo instance. Adding this feature removes this guarantee. I haven’t verified this but I expect that people are making use of this guarantee currently, whether knowingly or not.
2. It could make instance resolution harder to follow. It’s already very possible to come up with examples where it is difficult to determine why a particular instance does or does not exist (for example, the machinery required to implement generic deriving can already get pretty involved); this feature adds a lot of power, which inevitably comes with a lot more scope for making a big mess.
3. None of us fully understand the trade offs or consequences of doing this.
4. I think this is too much of a special case, and I think it could easily grow arms and legs. It might be simple enough to implement this one special case, but if we had this, it seems very reasonable to ask that e.g.

   instance Eq a => Foo a
   instance Show a => Foo a
   instance Foo Bar

   becomes allowable too, provided that Bar has neither an Eq nor a Show instance. edit: this is not a good example, see below
5. It will make compilation slower, and will make type class resolution harder to optimise (since the algorithm would have to become more complex). Existing code might not be too adversely affected, but surely if we are implementing a feature it’s because we expect people to use it?
6. It’s only slightly more flexible than what instance chains already give you. edit: instance chains don't give you this, that's why Allow guards in instance chains #3120 exists

[hdgarrood]

I’ve realised the example in my point 4 above is not a very good one, because it still doesn’t make sense if we did add this feature; of course we’d need to require that no types to be both Eq and Show for that to work, which is untenable.

I came up with another issue with this though: it would mean that adding an instance has to be treated as a breaking change. Imagine version 1.0.0 of purescript-bar exports a data type Bar with no Eq instance, and then a downstream package purescript-foo defines a class Foo with instances as in your original example. Now, if purescript-bar makes a new release with an Eq Bar instance, purescript-foo no longer compiles.

[rhendric]

I came up with another issue with this though: it would mean that adding an instance has to be treated as a breaking change. Imagine version 1.0.0 of purescript-bar exports a data type Bar with no Eq instance, and then a downstream package purescript-foo defines a class Foo with instances as in your original example. Now, if purescript-bar makes a new release with an Eq Bar instance, purescript-foo no longer compiles.

Ah. That, I concede, could be a hill worth dying on.

A somewhat weaker form of this objection also applies to #3120, does it not? If you use overlapping instances in an instance chain, a dependency could add an instance which causes code in your module or a downstream module to select an earlier instance in the chain. This is weaker in two senses: first, it only changes which instance is selected instead of failing to compile (is that truly better though?); second, one doesn't accidentally write an instance chain—it could just be a strong best practice that if you write overlapping instances in your instance chain, you had better be truly indifferent about which is selected. What are your thoughts on that? I could rechannel my efforts into implementing #3120 and get almost as good a solution for my use case, but if that's also a no-go, I have a bigger problem.

[hdgarrood]

Yes, it does also apply to #3120, although in the case of an instance chain I think it's slightly less of an issue because you're explicitly casing on whether a particular instance exists, so presumably you want the behaviour to change if an upstream data type gets an instance it didn't previously have.

That said, I think my objections 2, 3, and 5 above also apply to #3120, so I'm not particularly keen on doing that either, sorry.

it could just be a strong best practice that if you write overlapping instances in your instance chain, you had better be truly indifferent about which is selected.

I think the whole point of instance chains is to allow you to express things which you previously would have had to resort to overlapping instances to do; if your instances don't overlap then you shouldn't need chains at all.

[natefaubion]

I think guards on instance chains would need a way to scope the backtracking so that you could tell the typechecker when to commit to an instance, otherwise you'll always have to backtrack which will definitely lead to terrible errors and poor performance. That's why the instance chain paper introduces a separate syntactic form for guards.

[natefaubion]

Also, I should say that I am also not keen on this change. I really don't like the idea that I could create a type and it's automatically made instances of things without me opting into it. GHC has default signatures which provide implementations as long as you implement some other class, but you still have to opt into the instance.

[hdgarrood]

@natefaubion

That's why the instance chain paper introduces a separate syntactic form for guards.

The paper you're talking about is Instance Chains: Type Class Programming Without Overlapping Instances by J. Garrett Morris and Mark P. Jones right? Because the impression I had from that paper is that there wasn't a separate syntactic form for guards, they just decided to use a different syntax for instance contexts, and also that instance search can backtrack more generally than just in one particular instance chain:

3.1.3 Backtracking search
Haskell instance search never backtracks: if no two instance heads unify,
then no predicate could be solved by more than one instance. However,
combined with overlapping instances, this complicates reasoning about
instances. Even if an instance could apply to a predicate, it will not be
checked if a more specific instance exists anywhere in the program, and
failure to prove the preconditions of the most specific instance causes
instance search to fail rather than to attempt to use less specific
instances. ilab instance search backtracks when it can disprove the
pre-condition of an instance (either because of a fails clause or because
of a functional dependency). When backtracking, ilab checks clauses within
an instance chain in order. The order in which ilab checks instance chains
is unimportant because clauses in different chains are not allowed to
overlap.

[natefaubion]

I very well could be misremembering. I'd compare it to writing a parser that always backtracks at every alternative regardless of whether any tokens were consumed. There isn't anything "wrong" with this, and you'll still get a working parser, but you're going to get very bad errors without a lot of work, and you're going to probably do far too much work before failing.

Or another way to look at it, if you think of instances chains as type functions, then the head is like a pattern match and the context is like the branch expression. If you backtracked in the context, that would be like backtracking to another pattern if you threw any exception anywhere. We have a separate syntactic construct for value guards, so we should probably have it for type-level guards.

[rhendric]

Okay, let's leave these specific proposals to the side for a moment.

There is sometimes a need to write recursive functions over an open set of possibly non-cooperating data types. A good example is hash from purescript-unordered-collections. It's recursive because it's common (if not necessary) to define hash of a data structure as a function of the hash values of its elements; it's an open set because you want to be able to define new data structures that are hashable; and ideally that would include types that haven't taken a dependency on unordered-collections and therefore didn't explicitly agree to make a Hashable instance. Other examples would include pretty-printing functions (for when show's verbosity is unreadable—which is often, in my experience) or serialization/deserialization functions, or generators for property-based testing. I'm sure you could think of some that I haven't thought of. This sort of thing comes up a lot. Orphans and overlapping instances and the like are frowned upon for good reason, but nevertheless both do appear in Haskell projects, possibly because not having any tools to write these kinds of functions may be even worse than the flaws of these particular workarounds. If nothing else, that should say that being able to write recursive functions over an open set of possibly non-cooperating data types is important and valuable.

So what should PureScript do, if anything, to meet this need?

Logically, the only options are:

1. Ignore it
2. Tweak type classes to solve it
3. Use some other or new language feature to solve it

Let's talk about 1. It's obviously the most attractive from the perspective of a language maintainer, and as someone who occasionally has to tell petitioners that the thing they want isn't a good fit for a language I help to maintain, I promise I'm sympathetic to that position. But these are the options of a programmer trying to write a generic function like hash and friends in PureScript today:

1. Literally write it using Generic. You can add some special cases with instance chains, but that's it. Your function will never work on any data type that doesn't or can't have a Generic instance unless you take it as a dependency in your package. Users of your function will never be able to add cases that are faster than Generic-using code for their own types, or that vary in any other way from your implementation.
2. Write some instances and, maybe, provide a convenience genericHash or whatever function that someone else could use to write their own instances. Users of your function can add cases for their own types, but for someone else's types, they have to beg that person to add an instance to their package, or do possibly extensive newtype gymnastics. It is super un-fun when you have a complex, recursive data type and you discover that you need to map that to an extremely similar data type that holds all the same data but wraps one of the types involved in a newtype that you cook up just so you can define an instance to make your data serializable. (This is, incidentally, why *recursive* is an important qualifier in my problem statement; data fed to non-recursive functions are much easier to newtype, so existing tools suffice.)

I could be missing something, but I think that's it. I don't think this is a good place to be, and I doubt I'm alone in that! I say that not to be critical of PureScript's evolution thus far, and obviously I'm interested in helping and not just complaining. But I hope to start with a mutual recognition that this is a problem which deserves a better solution.

So option number 2: tweaking type classes, by adding some limited backtracking to instance resolution, or adding guards to instance chains, or something else.

If type classes are the answer to supporting recursive functions over open sets of possibly non-cooperating data types, and instances of classes are how you add new behavior to such functions, then adding an instance will be a potentially breaking change no matter how the feature works. It's unavoidable—if you write a function with behavior that's extensible through the participation of other modules but doesn't require that participation, then modules can change that function's behavior in a potentially breaking way. The question is how and whether this can be limited so that people don't live in fear every time they make something Traversable, and so that people don't worry, as @natefaubion objected, that types will be automatically made instances of things they oughtn't.

Maybe—and bear with me, this is a little half-baked as a proposal—there are actually two kinds of type classes. Type classes like Traversable are interpreted as a property of the type(s) they describe—this is something that an Array or whatever is—and their methods are things you can do as a consequence. The implementation is almost secondary. Type classes like Hashable, by contrast, are more about the functionality of the system that the type(s) in question need to integrate with. They are implementation first and specification second—the specification exists to guarantee your program doesn't crash when you add something to a HashMap, not to guarantee some mathematical property you may be assuming. I find it hard to imagine the sorts of people who go to war over whether or not Set is or ought to be a Monad getting as worked up over whether or not Set is pretty-printable. And there's a world of difference to me between someone automatically making my custom Complex number type serializable (‘oh, thanks!’) and someone automatically making it a Monoid (‘uh, wait... which one? why privilege that one when we have Additive and Multiplicative?’).

I would venture that type classes of the first kind (Traversable, Monoid) are well-served by the existing restrictions against orphans, overlaps, and so on, but type classes of the second kind are not. If these proposals for making instances more powerful would hurt their suitability for type classes of the first kind, perhaps the thing to do is to mark type classes of the second kind somehow for different treatment? Keyword, pragma, magical superclass a la Partial, the presence of an instance defined in the same file with some property... whatever it is, imagine defining the Hashable class with a marker that enabled limited overlapping or instance chain guards or whatnot, and also signaled to library authors that adding Hashable instances is a breaking change, unlike those other nice, mathematical type classes. No existing code would lose any guarantees, at least until someone adds this marker to a class like Hashable, which is obviously a breaking change.

I know this still leaves a lot of your very good points unresolved—about ability of users to follow instance resolution, about the time complexity of backtracking, especially the FUD about the consequences of trying something new—but I can't even begin to address those until there's some agreement on the goal. Hopefully you agree that PureScript should have a way to write recursive functions over open etc. etc., and maybe you agree that type classes, as the closest thing to a solution we have so far, could in principle be adapted in some way to get all the way there. But that brings me to option 3: a language feature in some different area.

Look, if some solution to the expression problem that isn't type classes is waiting on the roadmap to be implemented... well, I would say ‘great’, but I'm not sure PureScript needs two different approaches to the expression problem. I don't think this would happen. I don't think you think this would happen. I only included it in my list of options so as not to create a false dichotomy, since it's technically possible and I could be wrong about what you're planning! But this comment is too long already so I won't belabor it.

To conclude, I think because PureScript, relative to GHC, makes fewer escape hatches available to its users for getting around the rules, someone trying to write hashing, pretty-printing, serializing, arbitrary-value-generating, and other generally-applicable but special-caseable recursive functions in PureScript has to contend with some severe limitations, even with instance chains in play. I think this is a sufficiently important use case to merit a little bit of rethinking of how some parts of the language—probably type classes—work. The recent addition of instance chains gives me hope that another incremental and well-motivated addition to the language might still be on the table. If I can get you on board with just those ideas, I'm willing to keep pitching different ways to solve the problem for as long as you're willing to read them. Thanks for your engagement so far, and let me know what you think.

[hdgarrood]

I think we could do with a bit more discussion on what you can do about this problem with the language as it is today, as I have a couple of suggestions. Let's suppose that I am depending on both unordered-collections and a third-party library which provides a Complex data type of kind Type -> Type, and suppose also that Complex doesn't depend on unordered-collections (and thus doesn't provide a Hashable instance). Let's also suppose that I have a function genericHash :: forall a. Generic a => a -> Hash a, via which I would like to provide a Hashable a => Hashable (Complex a) instance.

One way I think you can get around the issue by defining a new class locally to your project, and you provide the missing instances via this class and instance chains:

class Hashable' a where
  -- this class will have the same methods as the class I care about
  hash' :: a -> Hash a

instance hashableComplex :: Hashable a => Hashable' (Complex a) where
  hash' = genericHash
-- If there are other third-party types we want to give instances to,
-- we can provide those instances here
else instance hashableSomethingElse :: Hashable' SomethingElse where
  hash' = genericHash
else instance alreadyHashable :: Hashable a => Hashable' a where
  hash' = hash

Now we can use a newtype to allow using the above class together with things which use a standard Hashable constraint:

newtype Hashable' a = Hashable' a

instance Hashable' a => Hashable (Hashable' a) where
  hash (Hashable' a) = hash' a

This is admittedly a bit more noisy, but it has a couple of properties which I think are really nice. Firstly, there's less non-local reasoning required, especially during upgrades of third-party libraries. If I upgrade to a later version of Complex which does provide a Hashable instance, my code doesn't change behaviour without warning; I have to opt in to switching to the default Hashable Complex instance by removing the hashableComplex instance from my instance chain. Secondly, it allows me to provide any number of special cases, and it allows me to use different strategies for each of them! For example, if SomethingElse didn't have a Generic instance either, I'd want to write a hash implementation for it manually.

[hdgarrood]

Oh actually, that doesn't really work does it, because if I want to hash, say, a Maybe (Complex a), then even going via Hashable', instance resolution will look like

Hashable (Hashable' (Maybe (Complex a)))
-> Hashable' (Maybe (Complex a))
-> Hashable (Maybe (Complex a)) -- via the "alreadyHashable" instance
-> Hashable (Complex a) -- fails

[rhendric]

Yup, that pattern works great for defining a new function hash' with the nice properties you enumerate. The trouble comes when you try to browbeat existing infrastructure that depends on hash into using hash' as a substitute, in the way you've observed. Taking this pattern forward results in what I referred to as ‘newtype gymnastics’: map wrap and map unwrap-ing your keys whenever you insert them into or read them from a HashMap, and so on. Or, you can add your own Hashable' case for Maybe a as well... but down that road lies a lot of boilerplate more or less copied from unordered-collections or elsewhere, as you absorb all relevant collection types and data structures into your instance chain, and rely on existing Hashable instances only for primitives—and even after all that, you still have to wrap and unwrap your keys (but only at the top level).

[hdgarrood]

I'm still thinking through your comment but I'll just post a couple more immediate thoughts for now:

Type classes like Hashable, by contrast, are more about the functionality of the system that the type(s) in question need to integrate with. They are implementation first and specification second—the specification exists to guarantee your program doesn't crash when you add something to a HashMap, not to guarantee some mathematical property you may be assuming.

I'm not sure this is the best example, because Hashable does have a mathematical property which is very important for the correct operation of data structures like HashMap, that a == b implies that hash a == hash b; if this isn't satisfied, you'll get duplicate entries in your HashMaps. I think it's also pretty important that if you're giving something a Hashable instance, the instance uses a decent hash function, because otherwise that completely defeats the point of using HashMap. Further,

there's a world of difference to me between someone automatically making my custom Complex number type serializable (‘oh, thanks!’) and someone automatically making it a Monoid (‘uh, wait... which one? why privilege that one when we have Additive and Multiplicative?’).

As it happens I think my reaction to someone automatically making my custom Complex number type serializable would be more along the lines of 'uh, wait ... which one?', because there will often be a number of options: 1+2i could be represented in JSON as any of [1, 2], { real: 1, imaginary: 2 }, { "Complex": [1, 2] }. Of course with serialization, it's often the case that you only care that decode <<< encode = Just, but whenever you have to interface with external systems (or even internal systems which happen to be written in different languages) the differences do matter.

One scenario which I think would be somewhat unpleasant is if one of these default catch-all instances ended up being broken. Imagine Alice maintains a complex number library, and Bob has written some other library which provides a class with a catch-all instance, but neither of them are aware of each other's libraries. Now suppose this catch-all instance applies to Alice's complex number type, but that instance ends up being broken. This puts pressure on either (or both) of Alice and Bob to add a dependency on the other's library and provide a specific instance, even if neither of the libraries really have anything to do with each other.

[rhendric]

I'm not sure this is the best example, because Hashable does have a mathematical property

Fair, having a ‘mathematical property’ probably isn't the best way to describe the distinction. It's possible there is no meaningful distinction, but I feel like there is one and I'm just struggling to characterize it rigorously. It probably has more to do with being part of an interface to a system you can largely treat as a black box, versus being an input to a combinator that you do want to be able to reason about. So yes, Hashable has a law, which is relevant to those who would write Hashable instances and collections that store Hashable values. But it's not (very?) relevant to those who just want to use HashMaps. I would argue that people don't just blindly use power, say, with Monoidal values in the analogous way; you're thinking about the Monoid your value is in before you reach for power, whereas you aren't thinking about the Hashableness of your key before you decide to use a HashMap. Fair warning, I might abandon this definition too. I wonder if you perceive a hint of what I'm trying to describe, or do you actually think there isn't anything there?

Of course with serialization, it's often the case that you only care that decode <<< encode = Just, but whenever you have to interface with external systems (or even internal systems which happen to be written in different languages) the differences do matter.

Granted. Please consider my comments to only apply to the case where the consumer only cares that decode <<< encode = Just. I was thinking that if I had a particular serialization I needed to target, I probably wouldn't use someone else's generic serialization function-and-type-class; I'd specify the serialization for all my types to make sure it was correct. So in that case I'd probably be looking for serialization/deserialization combinators instead of an off-the-shelf type class.

One scenario which I think would be somewhat unpleasant is if one of these default catch-all instances ended up being broken. Imagine Alice maintains a complex number library, and Bob has written some other library which provides a class with a catch-all instance, but neither of them are aware of each other's libraries. Now suppose this catch-all instance applies to Alice's complex number type, but that instance ends up being broken. This puts pressure on either (or both) of Alice and Bob to add a dependency on the other's library and provide a specific instance, even if neither of the libraries really have anything to do with each other.

Two responses: first, with the current language, there's already pressure on either (or both) of Alice and Bob to take the other as a dependency if those libraries are to work together at all; so that specific complaint hardly makes the hypothetical a worse state of affairs. Second, it's pretty obviously a bug in Bob's library if his catch-all instance doesn't satisfy the laws of his own class. If his catch-all is lawful, then I don't know in what sense a consumer can consider it to be broken. It would be nice (ignoring the downsides) if a third party consumer could define an orphan instance specifying a better implementation of Bob's class for Alice's data (one that is faster or produces fewer hash collisions are the examples I have in mind, not one that satisfies more laws), but of course orphans bring their own troubles and I'm not campaigning for that—unless, perhaps, the solution that comes out of the rest of this conversation happens to invalidate the objections to orphans as well.

[hdgarrood]

Fair warning, I might abandon this definition too. I wonder if you perceive a hint of what I'm trying to describe, or do you actually think there isn't anything there?

I haven't made up my mind yet 😄

there's already pressure on either (or both) of Alice and Bob to take the other as a dependency if those libraries are to work together at all; so that specific complaint hardly makes the hypothetical a worse state of affairs

I think it does give us a worse state of affairs: previously, attempting to use Alice's data with Bob's class, you would end up with a failure at compile time. Now, you end up with a failure at runtime. I think this does increase the pressure on one or both of Alice and Bob because runtime failures are rightly considered to be worse than compile time failures. Then again I suppose it is fairly clearly a bug in Bob's library.

[hdgarrood]

Honestly, I think I'm kind of grasping at straws here to keep the conversation going; my responses to this thread are mostly guided by my feelings that the language and community is best served by reducing the number of type system features we're putting in (which I've expanded more on in a Discourse thread "Thoughts on future additions of type-level features"). In particular I'm not keen on adding type system features which haven't already been discussed in PL academia, because I think that way we run a much larger risk of implementing something which turns out to be broken; see for example the GeneralizedNewtypeDeriving extension in GHC Haskell.

To go back to your original motivation:

There is sometimes a need to write recursive functions over an open set of possibly non-cooperating data types.

I think the viewpoint I'm converging on is that this is just a really difficult problem. Are you aware of any features provided by other languages which can satisfy this need better than either of your 1a and 1b approaches above? Perhaps Scala's implicits? I don't know much about them but I think they suffer from a lot of the same issues as orphans.

Maybe a good approach in this situation is to use regular functions instead of type classes (cf "Scrap your typeclasses"); I think these problems would be a fair bit easier to deal with if you had easy access to value-level versions of any instances which themselves need access to instances of inner types. For example, if I could easily get my hands on functions such as forall a. (a -> Hash a) -> Maybe a -> Hash (Maybe a) at the value level, the need for newtype shenanigans is significantly reduced. It's a lot more boilerplate than type classes, of course, but maybe that's just a compromise you need to make if you find yourself in this situation; maybe writing recursive functions over open sets of non-cooperating data types is actually incompatible with the global coherence requirements of type classes.

[hdgarrood]

You might find this interesting too: https://github.com/reactormonk/modules

[garyb]

One thing I'm not entirely clear on in this discussion is what the problem with newtypes is, in the presence of alaF and such. I'm not saying there's nothing there, I just could do with a bit more context as to why it's a problem that can't be (non-annoyingly) solved with newtypes.

[rhendric]

@garyb

Let's say I've written an algorithm that tosses around a lot of records. I love records in PureScript, partly because their types don't need to be pre-declared, so you can work with a lot of variations on the same type without having to fill your code with similar declarations (unless it makes sense to). For example, I might have a function that accepts

{
  a :: Boolean,
  b :: Int,
  c :: Array (Either (NonEmptyArray String) String)
}

and returns

{
  a :: Boolean,
  b :: Maybe Int,
  c :: Array (Either (NonEmptyArray String) (Tuple String Boolean))
}

.

Having written that function, I now want to lift it over HashSets of those types, via HashSet.map. The problem is that NonEmptyArray is not Hashable.

Now I'm sad, because here are the two options I think I have:

1. I can replace NonEmptyArray everywhere with NonEmptyArray', a newtype wrapper which I can make Hashable. But this needs wrapping and unwrapping every time it interacts with code that expects a genuine NonEmptyArray—maybe this is library code I can't change, or maybe it's just code that I hoped to isolate from the ugliness that is the NonEmptyArray' hack. Code that expected the second of the above types, but is now receiving the NonEmptyArray' version of that type, gets composed with

\{ a, b, c } -> { a, b, c: map (left unwrap) c }

. And of course this logic is different for many of the subtly different anonymous record types my algorithm is using. This adds clutter and brittleness, since it's now more code that needs to change if the details of those record types change, even in ways that don't involve the NonEmptyArrays—for example, adding a d field of any type.

2. I can take the approach suggested in Constraints and overlapping instances #3596 (comment), with a parallel Hashable' class and wrapper newtype, and just wrap the outermost layer of my data before I put it in any HashSets. The wrapping and unwrapping here is just wrap and unwrap regardless of the type, so that brittleness concern is gone. But now I have to replicate a lot of functionality from the original Hashable typeclass in Hashable'—in this example, Hashable' needs to have instances for records, Array, and Either. (They need to be replicated, and not just handled by a catch-all at the bottom of the Hashable' instance chain, because the original instances depend on Hashable constraints for the contained data, but the desired Hashable' instances will need Hashable' constraints.) And if I add more container types, I need to keep reimplementing the wheel. And I do still need to deal with some wrapping/unwrapping clutter, even if it's less clutter and less brittle than in option 1.

I don't see how ala and friends would help me out any. It looks to me like they're applicable if you need to run a function as if the things you are passing it are wrapped in some newtype, but in the case of working with HashSets, I need to pass around some container, including through functions like Set.map, as if the data contained in the container are wrapped in the newtype. If I'm missing something, I'm all ears!

(If the intended resolution to this dilemma is to stop using records in such a free and easy way... well, lightweight anonymous records was one of the biggest attractions of PureScript for my current project, so I really hope that isn't it.)

[MonoidMusician]

I'm wondering about a compromise solution. What if we allow that there be one default instance/instance of last resort, defined in the same module as the typeclass, that is tried only when there would fail to be another instance available. Would this be enough to solve the practical problems we've seen? Would this still work nicely with the rules of the existing typeclass system? I think there's potential in a simple idea like this.

I think it does solve a large number of the common problems with providing instances for types that you do not control. Most of the time, like in the case of hashable, you can write some kind of instance for the typeclass (possibly depending on another typeclass) – it might not be the perfect instance, but it's better than nothing, and there's value in having it autoderived, for convenience and to ease over compatibility concerns.

Note that, since we don't have instance guards, this instance would only be selected when there are no matching instance heads, so I don't think coherence would be a worry. And it wouldn't introduce any functionality like instance guards.

And actually, it should be relatively simple to implement, since we already have instance chains. It would act like the last item of an instance chain. (But in a global manner, not limited to a single instance chain as it currently stands.)

Does this sound reasonable? I know that this kind of feature has no precedent in Haskell, but I think it could work. What say you?

[rhendric]

@hdgarrood

I think the viewpoint I'm converging on is that this is just a really difficult problem. Are you aware of any features provided by other languages which can satisfy this need better than either of your 1a and 1b approaches above? Perhaps Scala's implicits? I don't know much about them but I think they suffer from a lot of the same issues as orphans.

Yeah, Scala's implicits score full marks on flexibility and get a fat zero on keeping dependencies from breaking your code and being easy for people to understand when they get buggy. I loved and hated them when Scala was my primary professional language for a few years.

I think you're right that the problem is difficult but part of my point is that PureScript's design constraints make it especially difficult here, or maybe just especially necessary. In any language that doesn't enforce referential transparency, this kind of thing gets done with a run-time registration pattern, possibly with the aid of a distinct reflection system (Java, .NET), or possibly by extending a prototype (JS) or run-time representation of a base class (Python, Ruby). Of the languages that remain, Haskell permits orphan instances and limited overlapping of instances, and also has things like Template Haskell. Agda's instance arguments don't permit overlap by default, but do allow local instances and backtracking through dependency instance arguments. I'm very unfamiliar with Coq, but from its wiki, it appears to allow multiple instances in cases where Haskell does not. Among languages I know of, PureScript stands alone in the quadrant of ‘referential transparency at all costs’ and ‘instance resolution must always be simple and safe’, and it's here that the problem lives.

I think these problems would be a fair bit easier to deal with if you had easy access to value-level versions of any instances which themselves need access to instances of inner types.

In other words, the combinator pattern. I'll gladly put up with building complex combinator values in some cases. Serialization, for instance; if I only need to communicate one big ADT across the wire, building an instance for that type with combinators is a small price to pay. I'm a lot less happy if I need to build a unique combinator assembly for every different, one-off, complex data type I want to put into a HashSet; see my previous comment. Pretty-printing for debugging purposes is another one of those; ‘I have a bug, it's time to diagnose it, let me Debug.Trace the relevant data real quick, OOPS nope let me spend a minute assembling some combinators so I can do that’ is not a great developer experience.

https://github.com/reactormonk/modules

Without having tried it, that looks awesome. Its implementation, I'd like to note, uses overlapping instances. (And type families, and TH of course.) So that implementation wouldn't fly here, but maybe something like that interface, built into the language directly, would. It would certainly make me happier.

And on that note, have you seen the Cochis paper? Here is a paper from PL academia which formalizes a scheme for resolving implicit values (or type class instances) that supports locally scoped values/instances like the modules library, maintains coherence, and is deterministic. I believe in practical terms, the upshot of this is that you would declare or import instances locally, and when resolving constraints, the matching value in the nearest lexical scope wins. (I'm thinking that existing global type class instances would be treated as if imported into an outermost global scope, and thus would still need to be forbidden from overlapping.) Integrating this into PureScript would entail some new syntax and design decisions (not to mention probably a lot of work under the hood), but it would be backed by research, it wouldn't require anyone to divide type classes into two categories, and I'm pretty sure it would result in a design where adding instances in dependencies still can't change the behavior of downstream code. I'd make a more fleshed-out proposal if you think this might have legs.

[natefaubion]

The problem is that NonEmptyArray is not Hashable.

It's not clear to me how the original proposal (or @MonoidMusician's suggestion) would fix the issue in the given example, since NonEmptyArray is opaque anyway. Can you clarify?

[natefaubion]

I'm assuming the default instance would be implemented in terms of const 0, which the documentation says is undesirable, and presumably you would never actually want to use this implementation. I understand the "but it works" viewpoint, but surely you would want to figure out how to get a real implementation working ASAP? I know it sounds like I'm being a little dense, but I don't think that accepting a poor implementation you'd never want is better than using a newtype as a stop-gap.

[natefaubion]

Additionally, #3351 would make the burden of conversions quite small. Small enough that I personally would opt for newtypes just so I didn't have to accept a poor default implementation.

[rhendric]

It's not clear to me how the original proposal (or @MonoidMusician's suggestion) would fix the issue in the given example, since NonEmptyArray is opaque anyway. Can you clarify?

Heh, fair. The answer is, if my original proposal were to be implemented, I'd go over to unordered-collections and ask real nicely if a Generic-based default instance could be added to the base of the Hashable instance chain—without the proposal, this would be a terrible thing to ask because it would preclude any custom Hashables ever, but with it, I have a shot. Then I guess in this case I would also go to arrays and ask real nicely if NonEmptyArray could get a Generic instance. 😄

(I don't know about @MonoidMusician, but when I'm talking about Generic-based default instances, I don't mean const 0; I mean something that calls from to convert the value into an appropriate composition of Product and Sum and Constructor and Argument and processes those guys to form a meaningful hash value.)

It's a reasonable counter to ask why I don't just go over to arrays right now and ask real nicely for a Hashable instance. But I don't think this general approach scales across the quadratic space of utility classes and data types; taken to its conclusion, library dependencies will balloon out of control. Maybe Hashable gets absorbed into prelude someday and this particular qualm disappears, but then there are the pretty-printers and the serializers and the QuickCheck generators and so on. However, asking data type authors to add Generic instances specifically, and type class authors to add Generic fallback cases, seems more practical.

It's an imperfect solution, though. If something like reactormonk/modules or Cochis ends up being more palatable to PS devs, that's great news to me. I just opened by asking for what I thought would be the least disruptive addition to the language that would offer some way forward.

[natefaubion]

Is there something particularly insufficient about Coercible other than perceived elegance? It's an orthogonal feature that solves the "deep" newtypes problem well at the cost of a function application.

[rhendric]

No, Coercible sounds sweet, and would improve other things besides! I got the impression that the decision to add roles and role inference might delay that proposal indefinitely. I'd hoped this would be a less disruptive alternative. (As this conversation progresses, it's becoming clear that this hope was likely misguided... ah, well.)

[timjs]

I think there are two separate discussions going on here:

1. Declaring an instance that is "more special" than another one (specialisation).
2. Declaring an instance of a non-local class for a non-local type (orphans).

Specialisation

This issue started with an example of specialisation, which is currently not allowed in both PureScript and Haskell. For Hashable one could imagine that the module declaring the class, gives a general instance using Generic. Any other instances, declared in the same package or not, should only overlap if it is more special than the other:

module Data.Hashable where

  class Eq a <= Hashable a where
    hash :: a -> Hash

  instance Generic a => Hashable a where
    hash x = ...


module MyApp where

  data T = ...

  -- Should be perfectly fine because `T` is more special then `forall a. Generic a`
  instance Hashable T where
    hash T = ...

Let me refer to Rust. It's trait system is greatly similar to Haskell's type classes. They studied specialisation at length and implemented it in language. The details are described in a request for comments. So with a good definition of specialisation, it should not affect coherence at all!

Orphans

The problem of instantiating a non-local class (or trait) for a non-local type is really a hard one. These orphan rules are also studied at great length by the Rust community, but they did not come up with an answer yet. Specialisation though, is thought as a way to soften the pain. See this special repository for the orphan problem for a quick overview.

[rhendric]

I believe Rust monomorphizes all functions when they're compiled, correct? This changes some of the trade-offs around specialization; in particular, see this playground. Since Rust makes two copies of call_get_name, it can defer looking up which Named impl to use until that point. PureScript, or any language that passes type class dictionaries to polymorphic functions at run time, would presumably need to resolve the less specialized impl inside call_get_name, which makes that function referentially opaque.

Also, there may be a third category of thing being danced around: overriding, which is when an instance can be declared locally that is meant to replace another instance made available globally. This feature is present in Scala, and in the reactormonk/modules library linked above and the Cochis paper, and when available it can also be used to soften the absence of either of the other features you describe.

[rhendric]

Actually, hey @natefaubion, I have a question about Coercible.

As I've seen it, the usual argument for global instance uniqueness involves a HashMap with conflicting instances of Hashable, right? You build a map with one hash function, then in a different context, try to operate on it with a different one, and your world explodes. Would Coercible enable that by allowing a HashSet (Wrapper Int) to coerce to a HashSet Int, where Int and Wrapper have different Hashable instances? If so, it seems not as safe as advertised. If not, I still have my problem if any of my not-natively-hashable types are inside a HashSet.

[natefaubion]

Would Coercible enable that by allowing a HashSet (Wrapper Int) to coerce to a HashSet Int, where Int and Wrapper have different Hashable instances? If so, it seems not as safe as advertised. If not, I still have my problem if any of my not-natively-hashable types are inside a HashSet.

I don't think so because HashSet wouldn't have a representational role. You coerce before insertion, and after lookup.

[timjs]

I believe Rust monomorphizes all functions when they're compiled, correct? This changes some of the trade-offs around specialization; in particular, see this playground. Since Rust makes two copies of call_get_name, it can defer looking up which Named impl to use until that point. PureScript, or any language that passes type class dictionaries to polymorphic functions at run time, would presumably need to resolve the less specialized impl inside call_get_name, which makes that function referentially opaque.

Rust indeed monomorphises everything. But I think that is not important here. The decision which implementation should be used (or which dictionary should be passed) is still made by the caller (i.e. the calls to get_call_name on lines 20 and 21). The playground example can be expressed in Haskell like this (split in two modules, using a proxy to use the type var a somewhere):

module Upstream where

  class Named a where
    getName :: Proxy a -> String

  instance {-# OVERLAPPABLE #-} Named a where
    getName _ = "unnamed"

  callGetName :: forall a. Named a => a -> String
  callGetName _ = getName (Proxy :: Proxy a)

module Local where
  import Upstream

  data This = This

  instance {-# OVERLAPPING #-} Named This where
    getName _ = "This"

  t0 = ( callGetName (0 :: Int), callGetName This )
  -- > ("unnamed","This")

Thing is, the compiler cannot reduce the context Named a for callGetName in module Upstream, because it does not know if there will be more specialised instances defined elsewhere (as is the case in module Local).

In PureScript you can have the same behaviour only by defining both instances in the same module and chain them together. The overlapping instance cannot be defined in another module, as one can do in Haskell or Rust. That is the pain point. I think specialisation of instances should work without using chains.

[natefaubion]

To this point:

Heh, fair. The answer is, if my original proposal were to be implemented, I'd go over to unordered-collections and ask real nicely if a Generic-based default instance could be added to the base of the Hashable instance chain—without the proposal, this would be a terrible thing to ask because it would preclude any custom Hashables ever, but with it, I have a shot. Then I guess in this case I would also go to arrays and ask real nicely if NonEmptyArray could get a Generic instance. 😄

I don't think NonEmptyArray can have a Generic instance because Array doesn't have a Generic instance, and it isn't clear what that would even look like. I know it sounds like I'm just being pendantic, but I want to make sure we are on firm ground as to what the exact problem and solution space is. In the example you gave, the only robust solution is still to use newtyping.

Note, I'm not saying specialization isn't useful, and I think we should keep discussing it and what it would mean for PureScript specifically (not Rust).

[rhendric]

I don't think NonEmptyArray can have a Generic instance because Array doesn't have a Generic instance

Does that matter? This code compiles fine for me:

import Data.Generic.Rep (class Generic)

newtype NonEmptyArray a = NonEmptyArray (Array a)
derive instance nonEmptyArrayGeneric :: Generic (NonEmptyArray a) _

[natefaubion]

It matters if you try to do anything with it, and if having the instance can let you violate the constraints of NonEmptyArray.

[hdgarrood]

Yeah, Generic only “unwraps” one layer of a structure, so that’s fine. However, NonEmptyArray should not have a Generic instance, because providing a Generic instance effectively makes the constructors public, which breaks the guarantees which make NonEmptyArray useful. Map doesn’t have a Generic instance for the same reason.

[hdgarrood]

Would Coercible enable that by allowing a HashSet (Wrapper Int) to coerce to a HashSet Int, where Int and Wrapper have different Hashable instances? If so, it seems not as safe as advertised. If not, I still have my problem if any of my not-natively-hashable types are inside a HashSet.

Cases like this are what the nominal role is for: if the structure of a value depends on more than the representation of a type argument, for example if it depends on a particular instance that that type argument has. I didn’t understand this until recently and I have been meaning to comment to that effect in the Coercible PR. So coerce :: HashSet Int a -> HashSet Wrapper a should fail to compile because the first type parameter should be marked as nominal.

[hdgarrood]

It's an imperfect solution, though. If something like reactormonk/modules or Cochis ends up being more palatable to PS devs, that's great news to me.

I was under the impression (perhaps incorrectly) that something like reactormonk/modules might be implementable in userland in PS; that was why I brought it up. I haven’t investigated that in any depth though. It’s probably worth looking into if you are interested in this problem.

[natefaubion]

Another point in this design space is class morphisms which sounds like it would let you define a morphism from Generic to Hashable.