Hierarchical Free Monads: Myopic alternative to Tagless Final

In this post I'm going to discuss "Hierarchical Free Monads: The Most developed approach in haskell". I spotted this article when I was searching details about Tagless Final style.

I was intrigued by some of the claims because I'm interested about where to go after getting to understand Final Tagless. But that post fails to deliver gloriously.

It's entertaining on its own, but it requires some background to be appreciated that way. I'll try to provide the needed background here.

Before we get to the main course, lets look at the framing of the post.

Industrial adoption of functional programming

Haskell's been around for a while now, I think it's been there around three decades?

The long history of programming languages shows that a language can't really survive without the industrial adoption. All the languages which were only academic toys became completely abandoned after a decade or maybe two. The languages which are refusing to interact with the mainstream are doomed to die slowly and inevitably. There is no reason for Haskell to be different here. Tasks from academia will be finished sooner or later. If we want the language to be successful and alive, adoption by the industry is the only possible way long term.

If you plan to casually grope the damsel, you got to first coinvince that she's in distress. Unfortunately this tactic may be ineffective if you mistake damsel for a queen. Haskell's already quite successful and it's going to be around for a long while.

But the industry is not interested in advanced Math concepts, it's not interested in cool smart things, it doesn't value curiosity as haskellers do. The only thing the industry considers important is can it have its goals achieved or not and by what cost. Unfortunately, achieving the industry's goals is where the Haskell community has a big problem. We all need to learn from the mainstream, we need to adopt methodologies, ideas and practices to show the industry that Haskell is not a toy but rather a tool able to solve real tasks and lead businesses to success. We all should be more open-minded and should not stay in our Ivory Tower.

IMHO. An industry that does not have curiosity to mathematics or theory of its own profession and doesn't find it interesting is too arrogant and narrow-minded for its own good. Therefore there would be nothing to learn from such a mainstream culture.

There are already plenty of "industry-accepted" and "pragmatic" programming languages. Why wouldn't you enjoy the environment and company of your own kind? The sort that hamster-wheeled arrogance creates. They might appreciate something like "hierarchical free monads" to compete with pure typed functional programming.

If "advanced math concepts" are so uninteresting for the industry, wouldn't there be better programming languages present for them? Everything has been already catered for short-term profits and quarterly profit cycle.

...

Ah. The post author found Haskell useful. But there's "great drama" when the community around it doesn't cater to him. He's not ready to learn about types, study category theory or find out what a lemma or a theorem is. That "new world of superior concepts" should fly to his hand like it was nothing.

Philosophy of functional programming

When I decided to write about this, I hadn't read completely through of this "philosophy" -section of the article.

You might have heard that the biggest thing haskellers value is Math: Category Theory, Abstract Algebra, Lambda Calculus, advanced type systems. You might have even heard the opinion that mainstream developers just aren't proficient in Math and this is why they have "Software Engineering" which is no more than just a rough substitution of it. So the discipline called "Software Engineering" is not applicable, is dirty and unwanted, they say. Why should we put our effort into methodologies and other mind flaws the outside industry has?

Maybe the modern "software industry" is a trainwreck in progress? I learned that from studying OOP.

And I'm not exaggerating. Haskellers consider their language as something special, unique, blessed and therefore standing out of those strange agreements the outer world managed to build. This is clearly not true. Although Haskell is kinda a unique language (what language is not?), it's no way different in the design space.

There's no single group of "Haskellers" to generalize, and I doubt smartest of them think that Haskell's particularly special in its class.

Software Design is about how to create a working software with low risks. How to make it reliable, maintainable, satisfying requirements. And certainly, how to achieve industry's main goals: a ready product that solves real problems and can produce money.

Btw. It could be slowly, finally, time to change the notion that a company's primary goal is to produce money. It's actually quite stupid and nonsensical to always take an action that produces the most gratification right now.

The current societal hierarchy and the culture of greed and lack in self-reflection is enthusiastically destroying its environment and cultural heritage, destroying all knowledge in copyright disputes, distorting historical texts to appear as good guys, killing everybody on the planet in wars while coercing their own religion to everybody, unwilling to share things that are wasted anyway, while reproducing like rabbits and eating themselves to early demise with cheaply produced produce.

Please, could I have some science, compassion, mathematics and future instead of this spinelessness?

Software Engineering helps the industry to not invent things again and again, to not start from scratch, to not spend more time for curiosity than it's actually needed. There should be several well established ways to do all the usual things: web apps, backends, frontends, command line apps, machine learning apps. This makes the development much cheaper and allows for less proficient developers who can be unfamiliar with all the high-level concepts but still will be able to solve business problems.

These "business problems" have been already solved several times over in "practical ways", in "pragmatic languages".

In this regard, Haskell was lacking high-level approaches and ideas composed into a complete methodology of Software Design. At least until recent years. Yes, sure, we have the mtl approach for a decade or so. We also call it Final Tagless, and it's the most popular approach to write code... But from the design point of view, it doesn't really satisfy the requirements the industry has. For example, its testability is very low, and its complexity is very high, especially if we're trying to incorporate some advanced library with massive type level tricks involved. The problem with mtl/FT is not in its idea but in how it's done. It doesn't allow you to separate layers completely, it forces you to use advanced type level features (like type classes, type equality, type families), and doesn't provide any good way to express the semantics other than just "immediate evaluation". It has many other flaws, and it's a leaky abstraction. I wouldn't recommend using FT for big codebases.

Lets make some notes.

Flaws of Tagless Final style:

  1. It's hard to test.
  2. It's really complicated.
  3. Massive type level tricks needed.
  4. Doesn't allow you to separate layers completely,
  5. Forces you to use type classes, type equality, type families.
  6. Doesn't allow express semantics other than "immediate evaluation".
  7. Has many other flaws and leaks as an abstraction.

Ok. I'll maybe address some of these points. But isn't it a bit hard to address this because the terminology isn't precise? Maybe we'd need bit more precision in the expression, some "mathematics" perhaps.

Free monads

Apparently free monads suffer from a bad reputation. I don't know why. From what I have asked from Haskell community and read responses elsewhere they are confused about the whole post. I should perhaps go check whether the windmills are okay.

When I asked about this, the best answer I got was this:

This reputation is a bit deserved, since any time you defer the decision about how various operations are implemented, you're putting an obstacle in the way of the compiler optimisations. -- Cale

Wait, what is a free monad? Well the description is short if you understand it.

"Free" in mathematical context is a construct that has been obtained by just stating the structure is there.

To build a free monad you take a functor, and declare that it's got unit and join, and that it behaves with monad laws, without saying what those are.

There's nothing wrong with Free monads as-it. On the contrary they're forming a quite interesting Haskell construct.

Free monads have constructors like these:

Pure :: a              -> Free f a
Free :: (f (Free f a)) -> Free f a

You can plug in any functor into the f and you get a monad for free. It's really interesting, consider what happens if f is a list. You can build structures like this:

Free [Pure 1, Pure 2, Free [Pure 3, Pure 4]]

It's quite obvious why these can be monads, recall monad has join -operation.

join :: Monad m => m (m a) -> m a

And you can define bind in terms of the join.

(>>=) :: Monad m => m a -> (a -> m b) -> m b
(m >>= f) = (join . fmap f) m

It's giving an appreciable perspective to monads.

Hierarchical free monads

Hierarchical free monads take free monads and nest them. Looking at the details, the author creates a functor AppF.

data AppF next where
  EvalLogger :: Logger () -> (() -> next) -> AppF next

instance Functor AppF where
  fmap f (EvalLogger logAct next) = EvalLogger logAct (f . next)

type App a = Free AppF a

The Logger is a similarly described free monad. Then it gets interpreted.

interpretAppF :: AppF a -> IO a
interpretAppF (EvalLogger loggerAct next) = do
  runLogger loggerAct
  pure $ next ()

Oh this looks like stupid. We are using free monads, but it's immediately interpreted after being constructed.

The free monad construct itself is demoted into fancy syntax of no interest. To demonstrate, lets examine the constructor for AppF (Free AppF a).

EvalLogger :: Logger () -> (() -> Free AppF a) -> AppF (Free AppF a)

We could achieve the same result with just this.

data App a where
  PureApp    :: a -> App a
  EvalLogger :: Logger () -> App a -> App a

Give it Functor, Applicative and Monad and it's the same structure.

The cue of ignorance about isomorphisms

I don't get the () -> next there because it's isomorphic to next.

The unit type is meant for capping type parameters. Eg. In the IO a, you plug the unit into a to produce an IO action that doesn't return anything.

Though, () -> next and next are isomorphic.

f :: next -> (() -> next)
f = const
g :: (() -> next) -> next
g = ($())

f.g = const . ($()) = id -- (through eta expansion on () -> next)
g.f = ($()) . const = id

You don't need to use the first one anywhere because you can get it by const x.

Efficiency

I'm not too worried about the efficiency, but lets look at the efficiency graph shall we?

The author comes up with a table where the thing chokes up after million operations stacked up while every other method maintains a linear slowdown.

Here, the Church Encoded Free Monad engine is a bit slower than Final Tagless, but don't mind the difference, - it starts to be significant from 1 million of operations. Are you sure your scenarios will be that long?

Everybody else gets linear time slowdown and your method goes up in a square and clips off at an arbitrary boundary of operations when it finally fails. This suggests there's some computational complexity in the solution, but why should there be any?

If each step takes short time enough, it's not too bad to be above-linear time in complexity even if you could avoid it. However, have you identified what is the factor that determines the time it takes in each step?

"Unified Design"

There's a problem in how the author is handling types.

He presents this scenario in hierarchical free monads:

printRandomFactorial :: App ()
printRandomFactorial = do
    n <- getRandomInt (1, 100)
    logInfo $ show $ fact n

And compares it to this Final-Tagless -style.

printRandomFactorial :: (Random m, Logger m) => m ()
printRandomFactorial = do
    n <- getRandomInt (1, 100)
    logInfo $ show $ fact n

Lets look at this again, but just types okay?

printRandomFactorial :: App ()
printRandomFactorial :: (Random m, Logger m) => m ()

While the bodies of the two functions are pretty much the same there is a significant difference in the function definitions.

Yeah, it looks like the FT gives you more information about the behavior of printRandomFactorial. Given the Haskell in safe mode, it'd also verify the procuder isn't accessing any services it isn't supposed to access.

This isn't far away from dependent typing, where types give guarantees about the correctness of software. They end up doing this by encoding properties of the results, in a similar manner to above.

So technically the longer type signature is better because it's giving more details about the behavior of the function.

However, the main theme of this week's blogpost raises its rear.

FT requires you to specify a list of constraints. The more effects you have the more constraints will be there. Normally, business logic of a regular web service consists of dozens if not hundreds functions, and typing this kind of boilerplate makes coding extremely annoying.

I'm not sure whether there's a solution to having to specify constraints, but I'd bet there is. Something that lets you do something like this:

{-# LANGUAGE ConstraintKinds #-}

type FactorialService a = (Random m, Logger m)

printRandomFactorial :: FactorialService m => m ()

I'm not entirely sure though. I'd put types first, they're propositions of what you're trying to prove, or alternatively specifications of software you're writing.

It doesn't buy anything useful. Absolute correctness is not required, and moreover, cannot be achieved. Documenting the effects doesn't make the code clearer.

If you want an utter bullshit of a type signature such as the App () is you already get it in "popular" languages.

Type information is all about correctness. It's supposed to contain guarantees about behavior of the expression. More you can tell in the type less I need to read to verify the code behind it is correct.

If you're doing it right, you write the type first to specify the software. The type is supposed to contain details of the behavior, otherwise what's the point of it being there?

Fine structuring of the project has more impact on the code clearness. Good project organization will allow you to know what effects are used there by just looking into the namespace (like, app/Product/Storage/Queries or app/Server/API). List of effects/constraints is not a tool for layering, effects can contradict to the namespaces, and in general it is a redundant boilerplate for no real purpose, "just in case".

This qualifies as "straight from an OOP book" gibberish.

Types are the structure you have, everything else that ends up being defered to the runtime ends up being guesswork. It's even the reason why it's performing "worse", there are less guarantees over the program's behavior!

I'm not satisfied to type information Haskell lets me to provide when it comes to interactive software. But there's no fix because doing better would require linear types.

IO () tells jack shit about anything. In case you want that kind of types that tell nothing about your software, you can use Data.IORef to obtain them.

You can write Haskell like it'd be 1980's BASIC. It's totally doable but.. why wouldn't you code in "popular languages" instead? It already lets you make every type into meaningless noise. You can use them and get the exact same results! Even the performance can be questionable if you play with classes a little bit and just get inspired from Haskell instead of actually using it.

"Implementation detail pepper" lets give you some salt instead

This mistaking of types with boilerplate continues on.

Violation of these principles seems to be embedded into FT. For example, in FT effects are usually peppered by implementation details too much. These details are coming from the native libraries and leak into the business logic. No good abstraction, no separation of concerns. Guts are exhibited and accessible for all curious people.

Lets look at one of these type signatures.

printRandomFactorial :: (Random m, WithLog SomeLogEnvironment String m) => m ()

You earlier had Logger m. It was already abstracting it out. Why this program would need details about the logging environment hmm?

Something's leaking into the business logic and it's visible in these types. It's a polar opposite of what he is claiming. His stuff is broken and he's misinterpreting it as a flaw of the abstraction!?

The stillborn App () "abstraction" just let the potentionally questionable accesses to implementation details and not reveal it. Then something would eventually break down the line because nobody knows anything about anything.

You can get this "feature" in your "popular language" I'm just saying.

"No value in composition"

One of the really nice things about Haskell is that things compose. Basically this function:

(.) :: (b -> c) -> (a -> b) -> (a -> c)

I just love using it. It composes two functions from their ends. Also if the two functions are correct and correctly chosen, then their composition is correct too. I just wish they'd have overloaded the dot operator so that I could use it to describe anything that resembles a category.

Another point of FT proponents is about composability. However there is no value in composition itself. As well as there is no value in lambdas, high order functions, types, type classes and other features of the language. We're here not to admire the language. We're here to solve real problems and achieve business goals, and we should be very careful in choosing the tools.

Could somebody remind me why he is using Haskell? Is it to brag, in sake of vanity? You know, bit like pumping oils into your muscles to look bigger. The outcome is about the same.

There are reason why those all things are in the language. Haskell's got correspondence to mathematical logic and even if it's a turing complete language and therefore that logic is unsound, it gives you plenty correctness guarantees given that the program terminates.

The types and structures are chosen to match with intuitionistic logic. Functions correspond to implications, that's why they're labeled with arrows. Pairs correspond to conjunctions while sums correspond to disjunctions.

There are huge benefits in corresponding a language in this way to logic. One of those benefits is possibility to write code that's correct by construction. It sides with understanding how things work when dependent typing is in the language so it's not necessarily something you learn just by sticking to writing Haskell.

There is no value composing effects. There is value in controlling effects. Specifications in the FT are very like when you place a mark BUG: fix me! near a bug. Do you really control it? Nope. The bug is still there. Explicit lists of effects is just a needless dancing around a landing strip in order to summon the complete correctness.

You can also get incomposibility in your favorite popular programming language. Why get a language that composes if you don't value composibility?

Extensibility

There's a point when he gets to refute that Finally-Tagless isn't extensible. Ah..

-- Then:
-- printRandomFactorial :: (Random m, WithLog SomeLogEnvironment String m) => m ()

-- Now:
printRandomFactorial :: (Random m, Database m, WithLog SomeLogEnvironment String m) => m ()

(why random factorial printer should access the database?)

Ok so the argument is that the change starts traversing upward in the call stack. We end up having to change everything that calls it.

-- Then:
-- printFactAndFib :: (Random m, WithLog SomeLogEnvironment String m) => m ()

-- Now:
printFactAndFib :: (Random m, Database m, WithLog SomeLogEnvironment String m) => m ()

But seriously, what's going on here? Is the factorial cached because it needs the database? Should the documentation change now? If there are repercussions to rest of the software, shouldn't the type change?

Now lets compare this with the greatness that is App.

printRandomFactorial :: App ()
printRandomFibonacci :: App ()
printFactAndFib :: App ()

Okay...

You can get that in a popular programming language I'm just saying. It's equally simple there.

Expression problem

HFM isn't an alternative to Final Tagless because it doesn't even attempt to solve the expression problem.

Well, you're right. With FT the Expression Problem is kinda solved. But we're not paid for solving expression problems, we're paid for solving business problems. Sometimes extensibility is a requirement, and sometimes it's not. My experience shows that the number of core subsystems rarely exceeds 10. Maybe 15. Some of these subsystems can be implemented on the start, some of them are fine to add lately. You always know what you do and why you do this.

I leave the whole quote in here. Although the first part would be enough, but it kind of gets dumber as it falls down.

...And BTW, the outer world is not aware about the term "Expression Problem", at all. Although haskellers love it and love to solve the Expression Problem, it's not a primary goal for industrial development.

I realise we are talking about some specific use of Final Tagless, but everything else is just being ignored. Your primary goal is not education so you kind of drop it to the floor and think that's okay.

Lets take Philip Wadler's quote where he describes expression problem:

The expression problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts). -- Wadler

So to explain what this means. Lets take a list type in algebraic form.

[a] = 1 + a * [a]

You get the two constructors, nil and cons.

nil       = inl 0
cons a as = inr (a, as)

And lets make some destructors, join and concat ought to be fun.

concat : [a] -> [a] -> [a]
concat (inl 0) a = a
concat (inr (a, as) b = inr (a, concat as b)

join : [[a]] -> [a]
join (inl 0) = inl 0
join (inr (a, as)) = concat a (join as)

Adding case means that you do this:

[a] = 1 + a * [a] + a

Lets say the new constructor is hbar. Though now the problem here is that concat and join are broken. They don't handle the hbar.

You can add as many functions as you want, but can't add even one constructor. This is a problem that appears in programming languages in several ways.

The idea of Final Tagless is that constructors can be abstracted with typeclasses, just like anything else.

Therefore you can declare:

class ListC list where
    empty :: list a
    cons  :: a -> list a -> list a

newtype ConcList a = ConcList [a]

instance ListC ConcList where
    empty = ConcList []
    cons a (ConcList b) = ConcList (a:b)

abstract :: ListC list => [a] -> list a
abstract [] = empty
abstract (x:xs) = cons x (abstract xs)

catenate :: ListC list => ConcList a -> ConcList a -> list a
catenate (ConcList a) (ConcList b) = abstract (a++b)

main = pure ()

Next, lets say you don't, but you do anyway. You want points into the list where it's broken into pieces.

class HBar bar where
    hbar :: bar a -> bar a

newtype BarList a = BarList [[a]]

instance ListC BarList where
    empty = BarList [[]]
    cons a (BarList (bs:cs)) = BarList ((a:bs):cs)

instance HBar BarList where
    hbar (BarList cs) = BarList ([]:cs)

unbar :: BarList a -> [[a]]
unbar (BarList as) = as

The earlier "abstract" and "catenate" stays the same, although now you also have "unbar" that can operate on the new structures. This is quite versatile and that's why it is getting attention despite being quite complicated.

Final Tagless still goes further from here. You can define the catenate such that it can be extended over to accept the HBar constructor.

Anyway that's the idea. I think we're confusing extensibility and extensibility here. The post author is talking about something simple, eg. Patching of existing code. We're talking about options we have for plugging programs together once they've been written.

Exception handling

The exception handling part seems to work. You pass errors as data, don't touch the Control.Exception and you should be fine.

Oh.. Wait a moment.

interpretLangF :: LangF a -> IO a
interpretLangF (ThrowException exc next) = throwIO exc
interpretLangF (RunSafely act next) = do
  eResult <- try $ runLang coreRt act
  pure $ next $ case eResult of
    Left (err :: SomeException) -> Left $ show err
    Right r  -> Right r

Well I hope that he's at least using exceptions to handle contradictions only. That is, exceptions would catch and trigger on actual bugs, while known error conditions would result in normal operation with some good plan to organize those errors.

Right?

Resource management of missing the point

Finally the article gets to resource management. In Haskell you can't bind a lifetime of a resource to an object, besides that, it'd be outside of the reach for logical reasoning.

Unfortunately, Haskell doesn't have much on it for resource management. At least not until linear types are getting their shape. It is a flaw in this language.

Another popular idea for RAII is to have a scope that is the only place where a resource can be accessed. Once the control flow leaves this scope, the resource is destroyed.

You can't implement this functionality in Haskell. However when we talk about Haskell's flaw here, it doesn't mean that this particular problem would have been solved well elsewhere.

Oh.. And I wonder why he didn't figure this out.

ioBracket
  :: IO a        -- computation to run first ("acquire resource")
  -> (a -> IO b) -- computation to run last ("release resource")
  -> (a -> IO c) -- computation to run in-between
  -> LangL c

Drop the convenient type information in comments.

ioBracket'
  :: IO a
  -> (a -> IO b)
  -> (a -> IO c)
  -> LangL c

Fill in the computation to run last, given the resource a.

ioBracket''
  :: IO a
  -> (a -> IO c)
  -> LangL c

Fill in the resource acquisition, lets call the resource foo.

ioBracket'''
  :: (foo -> IO c)
  -> LangL c

Plug pure :: Applicative m => a -> m b into the expression.

ioBracket''''
  :: LangL foo

Somehow our resource escaped the context. That's among some reasons of why, ladies and gentlement, you are going to need linear types if you plan to do resource management.

Also this reasoning with types is a thing. I didn't need to look anywhere else to figure this out. It's obvious in the type that the program has this problem.

Conclusion

There's already a judgement out there that hierarchical free monads seem mostly pointless. Be careful to not confuse them with free monads though.

Anyway, I didn't cover this with intent to inform the author. I can read from the text that he's not ready to listen.

Update 2020-07-03: There is discussion on r/haskell about the content of this article.

Please note that I do examine and rewrite my texts few times before publishing. If you find something recent that pisses you off it's completely justified to be enraged because it passed me at least 2 times prior thrown online.

I agree with the feedback in that some of the text ends up undermining the content as plain insults, giving it a derisive feel. I'll reflect on it and mark: the next thrown cold towel needs warmer water and few stones less.

I could be wrong about the author not listening this. But I see he is really invested into his product and I've been there myself. Even plain criticism is going to be perceived as insult.