Resolving orphan instance errors

Help
#1

I am attempting to tackle this exercise from chapter 7 in a more generic way.

(Easy) Use lift2 to write lifted versions of the numeric operators +, -, * and / which work with optional arguments.

Here’s one solution:

addApply :: forall f a. Apply f => Semiring a => f a -> f a -> f a
addApply = lift2 add

subApply :: forall f a. Apply f => Ring a => f a -> f a -> f a
subApply = lift2 sub

-- etc.

I’d like to find a solution using type class instances, so I can use the default add instead of my custom addApply.

Here’s an attempt which produces an orphan instance error. I believe I need to create a type for (f a), but I’m failing to find the correct syntax.

instance semiringApply :: (Apply f, Semiring a) => Semiring (f a) where
  add = lift2 add
  mul = lift2 mul
  zero = apply zero
  one = apply one
#2

That should be possible; I think the type you want is this:

newtype LiftedSemiring f a = LiftedSemiring (f a)

Full answer hidden under this details tag (spoilers):

instance semiringLifted :: (Apply f, Semiring a) => LiftedSemiring (f a) where
  add (LiftedSemiring x) (LiftedSemiring y) = LiftedSemiring (lift2 add x y)
  mul (LiftedSemiring x) (LiftedSemiring y) = LiftedSemiring (lift2 mul x y)add
  zero = LiftedSemiring (pure zero)
  one = LiftedSemiring (pure one)

However, it’s worth noting that such an instance will not be law-abiding. For example, if we choose Maybe for f, then our zero will be Just 0. However, Just 0 * Nothing would evaluate to Nothing, which fails to satisfy the annihilation law (that anything times zero is zero).

2 Likes
#3

Thanks for the guidance.

Is (f a) in LiftedSemiring (f a) considered a single argument? I assumed f would appear as an additional constructor and not be allowed according to the docs which say that newtype is “restricted to a single constructor which contains a single argument”.

Now add works if the arguments are wrapped by LiftedSemiring. Is it possible to use add without wrapping and without creating a new instance for each Apply type?

-- This works
> :t LiftedSemiring (Just 1) + LiftedSemiring (Just 2)
LiftedSemiring Maybe Int

- This works
> :t Just 1 `addApply` Just 2
Maybe Int

-- Ideal behavior
> :t Just 1 + Just 2
Maybe Int

Here’s the snippet I’m using, which contains a few adjustments, since the original did not compile for me:

newtype LiftedSemiring f a = LiftedSemiring (f a)

instance semiringLifted :: (Applicative f, Semiring a) => Semiring (LiftedSemiring f a) where
  add (LiftedSemiring x) (LiftedSemiring y) = LiftedSemiring (lift2 add x y)
  mul (LiftedSemiring x) (LiftedSemiring y) = LiftedSemiring (lift2 mul x y)
  zero = LiftedSemiring (pure zero)
  one = LiftedSemiring (pure one)

addApply :: forall f a. Apply f => Semiring a => f a -> f a -> f a
addApply = lift2 add

That’s an interesting point about whether Just 0 * Nothing should produce Just 0 or Nothing. It seems like there should be a counterpart to the annihilation law for side effects where any operation involving side effects should preserve those side effects. I guess laws shouldn’t have exceptions, but I suspect it’s safer to prioritize tracking side effects over zeros.

#4

Oops, yes, I didn’t bother putting mine in front of the compiler :slight_smile:

The (f a) in LiftedSemiring (f a) is indeed a single argument, yes. If you wrote newtype T = T (Maybe Int), that would also be acceptable, for the same reason.

There’s no way of being able to write Just 1 + Just 2, at least not unless you define your own version of +, because you’d have to write an orphan instance to do that.

I’d suggest the following instead:

liftedAdd :: forall f a. Apply f => Semiring a => f a -> f a -> f a
liftedAdd = lift2 add

infixl 6 liftedAdd as ^+

I think the numerical hierarchy is best left as-is rather than weakening laws to support more instances. At the moment, the hierarchy is all based on well understood mathematical abstractions; if we were to relax the laws so that instances like Maybe Int were permissible, the class would no longer represent a semiring (or a ring, or field, or whatever), and so you’d no longer be able to use existing results which do concern semirings or rings or fields. Additionally the example about Just 0 * Nothing = Nothing is just the first law failure which came to mind; I suspect there are quite a few more, especially if you look to more applicatives than just Maybe.

1 Like