Tagless final, questions

Hi everyone,

I’m trying to get a firmer grasp on the tagless-final style as it’s used in Scala.
Most of my reading so far comes from Nicolas Rinaudo’s article Nicolas Rinaudo - A "quick" introduction to Tagless Final, though there are many other great resources.

  1. Why do we need F[] at all?
    After a while I still can’t explain to myself why the higher-kinded type F[
    ] is indispensable.
    I’d love to keep a very short mental motto like “we need it because …”.

trait ExpSym[F[_]]:
def lit(i: Int): F[Int]
def add(lhs: F[Int], rhs: F[Int]): F[Int]
def eq (lhs: F[Int], rhs: F[Int]): F[Boolean]

Examples of the answers that occur to me:

  • F[_] lets different algebra operations return different value types (F[Int], F[Boolean], …).
  • F[_] makes it possible to have multiple interpreters, e.g. ExpSym[Pretty] vs ExpSym[Eval].

Is that the whole story, or is there something deeper? So, to me it seems that F is connected both with the ability to have multiple interpreters and with type-checking and perhaps with something else as well, as if it solves several problems at once.

  1. Must an algebra have exactly one higher-kinded parameter?
    Most tutorials show a single type parameter:

trait Algebra[F[_]]
But in articles like Typelevel | Tagless Final Algebras and Streaming I see examples with two:

trait Algebra[F[], G[]]
How critical is that single-parameter rule? When and why would you introduce a second one?

  1. Is it OK for the result type to contain effects already?
    trait Algebra[F[]]:
    def someOp(i: Int): F[Result] // simple
    def someOp(i: Int): F[List[Option[Either[String, Result]]]] // effectful structure
    Do we gain something by always hiding every effect behind the outermost F[
    ], or is it perfectly fine to let richer effect stacks appear inside?

  2. Parameters that come “out of thin air”
    With the classic expression algebra we write

trait ExpSym[F[_]]:
def lit(i: Int): F[Int]
def add(lhs: F[Int], rhs: F[Int]): F[Int]

I think “add” is typed this way so that

  • The compiler ties the operands to earlier lit/add results.
  • You can’t pass in arbitrary values that were never produced by the algebra.

But what about something more real-world, e.g. database access:

trait DBAlg[F[_]]:
def save (u: User): F[UserId]
def find (name: String): F[UserId]
def delete(userId: ???): F[Unit]
Should delete take userId: F[UserId] or a plain userId: UserId?
Pros of UserId – A controller can just call delete(id); simpler signature.
Pros of F[UserId] – Prevents deleting a user ID that appeared “out of thin air”, i.e. one not obtained via save or find.

What is the idiomatic choice here and why?

Thanks in advance for any insight!

I can recommend Noel Welsh’s talk on Tagless Final for Humans. In particular, I want to +1 his recommendation to drop the F[_] parameters. Use a member type constructor instead. It becomes much less cluttered.

3 Likes

Martin, thanks for the tip. I’d like to point out that the material discussed in the video can be read in print form here Functional Programming Strategies

2 Likes