Validation and capturing errors using an algebra

Question

I came across this article on medium: https://medium.com/@odomontois/tagless-unions-in-scala-2-12-55ab0100c2ff. There is a piece of code that I have a hard time understanding. The full source code for the article can be found here: https://github.com/Odomontois/zio-tagless-err.

The code is this:

trait Capture[-F[_]] {
  def continue[A](k: F[A]): A
}

object Capture {
  type Constructors[F[_]] = F[Capture[F]]

  type Arbitrary

  def apply[F[_]] = new Apply[F]

  class Apply[F[_]] {
    def apply(f: F[Arbitrary] => Arbitrary): Capture[F] = new Capture[F] {
      def continue[A](k: F[A]): A = f(k.asInstanceOf[F[Arbitrary]]).asInstanceOf[A]
    }
  }
}

Here are my questions:

• how does the scala compiler solve/handle the Arbitrary type given that the type is declared in an object? It seems to depend on the apply method parameter type but then how does that square to the fact that Capture is an object and you can have multiple apply calls with different types? I came across this post What is the meaning of a type declaration without definition in an object? but it is still not clear to me.
• according to the article the code above uses a trick from another library https://github.com/alexknvl. Could you please explain what is the idea behind this pattern? What is it for? I understand that the author used it in order to capture the multiple types of errors that can occur during the login process.

Thanks!

Update:

First question:

Based on the spec when the upper bound is missing it is assumed to be Any. So, Arbitrary is treated as Any, however, it doesn't seem interchangeable with Any.

This compiles:

object Test {
    type Arbitrary

    def test(x: Any): Arbitrary = x.asInstanceOf[Arbitrary]
  }

however, this doesn't:

object Test {
   type Arbitrary

   def test(x: Any): Arbitrary = x
}

Error:(58, 35) type mismatch;
 found   : x.type (with underlying type Any)
 required: Test.Arbitrary
    def test(x: Any): Arbitrary = x

See also this scala puzzler.

Answer 1

This is a little obscure, though legal usage of type aliases. In specification you can read type alias might be used to refer to some abstract type and be used as a type constraint, suggesting compiler what should be allowed.

• type X >: L <: U would mean that X, whatever it is, should be bound between L and G - and actually any value that we know fulfill that definition can be used there,
• type X = Y is very precise constraint - compiler know that each time we have Y we can call it Y and vice versa
• but type X is also legal. We use it usually to declare it in trait or something, but then we put more constraints on it in extending class.

  trait TestA { type X }
  trait TestB extends TestA { type X = String }
  

  however, we don't have to specify it to a concrete type.

So the code from the question

    def apply(f: F[Arbitrary] => Arbitrary): Capture[F] = new Capture[F] {
      def continue[A](k: F[A]): A = f(k.asInstanceOf[F[Arbitrary]]).asInstanceOf[A]
    }

can be read as: we have Arbitrary type we know nothing of, but we know that if we put F[Arbitrary] into a function, we get Arbitrary.

Thing is, compiler will not let you pass any value as Arbitrary because it cannot prove that your value is of this type. If it could prove that Arbitrary=A you could just write:

    def apply(f: F[Arbitrary] => Arbitrary): Capture[F] = new Capture[F] {
      def continue[A](k: F[A]): A = f(k)
    }

However, it cannot, which is why you are forced to use .asInstanceOf. That is why type X is not equal to saying type X = Any.

There is a reason, why we aren't simply using generics though. How would you pass in a polymorphic function inside? One that does F[A] => A for any A? One way would be to use natural transformation (or ~> or FunctionK) from F[_] to Id[_]. But how messy it would be to use it!

// no capture pattern or other utilities
new Capture[F] {
  def continue[A](fa: F[A]): A = ...
}

// using FunctionK
object Capture {

  def apply[F[_]](fk: FunctionK[F, Id]): Caputure[F] = new Capture[F] {
    def continue[A](fa: F[A]): A = fk(fa)
  }
}

Capture[F](new FunctionK[F, Id] {
  def apply[A](fa: F[A]): A = ...
})

Not pleasant. Problem is, you cannot pass something like polymorphic function (here [A]: F[A] => A). You can only pass instance with polymorphic method (that is FunctionK works).

So we are hacking this by passing a monomorphoc function with A fixed to type that you cannot instantiate (Arbitrary) because for no type compiler can prove that it matches Arbitrary.

Capture[F](f: F[Arbitrary] => Arbitrary): Capture[F]

Then you are forcing the compiler into thinking that it is of type F[A] => A when you learn A.

f(k.asInstanceOf[F[Arbitrary]]).asInstanceOf[A]

The other part of the pattern is partial application of type parameters of sort. If you did things in one go:

object Capture {
  type Constructors[F[_]] = F[Capture[F]]

  type Arbitrary

  def apply[F[_]](f: F[Arbitrary] => Arbitrary): Capture[F] = new Capture[F] {
      def continue[A](k: F[A]): A = f(k.asInstanceOf[F[Arbitrary]]).asInstanceOf[A]
    }
}

you would have some issues with e.g. passing Capture.apply as a normal function. You would have to do things like otherFunction(Capture[F](_)). By creating Apply "factory" we can split type parameter application and passing the F[Arbitrary] => Arbitrary function.

Long story short, it is all about letting you just write:

• takeAsParameter(Capture[F]) and
• Capture[F] { fa => /* a */ }