Semigroup with zero element (Zero) and `Zero z => Applicative (Tuple z)` instance

Change Proposals
#1

In Haskell we have Data.Zero.

I need the same in PureScript in order to make Zero z => Applicative (Tuple z).

However, I’m not allowed to define such orphan instance in my codebase.

Is there a chance to place Zero z => Applicative (Tuple z) in Control.Apply or Data.Tuple in order to avoid a newtype wrapper?

I would go like this:

-- Semigroup with zero value, fulfilling law: `zero <> x = zero = x <> zero`
class Semigroup s <= Zero s where
  zero :: s

instance Functor (Tuple c) where
  map f (Tuple c a) = Tuple c (f a)

instance Semigroup c => Apply (Tuple c) where
  apply (Tuple c1 f) (Tuple c2 a) = Tuple (c1 <> c2) (f a)

instance Monoid c => Applicative (Tuple c) where
  pure = Tuple mempty
else
instance Zero c => Applicative (Tuple c) where
  pure = Tuple zero

What do you think?

#2

I just found out that instance Zero c => Applicative (Tuple c) breaks Applicative

  1. identity law (pure id <*> v = v)
  2. composition law (pure (.) <*> u <*> v <*> w = u <*> (v <*> w))

So something deeper is going on here. Consider the idea immature yet.

#3

Several years ago when I was first learning PureScript, I wrote up a long issue proposing that this sort of thing (instance chains backtracking if their constraints can’t be satisfied) would be useful. It was a bit too much of a deviation from the prior art and literature on the topic, unfortunately, and truth be told I’m a little embarrassed by it now (despite how kind the maintainers were when explaining to me why that wasn’t what they wanted to spend novelty budget on).

But anyway, entirely regardless of whether your proposal is law abiding, this implementation won’t do what you want. If two instances in a chain have the same heads, then the first one will always be selected, even if the constraints for that instance end up not being satiable. Sorry.

2 Likes
#4

I think this very point (A => B is not "check if there is an instance for A and if you find one here is a way to have B but rather “hey this is a B here is how but please find me a A so I can do my job”) is a pit especially newer people always fall into (and for good reason - I was just the same and the way the ideas are presented makes this misunderstanding basically the default IMHO)

So I don’t think there is anything to be embarrassed about for anyone.

By the way to you know any literature/link that explains this really good? Or do you think one has to read implementations to actually understand?

#5

Jordan’s Reference describes this as a gotcha in a very accessible way.

1 Like
#6

In my experience, the most straightforward way to describe this is using normal term-level case. Instance dispatch is effectively “type case”, where the head is the pattern, and constraints + where definitions are the branch body. It’s important to note that constraints and the where definitions go together, as the constraints are used to satisfy the demands of the definitions being constructed (the syntax order really does not help here). Backtracking on instance constraints would be kind of like trying the next pattern match if there was an exception of some kind in a particular case branch. It’s… weird? Or really, it’s too broad. If you want to follow a branch given some term predicate, you would use a guard. That is, there’s special syntax for restricting the term you actually want to test. We don’t have anything like guards for instance dispatch. There’s no reason why it can’t exist, it just doesn’t.

1 Like