Without actually saying the words, this post makes a good introduction to the expression problem, trading the ease of adding types for the ease of adding behaviors.
TINSTAAFL, but what a functional programming paradigm takes away it replaces with brevity, concision, additional type safety, and greater opportunities for the compiler to restate your algorithms in a form more conducive to parallelization and concurrency.
There no reason that FP can’t do final encodings too. All you need is polymorphism, though modules/existentials make it less burdensome.
It’s just not the style FP usually emphasizes though. I wish Scala were less about OO-FP and more about Modules-FP to better emphasize this point.
Also interesting are modules in DT languages where you could actually prove a bisimulation and thus have perfect safety of module signature instantiation given a reference. Maybe as HoTT/OTT become more developed this technique will appear on the horizon.