Documentation

Original program in do-notation. Calls restore, bind, bind with argument v, then store, bind (ignoring result), then return.

Step 0: Desugar do-notation into explicit bind (>>=) operators. Shows the structure hidden by do-notation syntax.

Step 1: Replace method names (calculte, restore, store) with their actual implementations. Now we see the Free constructors (Calculate, Restore, Store) explicitly.

Step 2: Apply the Monad instance rule: Free m >>= f = Free (fmap (>>= f) m) The first bind gets transformed, revealing the fmap.

Step 3: Replace fmap with its realization from the Functor instance. fmap f (Calculate e next) = Calculate e (a -> f (next a))

Step 4: Move Pure a from the end to the front as the first argument of bind. Prepares for applying the Pure >>= f = f a rule.

Step 5: Apply Pure >>= f = f a rule from Monad instance. The a from Calculate goes to Pure, becomes r, so we remove Pure and just use r.

Step 6: Deal with the second bind. Apply Free m >>= f = Free (fmap (>>= f) m). We have Free (Restore Pure) and a function on the right.

Step 7: Replace fmap with the Restore realization. fmap f (Restore next) = Restore (a -> f (next a))

Step 8: Apply Pure a >>= f = f a again. The function already had name v, so we simplify by removing brackets.

Step 9: We have Free and bind again, apply the transformation rule. Free m >>= f = Free (fmap (>>= f) m)

Step 10: Replace fmap with Store realization. fmap f (Store i next) = Store i (a -> f (next a))

Step 11: Move Pure a to the front of bind again. Take the argument from the end and put it in front.

Step 12: Apply Pure a >>= f = f a using the Monad rule. Simplifies the bind with Pure.

Step 13: The a comes as an argument, but we ignore it (use _) and return v. Simplify to a function with no a.

Step 14: Replace return with Pure (return = pure = Pure in our Monad). Final form in continuation-passing style! We calculate e, get result r, call Free with Restore, which gives us v, pass to Store, ignore result, and end with Pure v signaling completion.