Optimizing a Free Monad

3
votes

If I have a value a: Free[Op, A], is it possible to "flatten" the structure of a so that two Ops that are bound together by the free monad may be collapsed into one?

Context: I'd like to perform this as an optimization step before interpretation because a semantic of Op is that its operations are idempotent. So if two appear "in a row", the second can be eliminated at no cost to the semantics of the program.

1
scalafunctional-programmingfree-monadscala-catsrecursion-schemes
Maybe this can only be done at the interpreter level? It seems like a useful generalization to have. - beefyhalo
It's an Scalaz/cats implementation constraint stemming from Scala's eager evaluation strategy rather than fundamental Free limitation. Reason is Gosub/FlatMapped constructor used by Free's flatMap to prevent stack overflow: it makes further introspection progress impossible by wrapping a computation into trampoline function. - P. Frolov

1 Answers

4
votes

As far as I understand there is no way for this kind introspection of Free Monad program as it represents sequential computation where each step depends on the result of another.

There is a great talk by John de Goes about the pros and cons of Free Monad vs Free Applicative (https://www.youtube.com/watch?v=H28QqxO7Ihc). The latter gives power of introspection.