Several days ago, we saw the new experimental feature called “capture checking” was announced in the tweet by M. Odersky.

This feature is a new chapter in a decade-long struggle for adding something like an effect system to scala 3. It has some similarities with the linear constraints proposal for Haskell and rust lifetimes.

Disclaimer:

all of the code snippets here are not type-checked and should be considered scala-like pseudo-language

Effect systems

Effect system is some form of metainformation, usually inside the type system. It alerts and checks that the runtime meaning or other semantics of the current expression has some special things, such as side effects, asynchronicity, errors, indeterminism, multiplicity, and whatnot.

A full-blown algebraic effect system needs several components:

• A composition that aggregates all the effects on the go
• A type system that behaves something like a semilattice
• An effect handling that looks something like a "Cut" rule in logic

The first one means that if we write something like foo(bar(x)) or foo(x) + bar(y) where foo has effect A and bar has effect B, that whole operation should have an 'A + B' effect. Where 'A' and 'B' can be anything from mutating some variables to parallel internode communication

A Second one means that you have some "adding" effects operation, commutative and idempotent. That is a + b + a, a + b, and b + a are all the same thing.

A third one means that you can sometimes take some expression with a complex effect like a + b and as soon as you have some "handler" for b you can apply that handler to your expression and get some new expression with only a mark on it.

Scala 3 had several possible mechanisms providing for such a system, notable two are:

• Contravariance
• contextual abstraction

Both are suggesting effects as capabilities. I.e., requiring an object of some type is the mark of effect, and providing a required object is handling.

The first one is based on the fact scala 3 already has a nice subtyping lattice. Meaning having some contravariant type Expr[-_] you can end up with the rule when composing expressions with Expr[A] and Expr[B] will lead you to some Expr[A & B] with all the commutativity and idempotence for free. That was fully exploited by the first version of the ZIO module pattern.

However, "handling" was troublesome since it's not that easy to write a correct runtime that can "subtract" one trait from another, which eventually would lead you to the need of "merging" traits, i.e., providing a general function doing (A, B) => A & B.

That was partially solved first by macros in the "zio-macros" library.

Then, a partial solution based on a TypeTag-keyed HashMap called Has arrived at ZIO. And ZIO-2 is going to make this hashmap completely hidden, leaving a user with types like Console & ReadUser & Postgres, where all of the Console, ReadUser, and Postres types are bare traits and not aliases to Has.

The second option, a contextual abstraction, was particularly interesting to M.Odersky. He felt that the mechanism of implicitly passing arguments during application is the best form of a capability-type of effect system. So having effects of A and B is easy as having contextual arguments of types A and B, i.e., having type (A, B) ?=> Whatever.

This mechanism has a straightforward effect handling - it's just an argument passing. However, it requires more direct typing effort from the user since contextual arguments can't be inferred yet.

Also it lacks basic properties since (A, B) ?=> X is not the same type as (B, A) ?=> X . And what is worse when B is a subtype of A, so A ?=> X is a subtype of B ?=> X for any X it's not true that (A, B) ?=> X is the same as B ?=> X

But those weren't the issues that Martin was sad about. The most considerable trouble for him was a "capability leaking" problem. So imagine you have Database ?=> User. Technically you can provide some Database and now have a pure value of User, but there is no guarantee that some method or function inside the User hasn't captured this Database instance. So you continue your calculation, now free of Database formally and somewhere you start an SQL transaction all of sudden, using an old and maybe closed database session.

The dotty team was so obsessed with this misfortune that it reimplemented one of the most exciting things in rust type system: lifetimes.

Lifetimes

Imagine you have the compiler that builds an application with no garbage collection support and as small copying data as possible. So when you allocate something on the heap or the stack, you need to encourage to reuse this data, using some GC-untracked bare references to the object.

So rust introduced lifetime parameters.

Every function or type can have generic parameters like 'a 'b, these can be further applied to some reference or another generic entity and have meaning "lower bound of how long this reference will leave" or "an interval where this reference is guaranteed to be correct."

So the following couple of definitions have drastically different semantics

If the return type doesn't mention the parameter's lifetime, the function probably performs something, access arguments during it, and constructs the result, totally independent of the argument.

The second means that the function probably uses the argument and puts it the result, so the result type will most likely be incorrect when the initially referenced value is moved or dropped.

Capture checking

The dotty team offers something similar in scala 3. But instead of presenting additional ephemerous types, it represents lifetimes with names of corresponding parameters. The first variant would look traditionally.

And second, now have some exquisite mark on the type

So instead of adding the special named type marks, we can just use argument names as their "lifetimes".

So why is this even relevant to a language with GC-enabled runtime such as scala?

First and most obvious, it solves the "leaky capability" problem. Now whenever Database is a trait marked with the @capability annotation, you can't write Database ?=> User function unless the result is a Database-irrelevant value. Instead It should be something like

So you must somewhere explicitly mark that a result type isn't free of db. Does this enable contextual abstractions as a good effect system? It's hard to answer this, but I think it does a much more interesting thing.

One should be aware that capture checking does not involve "linearity" or another form of substructural typing. If we check carefully, none of the three most common structural rules (weakening, contraction, exchange) is compromised. The most tricky one, "contraction," which provides "reuse" ability, is still safe. Although conclusion types can explicitly refer to a context variable's names, so does the dependent type system, and corresponding logic is not substructural. We can just "reassign" several names to a single variable during contraction.

Resource scopes

A typical resource-aware concurrent application in cats-effect or ZIO uses Resource or ZManaged monadic type. This type is usually based on some underlying asynchronous monad, say F[_], or ZIO, and includes:

• a step to initialize resource
• a step to release the resource.

So typical usage of such type would be resource.use(actions), which is roughly equivalent to

You resource can be compound, you can have several resource allocating procedures and have something like

When you write something like resource.use(actions) whole sequence will look like

Resources have something like a statically known lifetime. Resource c lives from line 4 to 6, b lives from 3 to 7, and a from 2 to 8.

What if we need something like

In this code, we assume that resB and resC only use the resA result during initialization but don't need this during its life so that any function g can reference them without fear. But it seems that flows like that are difficult to express using the current form of static-scoped resource.

RAII

One of the nicest things about lifetimes in rust is that it helps to deal with the resources efficiently.

A code above can be translated to something like

The first thing we can see here - there is no actual need for deallocators, even drop(a) is optional since rust can automatically calculate drop time for each variable.

The second one: although a is dropped, we can freely use b and c since their lifetimes are supposedly not bound to a's.

The third is that we don't have a "resource" type here. Every construction can serve as a resource allocation.

Unfortunately, these niceties are hard to use in the concurrent code. Most popular rust implementations of asynchronicity use a global loop to schedule tasks. Each Task element is a special case of Future and must have a 'static lifetime to be scheduled. That means variables allocated in one task can’t be used as “lifetime tracked” resources in another. So if your "resource" should be used concurrently, it is tough to track its "lifetime."

Capture Checking And RAII

In the new proposal, one can achieve something similar. You can distinguish between three types of usage, such as

The capture annotation before the IO means you can refer {a} during the calculation process. On the other hand, the annotation before B types reflects that the calculation result will still refer to the argument somehow.

That also means that technically we can have something like a resource without the need for different monadic types. Yet we must add some kind of mark on natural "resources", things that need deallocation.

Say the standard calculation will have the type IO[normal, A] and resource-like IO[resource, A], we should adapt our flatMap accordingly. I.e.

That also means we need some more sophisticated for-comprehension (or other sugar) that could terminate flatMaps before the whole expression stops, so that:

could be translated to

Note the left-associated flatMap on resA to close the resource preliminary based on the fact that b and c are not capturing a reference.

We can also add drop(a) here to enforce the correct end of life.

These `normal` and `resource` flags most probably can be thrown out using some additional "capture" annotation such as (r: Release) ?-> {r} Async[A] can be an alias for IO[normal, A] and (r: Release) ?-> {r} Async[ {r} A] will be an alias for IO[resource, A]- a calculation that need some closing job.

So instead of having a particular monad for resources, we can have a scope mark representing scoped operations.

Final thoughts

Resource allocation is just one of the examples of how one can use the new capture checking mechanics.

But it's not the end of the story. In short - I don't think that capture checking is about effect tracking. I believe it's a beautiful tool for scope tracking.

There are much more scope-enabled concurrent problems such as

• Concurrent Locks
• Database sessions
• User HTTP sessions
• STM

Every time we have some auxiliary monadic type translated to IO, we introduce a special scoping, and scopes' interoperations are tricky.

Capture checking adds an ability to have scope intersections and replace every narrow-purpose scope-marking type with a single lexical "capability."

It enables the "intersection" of scopes and possibly eliminates functor zoos in existing concurrent libraries.

In the previous post, we’ve discovered this beautiful structure

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

If some functor representing the tagless continuation of some data is provided as F[_], Capture[F] would represent an initial form of such data.

Contravariance can help represent unions in terms of intersections and vice versa, using the duality.

Capture[F] & Capture[G] = Capture[F | G]
Capture[F] | Capture[G] = Capture[F & G]

Still, we haven’t touched most useful properties of tagless final encoding yet:

1. The ability to represent recursive data definitions
2. The ability to represent HKT

Let’s start with recursion

Free Construction

There are a lot of recursive data structures representing some free constructions.

The one everyone loves is List[A] which is a known form of a free monoid.

Other examples are:

• NonEmptyList[A] is a free semigroup for A
• Option[A] is a free pointed set for A

Let’s define corresponding definitions

trait PointedE[-A, B]   extends (A => B) { def empty: B }

trait SemigroupE[-A, B] extends Semigroup[B] with (A => B)

trait MonoidE[-A, B]    extends Monoid[B] with SemigroupE[A, B]    with PointedE[A, B]

Each of those definitions includes some Algebra[B] paired with embedding A => B.

Having this definition of free structure

trait FreeStruct[Algebra[_], A]{
  def continue[B](embed: A => B, algebra: Algebra[B]): B
}

We’re just merging two arguments into the single trait resulting in

trait FreeStruct[AlgE[_, _], A]{
  def continue[B](algebraAndEmbed: AlgE[A, B]): B
}

This may be simplified as

type FreeStruct[AlgE[_, _], A] = Capture[AlgE[A, ?]]

Having this form we can define the following

type FreeSemigroup[+A] = Capture[SemigroupE[A, ?]]
type FreeMonoid[+A]    = Capture[MonoidE[A, ?]]
type FreePointed[+A]   = Capture[PointedE[A, ?]]

What’s so special about it?

If we require SemigroupE andMonoidE implementations to follow usual Monoidand Semigroup laws,

we can be sure that

• FreePointed[A] is isomorphic to Option[A]
• FreeSemigroup[A] is isomorphic to NonEmptyList[A]
• FreeMonoid[A] is isomorphic to List[A]

Let’s start from the Option:

def fromOption[A](opt: Option[A]): FreePointed[A] =
  new Capture[PointedE[A, ?]] {
    def continue[B](k: PointedE[A, B]): B = 
      opt.fold(k.empty)(k.apply)
  }

def toOption[A](opt: FreePointed[A]): Option[A] =
  opt.continue(new PointedE[A, Option[A]] {
    def empty: Option[A]       = None
    def apply(a: A): Option[A] = Some(a)
  })

Next, take the NonEmptyList:

def fromNel[A](nel: NonEmptyList[A]): FreeSemigroup[A] =
  new Capture[SemigroupE[A, ?]] {
    def continue[B](k: SemigroupE[A, B]): B =  
         nel.reduceMap(k.apply)(k)
  }

def toNel[A](nel: FreeSemigroup[A]): NonEmptyList[A] =
  nel.continue(new SemigroupE[A, NonEmptyList[A]] {
    def apply(a: A): NonEmptyList[A]  = NonEmptyList.one(a)
    def combine(x: NonEmptyList[A], y: NonEmptyList[A]): NonEmptyList[A] = x ::: y
  })

And finally the List

def fromList[A](l: List[A]): FreeMonoid[A] =
  new Capture[MonoidE[A, ?]] {
    def continue[B](k: MonoidE[A, B]): B = l.foldMap(k.apply)(k)
  }

def toList[A](l: FreeMonoid[A]): List[A] =
  l.continue(new MonoidE[A, List[A]] {
    def apply(a: A): List[A]                     = List(a)
    def empty: List[A]                           = Nil
    def combine(x: List[A], y: List[A]): List[A] = x ::: y
  })

Now we can define some basic constructors

def single[A](a: A): Capture[A => ?] = new Capture[A => ?] {
  def continue[B](k: A => B): B = k(a)
}

def combine[A, F[x] <: SemigroupE[A, x]](
   xs: Capture[F], 
   ys: Capture[F]): Capture[F] =
  new Capture[F] {
    def continue[B](k: F[B]): B = 
       k.combine(xs.continue(k), ys.continue(k))
  }

def empty[A, F[x] <: PointedE[A, x]]: Capture[F] =
  new Capture[F] {
    def continue[B](k: F[B]): B = k.empty
  }

The intriguing property of this representation is the ability to embed free constructions via subtyping

FreeSemigroup[A] <: FreeMonoid[A]
FreePointed[A] <: FreeMonoid[A]

Particularly we achieved

1. NonEmptyList that is a subtype of List
2. Option that is a subtype of List
3. single that can create each of Option, List, and NonEmptyList without any type class magic
4. empty that can create both Lists and Options
5. combine that able to
   - concatenate two NonEmptyLists resulting in NonEmptyList
   - concatenate couple of Options, Option and NonEmptyList or a couple of Lists resulting in simple List

So we now have a lot of data relations without special type classes, representing them.

Definitions

Before we continue, we need to make a few additional definitions

First is a selective functor

This is just an extension of Applicativeallowing for conditional effect composition.

We define such as

trait Selective[F[_]] extends Applicative[F] {
  def select[A, B](fab: F[Either[A, B]], fa: => F[B]): F[B]
}

The second one is just a redefinition of FunctionK having variance marks on type parameters

trait FunK[-F[_], +G[_]] {
  def apply[A](fa: F[A]): G[A]
}

That gives us more subtyping when we apply functor embedding

Higher Kinded Types

Now it’s time to remind the Functor power hierarchy

Functor       Pure
   |           |
   V           |
Applicative <--+
   |
   V
Selective
   | 
   V
Monad

Each of these definitions could have a free form like Free Monad or Free Applicative

Unluckily we are forced to define each free ADT separately, copying common constructors, and translating between using folds

We can start from this upgrade of Capture

trait Capture1[-K[_[_]], A] {
  def continue[F[_]](k: K[F]): F[A]
}

This is pretty much like the previous one, but continuation algebra is now higher kinded. We might represent functor capabilities using it.

We define our Embedding Algebras:

trait PureE[-F[_], G[_]]        extends FunK[F, G] with Pure[G]

trait FunctorE[-F[_], G[_]]     extends FunK[F, G] with Functor[G]

trait ApplicativeE[-F[_], G[_]] extends FunctorE[F, G] 
                                with PureE[F, G] 
                                with Applicative[G]

trait SelectiveE[-F[_], G[_]]   extends ApplicativeE[F, G] 
                                with Selective[G]

trait MonadE[-F[_], G[_]]       extends Monad[G] 
                                with SelectiveE[F, G] {
  def select[A, B](fab: G[Either[A, B]], fa: => G[B]): G[B] =
    flatMap(fab) {
      case Left(a)  => fa
      case Right(b) => pure(b)
    }
}

And the collection of free functorial Structures

type FreeF[+F[_], A]           = Capture1[FunK[F, ?[_]], A]

type FreeFunctor[+F[_], A]     = Capture1[FunctorE[F, ?[_]], A]

type FreePure[+F[_], A]        = Capture1[PureE[F, ?[_]], A]

type FreeApplicative[+F[_], A] = 
     Capture1[ApplicativeE[F, ?[_]], A]

type FreeSelective[+F[_], A]   = Capture1[SelectiveE[F, ?[_]], A]

type FreeMonad[+F[_], A]       = Capture1[MonadE[F, ?[_]], A]

Now we’ll start defining our instances. First one is Pure

trait PureInstance[F[_], K[g[_]] <: PureE[F, g]] 
   extends Pure[Capture1[K, ?]] {
  override def pure[A](x: A) = new Capture1[K, A] {
    def continue[G[_]](k: K[G]): G[A] = k.pure(x)
  }
}

implicit def pure[F[_]]: Pure[FreePure[F, ?]] = 
    new PureInstance[F, PureE[F, ?[_]]]       {}

Next one is Functor

trait FunctorInstance[F[_], K[g[_]] <: FunctorE[F, g]] 
   extends Functor[Capture1[K, ?]] {
  override def map[A, B](fa: Capture1[K, A])(f: A => B) =
    new Capture1[K, B] {
      def continue[G[_]](k: K[G]): G[B] = k.map(fa.continue(k))(f)
    }
}

implicit def functor[F[_]]: Functor[FreeFunctor[F, ?]] = 
   new FunctorInstance[F, FunctorE[F, ?[_]]] {}

Why do we have some strange type parameter like

K[g[_]] <: PureE[F, g]

or K[g[_]] <: FunctorE[F, g] ?

It allows us to reuse our instance implementation to implement more powerful instances, let’s continue with Applicative

trait ApplicativeInstance[F[_], K[g[_]] <: ApplicativeE[F, g]]
    extends Applicative[Capture1[K, ?]] 
    with FunctorInstance[F, K] 
    with PureInstance[F, K] {

  override def ap[A, B]
    (ff: Capture1[K, A => B])
     (fa: Capture1[K, A]) =
    new Capture1[K, B] {
      def continue[G[_]](k: K[G]): G[B] = 
        k.ap(ff.continue(k))(fa.continue(k))
    }
}

implicit def applicative[F[_]]: Applicative[FreeApplicative[F, ?]] = new ApplicativeInstance[F, ApplicativeE[F, ?[_]]] {}

Then Selective

trait SelectiveInstance[F[_], K[g[_]] <: SelectiveE[F, g]]
    extends Selective[Capture1[K, ?]] 
    with ApplicativeInstance[F, K] {
  def select[A, B]
  (fab: Capture1[K, Either[A, B]], 
   fa: => Capture1[K, B]) =
    new Capture1[K, B] {
      def continue[G[_]](k: K[G]): G[B] =   
        k.select(fab.continue(k), fa.continue(k))
    }
}
implicit def selective[F[_]]: Selective[FreeSelective[F, ?]] = 
   new SelectiveInstance[F, SelectiveE[F, ?[_]]] {}

And finally her highness Monad

trait MonadInstance[F[_], K[g[_]] <: MonadE[F, g]]
    extends StackSafeMonad[Capture1[K, ?]] 
    with SelectiveInstance[F, K] {
  def flatMap[A, B]
    (fa: Capture1[K, A])
    (f: A => Capture1[K, B]) =
    new Capture1[K, B] {
      def continue[G[_]](k: K[G]): G[B] = 
        k.flatMap(fa.continue(k))(a => f(a).continue(k))
    }
}
implicit def monad[F[_]]: Monad[FreeMonad[F, ?]]             = 
   new MonadInstance[F, MonadE[F, ?[_]]]         {}

The most useful constructor: embedding of any HKT application within any free structure

def embed[F[_], A](fa: F[A]): FreeF[F, A] =
  new FreeF[F, A] {
    def continue[G[_]](k: FunK[F, G]): G[A] = k(fa)
  }

We define simple isomorphism with cats.free.Free to show we didn’t lose any power

def fromFreeMonad[F[_], A](fa: cats.free.Free[F, A]): 
   FreeMonad[F, A] =
  fa.foldMap[FreeMonad[F, ?]](functionK[F](fa => embed(fa)))

def toFreeMonad[F[_], X](fa: FreeMonad[F, X]): Free[F, X] =
  fa.continue(
   new MonadE[F, Free[F, ?]] with StackSafeMonad[Free[F, ?]] {
    def pure[A](a: A): Free[F, A] = 
       Free.pure(a)
    def apply[A](fa: F[A]): Free[F, A] = 
       Free.liftF(fa)
    def flatMap[A, B](fa: Free[F, A])
                     (f: A => Free[F, B]): Free[F, B]   =  
       fa.flatMap(f)
  })

One can easily verify that

FreeApplicative[F] <: FreeMonad[F]

and also for each F[_] <: G[_]

FreeMonad[F] <: FreeMonad[G]

That property can be extremely useful since we might use

FreeMonad[Console | UserStore | Authorization, ?]

instead of nasty InjectKs like

[F[_]
  : Console :<: ?[_] 
  : UserStore :<: ?[_] 
  : Authorization :<: ?[_] ]  Free[F]

And have Free monads with nice type inference and seamless embedding

Also, we can express more powerful types like FreeIO monad with precise effect control and effect system, powered by subtyping, pretty much like ZIO but allowing to embed any functor and control async/concurrency capabilities, but this is a theme for the following posts.

Conclusion

Final algebraic form along with contravariance gives a chance to build powerful cost-free relation system between recursive types, simple or higher-kinded.

We can redefine some well-known structures as free definitions, gaining two-dimensional subtyping control:

• Covariance on base set (alphabet)
• Contravariance on algebra structure

Latter means that more restrictive (based on weaker algebras) data structures are subtypes for less restrictive. NonEmptyLists and Options are subtypes of Lists, and FreeApplicatives and FreeSelectives are subtypes of FreeMonads

Code

All the code samples presented in this package

manatki/manatki

Thanks

Special thanks to https://twitter.com/katzenstrophe for the help in preparing this post.

So you’ve found yourself again in this situation.
You have 2+ error ADTs like this

sealed trait PasswordError

object PasswordError{
  case class TooShort(required: Int) extends PasswordError
  case class ToesNotContain(chars: String) extends PasswordError
}

And this

sealed trait LoginError

object LoginError{
  case class TooLong(maxLength: Int) extends LoginError
  case object BadFormat extends LoginError
}

Next, you use some monadic type, using checked errors like
Either or ZIO, and have some of the code like having different checked errors

def validateLogin(login: String): ZIO[HasLoginConfig, LoginError, Unit]

def validatePassword(pass: String): ZIO[HasPasswordConfig, PasswordError, Unit]

And you’d like to use both of them in the single expression, so that result type can express the possibility of either error

def validateUser(user: User) = 
  validateLogin(user.login) *> validatePassword(user.pass)

Good news: your error type parameter has “covariant” tag so you can expect something like

ZIO[
  HasLoginConfig & HasPasswordConfig, 
  LoginError | PasswordError
, Unit]

Bad news: scala 2 still has not any type union operation, yet it has the with operator: not-always-commutative type intersection

If you aren’t familiar with tagless final approach yet it’s about time. There is plenty of videos like that one, just google it

So start from redefining your error ADT’s as single parameter traits like

trait LoginErr[+A] {
  def tooLong(maxLength: Int): A
  def badFormat: A
}

trait PasswordErr[+A] {
  def tooShort(required: Int): A
  def doesNotContain(chars: String): A
}

Starting from here, LoginErr[A] is equivalent to LoginError => A it’s just little bit more effective.

If you had pattern matching like

{
  case TooLong(x) => a
  case BadFormat => b
}

you may just replace it with

new LoginErr[X] {
  def tooLong(x: Int) = a
  def badFormat = b
}

And we have exhaustiveness check for free

But what should we match? We might need some “initial” form of our algebra, let’s introduce the universal initializer

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

Here F is the placeholder for your algebra, e.g. LoginErr or PasswordErr

To apply the “pattern matching” you need just pass your LoginErr[X] to the continue method and get back your X result

Why have we marked our -F[_] as contravariant? This is the main part

So our capture is just a natural (hopefully) transformation F ~> Id with covariance on the argument functor

Recalling that we are going to use some “algebras” as F it’s just a
[A] (ADT => A) => A where [A] f[A] is just a fancy syntax for higher-ranked type, forall a. f a if you prefer

According to Yoneda lemma[A] (ADT => A) => A is moral equivalent to ADT, you can verify just applying Yoneda to Scala wannabe-category and Id endofunctor, that means that Capture[LoginErr] is same as LoginError from our first attempt

Next, we might play a little bit with variances, if C[+A] is covariant you’ll have

C[A] & C[B] = C[A & B]
C[A] | C[B] = C[A | B]

Сonversely if C[-A] is contravariant you’ll have

C[A] & C[B] = C[A | B]
C[A] | C[B] = C[A & B]

Scala might not have | and & operations on type level, but those rules are effective when scalac is searching for least upper and greatest lower bounds during the type inference.

Recalling that functions -A => +B are covariant on the result and contravariant on the parameter we may conclude that

PasswordErr[A] & LoginErr[A] ~
(PasswordError => A) & (LoginError => A) =
(PasswordError | LoginError) => A

So PasswordErr[A] with LoginErr[A] is a special type that is effectively algebra corresponding to some union ADT PasswordError | LoginError

And that’s great because when compiler search for the least upper bound of

Capture[PasswordErr] and Capture[LoginError]

it should find

Capture[[A] PasswordErr[A] with LoginErr[A]]

due to Capture contravariance which is moral equivalent to union PasswordError | LoginError. And to “pattern match” it you need to implement merged PasswordErr with LoginErr , that will require you to implement all four methods, that is pattern match all four possible constructors

Now it’s time for some boilerplate.

For the real use, we’ll need easy Capture construction, without hesitation, we use Alex Konovalov’s trick for higher-ranked lambdas

object Capture {
  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]
    }
  }
}

Now we can implement the initial algebra, that is — implementation of our algebra trait for the initial Capture type

object LoginErr extends LoginErr[Capture[LoginErr]] {
  def tooLong(maxLength: Int) =  
      Capture[LoginErr](_.tooLong(maxLength))
  val badFormat               = 
      Capture[LoginErr](_.badFormat)
}

this methods could be used as constructor, we can simplify types defining

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

The full code can be found in this repo https://github.com/Odomontois/zio-tagless-err

Special thanks to https://t.me/scala_ponv community for the forcing to write my debut blog post

Any remarks, corrections, including English grammar are appreciated