Phil Freeman's paper titled Stack Safety for Free introduces the MonadRec type class with the following definition.
class (Monad m) <= MonadRec m where
tailRecM :: forall a b. (a -> m (Either a b)) -> a -> m b
Any instance of the MonadRec class must adhere to certain laws.
tailRecM f ashould be equal tof a >>= gowherego (Left a) = f a >>= goandgo (Right b) = pure b.- The stack utilization of
tailRecM fmust not exceed a constant multiple of the stack usage byfitself.
Now, let's consider the Pair class in TypeScript.
class Pair<out A> {
public constructor(
public readonly fst: A,
public readonly snd: A,
) {}
public chain<A, B>(this: Pair<A>, arrow: (value: A) => Pair<B>): Pair<B> {
return new Pair(arrow(this.fst).fst, arrow(this.snd).snd);
}
public static of<A>(value: A): Pair<A> {
return new Pair(value, value);
}
}
The implementation of chainRec for Pair, which is equivalent to Phil Freeman's tailRecM, involves defining an Either type first in TypeScript.
class Left<out A> {
public readonly isLeft = true;
public constructor(public readonly value: A) {}
}
class Right<out B> {
public readonly isLeft = false;
public constructor(public readonly value: B) {}
}
type Either<A, B> = Left<A> | Right<B>;
Then, the chainRec function is implemented within the Pair class as shown below.
public static chainRec<A, B>(
arrow: (value: A) => Pair<Either<A, B>>,
value: A,
): Pair<B> {
// Implementation omitted for brevity
}
You can test this implementation using the provided Fantasy Land Playground Link.
In terms of adhering to the laws, while it's evident that the first law is satisfied, concerns arise regarding the second one.
- The stack utilization of
Pair.chainRec(f, a)must not surpass a fixed multiple of the stack usage byf.
Regarding the second law, there may be uncertainties due to the potentially unbounded growth of the local stack variable within the rec function. This prompts questions on whether allowing chainRec to use such a large local stack could enable creating valid instances of MonadRec for any monad. If not, examples of monads that are valid Monad instances but not MonadRec instances would provide clarity on non-tail recursive monads.