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.

Vacationist

type Arbitrary simply means "treat this as a type to be refined by future references/context". You can remove it and replace it with def apply[Arbitrary](f: F[Arbitrary] => Arbitrary)... and it will still compile. – Spokesman

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 */ }

Endless

Thanks for the answer! One quick question about the Capture pattern, what is the idea behind it, or in other words what was the process that lead to it? I watched a presentation by Rob Norris (youtube.com/watch?v=7xSfLPD6tiQ) he did something I liked very much, he started from a case class definition and showed the process of abstractization that lead him to Cofree and Fix. Can something similar be said for this capture pattern? – Vacationist

In this particular example with validating errors, I think the pattern captures the call that returns the error message associated with an error. Then the error messages can be retrieved and displayed for the user. Aside from this, one issue that I have with the example is why use this method instead of simply building the error message. – Vacationist

I'd say this pattern itself is not particularly bound to capturing errors - it's a convenient way of defining polymorphic function [A]: F[A] => A and lifting it to a type class. Capture is just an use case for this pattern/implementation detail, and the error validation from the article could be analyzed in separation (because you could implement it in a different way, though probably with slightly changed syntax). – Endless

I reworded this a bit, but I am no Rob Norris and this is not a conference, so I don't plan to improve this answer much more. – Endless

Thanks again! I appreciate it and I think your comment above (polymorphic function lifted to its "box" type class ) clarified it for me – Vacationist

I'm glad to hear that :) – Endless