What is the underlying idea of chainRec?

Question

[EDIT]

This is a follow-up question of How to implement a stack-safe chainRec operator for the continuation monad?

Given is chainRec's type

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b

Usually, chainRec is implemented along with a trampoline to allow stack safe recursion within a monad. However, if we drop the trampoline, we can implement chainRec's type for normal functions as follows:

const chainRec = f => x => join(f(chainRec(f), of, x));

Next, I want to apply it to a recursive action:

const map = f => g => x => f(g(x));
const join = f => x => f(x) (x);
const of = x => y => x;

const chainRec = f => x => join(f(chainRec(f), of, x));

const repeat = n => f => x => 
  chainRec((loop, done, args) =>
    args[0] === 0
      ? done(args[1])
      : loop([args[0] - 1, map(f) (args[1])])) ([n, of(x)]);

const inc = x => of(x + 1);

repeat(10) (inc) (0) (); // error

I figured that since there is a join in the definition of chainRec there must be a map involved in the implementation of repeat, so that there are two nested functorial contexts to collapse. Yet it doesn't work and I have no idea how to fix it.

Are you asking about the underlying idea of `chainRec` or about your specific problem? — Bergi, May 27 '18 at 13:59
"*Usually `chainRec` is implemented along with a trampoline to allow stack safe recursion within a monad.*" - yes, that's [what the `c` in the type is all about](https://stackoverflow.com/a/48972000/1048572). "*However, if we drop the trampoline…*" then you should not implement `chainRec` at all but simply `chain`. — Bergi, May 27 '18 at 14:00
What I am trying to understand is if `chainRec` is essentially `chain` implemented with `map` and `join`. Since `chain` now consists of two steps, we can separate them. Mapping takes place within `f` (of `chainRec`) and `join` within `chainRec` itself. — , May 27 '18 at 15:21
Then I tried to check this vague idea by implementing it with a contrived example, but without success. — , May 27 '18 at 15:21
No, `chainRec` is not just `chain = join . map` (every `chain` can be implemented like that). `chainRec` is specifically an optimisation for functions in the form `function recurse(x) { if (…) return of(…); else return doSomethingMonadic().chain(recurse); }` and nothing else. — Bergi, May 27 '18 at 15:30
The important point is that the chaining process implemented with `map`/`join` can be separated in two parts, where the latter (joining) can be deferred and carried out elsewhere (e.g. inside a trampoline). Sorry that I am not able to explain it any better. — , May 27 '18 at 15:38
No, that's not the point of `chainRec`. The point is to defer the `map`ping of the `recurse` call into the evaluation of the `join`ing, where it can be done without growing the stack. Notice that `chainRec = f => x => join(f(chainRec(f), of, x))` does *not* actually do that, it just implements the same type but without any benefits. — Bergi, May 27 '18 at 15:45
I understand that this implementation of `chainRec` is useless regarding stack safety. But without the trampoline boilerplate it gives a clear view of the underlying mechanism. — , May 27 '18 at 15:53
Without the trampoline, it just opens up the chance for unintentional type errors, mixing the monad type and the `c` type. I think this form is only good for understanding how the recursion works out. The actual idea behind it would better be expressed by `chainRec = f => x => unwrapRecAndChain(inLazyRecWrapper(chainRec(f)), stopUnwrap, x))`. — Bergi, May 27 '18 at 15:56

Bergi · Accepted Answer · 2018-05-27T15:11:14.387

Having no idea what your repeat function does, I guess that your call repeat(10)(inc)(0) is supposed to expand to

map(inc)(
 map(inc)(
  map(inc)(
   map(inc)(
    map(inc)(
     map(inc)(
      map(inc)(
       map(inc)(
        map(inc)(
         map(inc)(
          of(0)
         )
        )
       )
      )
     )
    )
   )
  )
 )
)

Since your inc does for some reason return a function _ => Int instead of a plain Int, this will call x + 1 on a function x which leads to the stringification of that function (y => x becoming "y => x1"), which will throw an exception when attempted to be called.

After fixing const inc = x => x + 1;, your repeat function still doesn't work. It would need to be plain recursion, with

const id = x => x
// rec :: ((a -> c, b -> c, a) -> c) -> a -> b
// here with c == b, no trampoline
const rec = f => x => f(rec(f), id, x) // a bit like the y combinator

const repeat = n => f => x => 
  rec((loop, done, [m, g]) =>
    m === 0
      ? done(g)
      : loop([m - 1, map(f)(g)])
  )([n, of(x)]);

repeat(10)(inc)(0)() // 10 - works!

There's no monad involved at all!

If we wanted to use chainRec, we would need to introduce some arbitrary monad (here: the function monad), and the f callback to chainRec would need to return an instance of that monad type instead of just loop/done:

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b
//                                                ^

We could do so by simply wrapping the return value in of:

const repeat = n => f => x => 
  chainRec((loop, done, [m, g]) =>
    of(m === 0
//  ^^
      ? done(g)
      : loop([m - 1, map(f)(g)])
     )
  )([n, of(x)]);

and of course now get an m b, i.e. everything wrapped in yet another function:

repeat(10)(inc)(0)()() // 10
//                  ^^

// repeat(1)(inc)(0) expands to `of(map(inc)(of(0)))

But I doubt this is what you wanted.

Yes, that's exactly what I was looking for! My mistake was to define `inc` as an action, which along with `map` provides the nested functorial context. Clearly `chainRec`'s `f` has to provide this context. — , May 27 '18 at 15:42
`repeat` defined this way is clearly nonsense, of course. I should spent more time to find a less contrived example next time. — , May 27 '18 at 15:43
To avoid leaking the nested context I implemented `chainRec = f => x => join(f(chainRec(f), map(join) (of), x))` — , May 27 '18 at 15:47
@ftor I guess you could keep `inc` as an action and simply build your sequence of calls with `chain` instead of `map`. Though there still wouldn't be any use of `chainRec`, because you are never *tail*-chaining the recursive call — Bergi, May 27 '18 at 15:48
@ftor `chainRec = f => x => join(f(chainRec(f), map(join) (of), x))` has the wrong type, though — Bergi, May 27 '18 at 15:53
This was stupid, anyway. `chainRec = f => x => join(f(chainRec(f), id, x))` makes probably more sense. The type is still wrong, though. Thanks for your help! — , May 27 '18 at 16:07

What is the underlying idea of chainRec?

1 Answers1