[DRAFT] Free vs Final tagless

text.txt

So, Free vs Final Tagless.
The first consideration is that the reason why Free is so popular in
Scala, is that Final Tagless didn't quite work (due to ambiguous
implicits), in the current, subtype based encoding of typeclasses used
by cats and scalaz, whereas Free did. However, both libraries are now
addressing the problem, and will accommodate final tagless (also known
as finally tagless, tagless final, mtl style) better.  Another
important point is that they are roughly equivalent in power, but some
things might be easier or harder with one of them than with the other.
The thing with Free is: you are reifying a monadic computation into a
concrete data structure. However, if all you do with that data
structure is translating it to another monad (e.g. IO), then you can
avoid this roundtrip by using final tagless, which simply abstracts
over whatever monad you are going to use in the end. If however you
also want to modify this data structure, then Free is easier.  Another
point is mixing in different algebras, by which I mean writing a for
comprehension that uses both your HttpAlg and PersistentAlg: this is
easier with final tagless. With Free, you basically need to work with
Coproducts and injections (I could explain what this means, but the
talk Compositional architecture with reasonably priced monads does a
better job), whereas with FT you just add another implicit parameter.
Yet another point is when you need your algebra to be more powerful
than Monad, and you want this power to be available in your algebras,
not just in the interpreter. This is the case you were in yesterday,
where basically you want your algebra to not only be as powerful as
Monad (which is what Free gives you), but also as powerful as
MonadError (to use handleWith and so on). With Free you are stuck with
having all ops return Either (pain in for comprehensions), or adding
other constructors like Attempt , which is basically reinventing the
algebra behind MonadError. With FT, you just say that your F needs to
be F[_]: MonadError, and you're good to go.  Otoh, if you need to do a
lot of manipulation of interpreters (e.g. composing two interpreters
together), it's easier with Free (still possible with FT though), but
that's a somewhat more advanced topic that you might, or might not
need.  FT is less boilerplate, but Free does not need all your methods
to have type parameters (if you only have one algebra). Free has way
more learning resources in Scala. Many people reinvent FT without
knowing what it is (and therefore without being able to exploit it
fully). With Free, it's a bit easier (imo) to understand the mechanics
of interpretation, since transforming a data structure is easier to
grasp than type application to select typeclass instances. With FT
it's a bit easier (imo) to understand the mechanics of abstraction,
since adding a type parameter to a trait is easier to understand than
how Free works, and why it's a Monad.  These are my random thoughts,
I'm sure other people can add or correct, especially @edmundnoble
(which is writing cats-mtl), and @tpolecat (whose doobie library uses
Free at its core, with a FT higher-level interface. This strategy is
also similar to what fs2 does)