Opaque types and accidental recursion

Language Design
1

I’ve been playing a lot with opaque types and have repeatedly hit bugs where I accidentally make self-recursive methods.

opaque type MyErr[T] = Either[String, T]
object MyErr[T] {
  implied PureErr[T] for Pure[MyErr[R]] {
    type EitherString[T] = Either[String, T]
    def pure[A](x: A): MyErr[A] =
      the[Monad[EitherString]].pure(x)
  }
}

Depending on the phase of the moon, the call to pure /within/ pure will end up invoking MyErr.PureErr.pure, resulting in an infinite loop. The code compiled because it is within the MyErr object, where things are coerced between the opaque type lhs and rhs.

My suggestion would be to emit an error if any method within an opaque companion object recurses without being annotated as recursive. It is, in my experience, always an error.

2

I can’t understand how your implementation of pure can be self-recursive.

Your implementation calls function pure of type Monad[EitherString]. But MyErr.PureErr is not an instance of Monad[EitherString] even if we know that MyErr[T] is Either[String, T].

Moreover, code that you supply could not compile. At least, you have type-parameter of object and you have an undefined type R in the expression Pure[MyErr[R]]. Also, your Pure seems to accept types with no type arguments (unlike a Monad that accepts a type constructor). This seems to be a non-sense.

I’ve rewritten your example to be compilable with 0.13.0-RC1 and it works like a charm:

opaque type MyErr[T] = Either[String, T]
object MyErr {
  implied PureErr for Pure[MyErr] {
    type EitherString[A] = Either[String, A]
    def pure[A](x: A): MyErr[A] =
      implicitly[Monad[EitherString]].pure(x)
  }
}

Usage was

implicitly[Pure[MyErr]].pure("yes!")
// returns Right("yes!") as expected

Here are ancillary definitions (to not to require any dependencies):

trait Pure[F[_]] {
  def pure[A](x: A): F[A]
}

trait Monad[F[_]] extends Pure[F]

type Ei[E] = [A] => Either[E, A]
implied [E, A] for Monad[Ei[E]] {
  def pure[A](x: A) = Right(x)
}

Talking not about your particular example but about the general idea of requiring annotation of recursive functions in the opaque type’s companion, I personally think that opaque type’s companion is not a too special place. Either we shouldn’t require such annotation or we should require it everywhere.

3

It’s a phase of the moon thing regarding implied instances lookup. When the moon is in the wrong phase, the compiler sees EitherString[T] = Either[String, T] and unifies it with opaque type MyErr[T] = Either[String, T] so that the[Monad[EitherString]].pure(x) becomes PureErr.pure(x).

The special thing about the opaque companion is that it can see both sides of the opaque type, making these kinds of accidental recursive definitions possible.