Add ChainRec type class

[safareli]

TailRec - A type class which captures stack-safe monadic tail recursion.

It would be nice to have a common specification for Tail Recursive Monads in JS community, so that libraries like Free could use the interface to be stack safe.

in PS MonadRectype class looks like this:

class Monad m <= MonadRec m where
  tailRecM :: forall a b. (a -> m (Either a b)) -> a -> m b

So we could have something like this without stack overflow:

Identity.tailRecM((n) => {
  if (n == 0) {
    return Identity(Either.Right("DONE"))
  }
  return Identity(Either.Left(n - 1))
})(20000)

one thing is that there are multiple Either implementations in js and this spec should depend on bare minimum from any Either type. from what I have found the minimum api from Either type is to have a cata method. but before that let's see an implementation of tailRecM of Identity:

const tailRec = (f) => (a) => {
  let v = f(a)
  while (!isDone(v)) {
    v = f(getValue(v))
  }
  return getValue(v)
}

const runIdentity = (i) => i.x

Identity.tailRecM = (f) => (a) => Identity(tailRec((v) => runIdentity(f(v)))(a))

So we have seen usage of it and part of it's implementation. now what we have left is implement isDone and getValue so that they are as generic as possible.

const isDone = (e) => e.cata({
  Right: () => true,
  Left: () => false,
})

const getValue = (e) => e.cata({
  Right: (v) => v,
  Left: (v) => v,
})

so as it looks any Either with cata would work so users shouldn't be tied to some particular Either implementation (as long as it has cata). To note this Either implementation would work with tailRecM.

const Either = {
  Right: (v) => ({ cata: (c) => c.Right(v) }),
  Left: (v) => ({ cata: (c) => c.Left(v) }),
}

---

The hardest was to implement tailRecM for Task/Future but i have made it and after we agree on some interface I would create PRs for some popular Task/Future implementations

[safareli]

@rjmk about c vs t a b, as there are no constraints on t for client there is not a big difference if we say it's c. also this c/ t a b is created used by only tailRec and i think it's better to say as little about it as possible so client's cant do anything with them except wrapping in m. But mostly it would be of type t a b

Also I thought about passing constructors to func vs providing destructor to tailRec and there is one good use case of providing destructor to tailRec.

const tailRecWithFold = (m,f,i) => m.tailRec((done,next,v) > v.fold(done,next),f,i)

Can you sketch what are advantages disadvantages with providing destructor vs passing constructors?

[rjmk]

@safareli Yep, you're completely right about c vs t a b. I guess the thing I was thinking was similar to my thought for fold -- that is it's nice to encode the ability to fold on the 2 type parameters. But I guess the signature for tailRec and maybe some laws sorts us out for that.

On destructors vs constructors, the 2 main advantages I see are

1. It sort of gives a Church encoding for any Either-like data type, fixing only the interface we care about. It even gives us the ability to show how there's an Either embedded in our type, even if it's a 'larger' type
2. It saves us from 2 lines of duplication throughout the ecosystem. Not practically a big deal, but philosophically a bit painful

As a disadvantage, I think the API is less familiar to Javascript though, whereas the two callbacks approach is a bit more common.

Anyway, I don't think it's terribly important which we go for

[safareli]

@scott-christopher hypothetically if we would have some other *Rec interfaces MonoidRec or some WhateverRec then with tailRec as a method name we would have conflict. maybe because of that the name is tailRecM in PS to indicate it's Monadic. so for that reason chainRec LGTM and possible if there would be MonoidRec, ApplicativeRec or WhateverRec we would have whateverRec methods without conflicts.

What others think on this?

---

And also what are thoughts on passing destructors?

class Chain m <= ChainRec m where
  -- or tailRec
  chainRec :: ((a -> c) -> (b -> c) -> a -> m c) -> a -> m b

VS

class Chain m <= ChainRec m where
  -- or tailRec
  chainRec :: ((a -> z) -> (b -> z) -> t a b -> z) -> (a -> m (t a b)) -> a -> m b
  -- or    :: ((a -> z) -> (b -> z) -> t     -> z) -> (a -> m  t     ) -> a -> m b

[rpominov]

+1 for chainRec it is also consistent with Chain algebra that has chain method.

And +1 for constructors because they are simpler to use especially if we don't have an Either type on hand:

T.chainRec((next, done, x) => {
  return x > 0 
    ? T.of(next(x - 1)) 
    : T.of(done(x))
}, initial)

// I have to create an ad-hoc Either in order to use `chainRec`
T.chainRec((next, done, result) => 'next' in result ? next(result.next) : done(result.done), x => {
  return x > 0 
    ? T.of({next: x - 1}) 
    : T.of({done: x})
}, initial)

// With an existing Either type it's also a bit more complicated than with constructors
T.chainRec(Either.fold, x => {
  return x > 0 
    ? T.of(Either.right(x - 1)) 
    : T.of(Either.left(x))
}, initial)

[rjmk]

@rpominov One can always define a function with the next / done API around one with the destructor. There's no way to get the constructor version to stop using its version of Either (though you can just fold your version down with the constructors)

I really hope we get somewhere to keep our 🚲 s! I'm reasonably confident that its better to build it from oak than yew, but I don't think the difference is large

[safareli]

@rpominov one can write this with desctructor version:

const chainRec = (m, f, initial) => m.chainRec(
  (next, done, v) > v.fold(next, done),
  (v) => f(
    // or Either.Left
    (a) => ({ fold: (done, next) => next(a) }),
    // or Either.Right
    (a) => ({ fold: (done, next) => done(a) }),
    v
  ),
  initial
)

[rpominov]

So you're saying that if we have chainRec based on destructors we can build a chainRec based on constructors? But this is also true other way around:

const chainRec = (fold, f, initial) => m.chainRec((next, done, x) => {
  return f(x).map(a => fold(next, done, a))
}, initial)

I just don't understand what we can do if we'll be able to use our own Either type? What additional possibilities this opens?

[rjmk]

Yeah, sorry that's what I meant here:

There's no way to get the constructor version to stop using its version of Either (though you can just fold your version down with the constructors)

I guess my point there was that you always need constructors and destructors. With destructors you can do some wrapping to make the API the constructor way and only have one pair of constructors and one destructor. If you have internal constructors you end with 2 destructors and 2 pairs of constructors

[rpominov]

If you have internal constructors you end with 2 destructors and 2 pairs of constructors

Sorry, not sure if i understand this right. You mean that if we consider two versions of chainRec converted from spec API to alternative API (1: https://github.com/fantasyland/fantasy-land/issues/151#issuecomment-244375062 and 2: https://github.com/fantasyland/fantasy-land/issues/151#issuecomment-244378085). The #2 version will have more wrapping/unwrapping under the hood? So it would hurt performance?

Not sure we should care about performance here, but also I just don't understand why one would want to use their own Either, so why would they do #2 conversion even though it's possible?

[rjmk]

Definitely not advocating it because of performance (though you're right that would be the obvious impact)! More philosophy. The ChainRec doesn't need to know how to build and destroy Eithers, it just needs to know how to check if a computation is finished (in a sensibly typed way). We can encode that need in the destructor and then I think the ChainRec is more focused on what it's actually about.

also I just don't understand why one would want to use their own Either

That's fair. The main case I'm thinking of is if one already has a function in terms of Eithers (or Futures, or ...) that could be recursed on. Not sure how common that would be

[safareli]

If we T has some internal Either like structure then users does not need to have it too and could just use done/next functions instead of depending on some other Either and passing fold.

[rjmk]

Basically I think that that passing the constructors is "easier" and asking for the destructors is "simpler" (in the Rich Hickey sense)

[safareli]

If user wants to use the chianRec then, destructor version asks user for some structure which they might only need for using chianRec and not elsewhere and a fold function for that. Also those structures would still need to implement the Either like thing for testing.

When constructor version passes everything needed to actually use the function and user need nothing else (works out of the box). also this way the structure could have some efficient representation of Next/Done and user would not have to think on that at all. I think we could go with constructor version as it would be easy to use. also PS version is going with ADT version for future and constructor version is more like that.

[safareli]

Also with destructor case, asking to pass fold as argument is basically same as asking the object to have the fold method

[rjmk]

Also with destructor case, asking to pass fold as argument is basically same as asking the object to have the fold method

Yeah maybe that would be the more "Fantasy Land" way.

Anyway, I think you should make the PR with the constructors. 👍