Halfway as a learning exercise and halfway toward starting to build something like fp-ts, I am implementing a functional programming standard library in typescript.
In particular, I am focusing on making a free monad transformer, as a warmup towards building an extensible effect system.
To do this, I am drawing heavily from decisions made in purescript contrib libraries, and what’s relevant for this question, trampolines.
To trampoline a plain javascript function, the approach often taken is reflected in the interface for the Trampoline monad in purescript’s purescript-free under Control.Monad.Trampoline. A suspended computation is represented in a Trampoline a containing either a Unit -> Step a thunk returning the next step, or a finished result. A function returning Step a can then be trampolined to avoid stack overflow in recursive functions.
This is the approach I’ve taken at first, as it is simple, and allows me to trampoline tail recursive non-monadic functions, of which I need to implement many to construct a Free monad.
Regardless, I am a bit confused on why there is a second, different approach taken, under Control.Monad.Rec.Class, for the MonadRec m typeclass, where the deferred computation is represented as a Step a b containing either an a-ccumulator value, or a b-finished computation, such that a function a -> m (Step a b) can be trampolined through a monad’s implementation of the class.
Are both approaches applicable in both situations? Can one approach be implemented in terms of the other? Is one of these approaches more general than the other? I am looking for some insight in general as to why these two approaches are separately implemented, so that I can correctly proceed.
Trampoline isn’t a Transformer. It’s useful as a concrete base Monad and can make some arbitrary transformer stack stack safe. With MonadRec and tailRecM, you can write tail recursive algorithms that are abstract over the base Monad.
For example, Effect is not stack safe over binds in general, but it implements MonadRec. Same for Identity. That means I could write a generic Monadic algorithm and instantiate it with different base Monads.
doStackSafeFoo
:: forall m. MonadRec m => MonadState Int m => List Int => m Unit
This could be instantiated with something like StateT Int Effect or StateT Int Identity. The main issue here is that it affects the way you write your program. It must be formulated in terms of tail recursion.
An example of a use case for trampoline might be a parser library that is implemented as a transformer. You might write your “pure” parser in terms of some concrete Parser String Identity, but this is likely not stack safe if implemented naively. However, you can swap out Identity for Trampoline as the base Monad, and Trampoline essentially dynamically rewrites your parser program at runtime into something that can be executed in a tail recursive manner by the Trampoline interpreter.
In general, I personally try to avoid MonadRec where I can and prefer to use stack safe base Monads as it makes for nicer and more efficient programs. As an example, Aff is always stack safe, and so MonadRec is unnecessary. If you write an algorithm in terms of MonadRec, and then use it with a stack safe Monad like Aff, you are just incurring unnecessary overhead, doubling the number of binds that have to be executed!
The ParserT type in parsing uses an internal trampoline approach in a similar way, so all parsers are stack safe, and pure parsers have no transformer overhead.
I’m sorry, I feel you may have misunderstood me. My question isn’t about the Trampoline monad itself, but about the ways trampolining, as a technique, is done in the libraries. Of which I have seen two. i wondered why two different approaches were taken, instead of one for both cases.
Trampoline is a concrete base Monad, and is always pure. You can’t combine Trampoline with effectful base Monads. It’s only real use case to make pure, non-tail recursive programs stack safe without much thought, such as subbing in as the base Monad in a concrete transformer stack instead of Identity (for example, parsers).
MonadRec is an abstraction that can be implemented by many base Monads, such as Effect or Identity.
Using MonadRec, you can write tail recursive algorithms polymorphic over some Monad.
It can also be used concretely when you know your concrete base Monad is stack unsafe under binds (such as Effect).
There’s a performance sink when combining MonadRec with Monads that are already stack-safe.
My personal preference is to use stack-safe base Monads instead of MonadRec as it makes writing programs easier and often more performant.
Writing a stack-safe base Monad usually entails embedding some sort of trampoline in it’s algebra.
See the implementation of Parser for an example of an effectful, trampolined algebra which cannot use Trampoline directly (as it’s a transformer and must go through MonadRec for lifted operations).
Note, a recursive algorithm can be mechanically transformed into a tail-recursive one with an explicit stack. Trampoline generalizes this by making the explicit stack a queue of closures.
