Fantasy-land: Update `chainRec`

[i-am-tom]

I _know_ I'm not the first to bring this up - this has been discussed in #151, #152, #185, and probably others - but there are some inconsistencies to fix with chainRec that are undoubtedly best addressed sooner rather than later. I hope this all makes sense!

I've been writing a series of posts on Fantasy Land spec, but I've hit a wall with this one, as I think we've made it a bit harder than we should've, so I'd like to propose we do something about it 😄 tl;dr, my proposed signature is this:

chainRec :: ChainRec m => m a ~> (a -> m (Either a b)) -> m b

Either

Using Either makes this type _much_ more comprehensible to beginners. Every time I use chainRec, I have to look at MonadRec in Scala or PureScript to remember _how_ it works, and then mentally translate it to the current approach, and I know I'm not the only one 😳 I can only do this because of my limited knowledge of those languages, though!

In production, we've simply taken to using something like the following. Forgive the name - it was a bad homonym joke that apparently caught on...

//+ trainWreck :: ChainRec m => (a -> m (Either a b)) -> ((a -> c, b -> c, a) -> m b)
const trainWreck = f => (next, done, x) =>
  chain(cata({ Left: next, Right: done }), f(x))

It _works_, but no one who hasn't seen Haskell/PS/Scala understands _why_ 😞 The lack of understanding isn't totally due to this, though - there are two other problems...

m b

The eventual return of chainRec is m b. If we imagine writing the type in PureScript/RankNTypes, we'd get here:

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

The b type gets introduced in our inner function, and then reappears in the return value of the outer function. For a strict type system, one of these doesn't know what b is. Either b is declared in outer scope, and the inner function has no idea what b is (which makes writing such a function really hard), _or_ it's declared in inner scope, and can't be returned from outer scope! @joneshf mentioned this somewhere ("where does the b come from?"), and it's certainly another point of confusion for newcomers. Of course, with an Either, none of this matters - positive and negative positions, etc. Again, @joneshf did a much better job than I will of explaining this, hah!

m a ~>

The spec entry talks about a _value_ implementing the ChainRec spec, but chainRec is a static function (vs. chain that is at the instance-level). Firstly, this creates some confusion as it implies they work in similar ways. Secondly, if we _did_ make it an instance method, we wouldn't need the a parameter on the inner function as we'd already have it! Given that we only use it once - at the start - and we _know_ m is a chain type, we can safely assume that the user can always get to an m a, and is probably more likely to have started there. Of course, it's not as simple as pure (which I assume is why other specs call this MonadRec), but we _do_ have a function at our disposal that will lift an a inside an m _or_ give us the end result!

---

I know there has been mention of the ordering within Either, so I guess this would be a good change to add to the end (were this proposal accepted!), but these are, as I see it, the main worries. Of course, it seems that none are original thoughts on my part, but I think it's probably worth addressing them collectively!

Thanks :)

[Avaq]

In defense of chainRec: I'm not here to dismiss your ideas, but rather to present the other side of the story. I don't have a background in any kind of functional programming language, and purely as a JavaScript programmer consider ChainRec to be quite fine.

there are some inconsistencies to fix with chainRec

The chainRec spec is not inconsistent, right? It's just several layers of abstraction which may be difficult to grasp. How is it inconsistent?

Every time I use chainRec, I have to look at MonadRec in Scala or PureScript to remember how it works [...] I can only do this because of my limited knowledge of those languages, though!

I have no other reference than the FantasyLand spec, and I get along with chainRec quite well.

Using Either makes this type much more comprehensible to beginners.

I (a beginner) was quite happy that the FantasyLand spec doesn't push any specific types onto me. I was able to implement chainRec with a very minimal type for c.

If I had to use an Either type, I would have to implement it myself, bothering my users with a partially implemented Either if I didn't go all the way, or use an existing implementation, which brings in a whole new dependency just to get chainRec working which is meant to be abstracted over any way.

I worry that requiring authors to use Either will lead to many different implementations of the Either type being created.

"where does the b come from?"

c is a wrapper over a b. You are given two functions to wrap your a or b in a c, and are expected to do so as indicated by the return type of your function (m c). It is then unwrapped before it's returned, as indicated by the return type of chainRec (m b). Maybe clarifying the fact that c is a wrapper type would help:

chainRec :: ((a -> c a d, b -> c d b, a) -> m (c a b), a) -> m b

I'm not sure if that's proper, but at least now you can see that c is just another word for Either, but generalized to any "bi-wrapper" type.

if we did make [chainRec] an instance method, we wouldn't need the a parameter on the inner function as we'd already have it!

Not quite, the second parameter is of type a, whereas it would be of type m a if chainRec would be a method. You would have to first MyChainRec.of('a') before you can use chainRec, like you mentioned. But I don't think wrapping a value for the sake of accessing a method which may as well have been a normal function is good practice. With currying in mind, I think the current argument order is rather convenient: the following two functions are "equal", except the first might not have constant stack usage:

//    recur :: Integer -> Integer
const recur = x => x > 10000 ? M.of(x) : M.of(x + 1).chain(recur);

//    recur :: Integer -> Integer
const recur = M.chainRec((next, done, x) => M.of(x > 10000 ? done(x) : next(x + 1)));

[i-am-tom]

I should clarify: I understand (and use in production) chainRec. However, to address those points in order:

I don't see any inconsistencies, just some layers of abstraction.

There's a misuse of the term "abstraction" here. It's one abstraction that _hides_ the relationship between chain and chainRec, which we'd ideally like to make as clear as possible. It's moving away from "abstraction" and more towards "obfuscation" in this regard.

I get along with chainRec quite well

You are certainly more capable than me, then 🙇 However, my experience with trying to introduce this approach to programmers without a functional background hasn't been nearly so positive :(

I was able to implement chainRec with a very minimal type for c.

No matter how minimal your type, it simply doesn't need to exist in the case of Either or Result, which could be implemented as the simplest of sum types. Why would you have to implement Either yourself?

Conceivably, in the case of fluture, a better approach would have been to introduce a typeclass along the lines of MonadError (i.e. a way of noting "success" and "failure" - res and rej) and use _that_ as a constraint, which would mean you wouldn't need a separate inner type at all!

c is a wrapper over a b

Careful here: for a start, your type should be (a -> c a b, b -> c a b, a) -> m (c a b), a) -> m b, which is _definitely_ more confusing. The fact is that the done: true flag exists only to mimic a sum type. If we introduced a spec that said (a -> m (n a b)) "for some bifoldable n", then we're in total agreement here, and I'd be cool with that as a middle ground. However, "bifoldable" is definitely less beginner-friendly than "either", and a -> c looks like total magic to someone trying to understand parametricity :sparkles:

You would have to first MyChainRec.of('a')

No; this would make MyChainRec a monad (more specifically a MonadRec). The easiest way to "lift" it is to run your bifoldable-returning function, which is exactly the plan at every other step!

---

I think, ultimately, my concern comes from the fact that we run into troubles that no other community seems to have, simply because of this encoding. The ranks involved mean that you either have to say "don't look too closely at this", _not_ teach people how the type signatures work, or explain higher-rank polymorphism. Regrettably, most will go for the first option, and that's not going to do any of us any good in the long run :(

[safareli]

Signature with forall should look like this:

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

So it's not true to say "where b is coming from". the point of chainRec is to get from some accumulating value of type a to b (in m).

It's almost chain except you instead of directly returning m b you get contractors for iteration object c which you should wrap in m and the structure will take care of it.

The function exists just so that you get stack safety and it could be abstracted away using Free monad like structures (for example if you do recursive chain using fluture you are safe). and indeed it's somewhat obfuscated (to don't ask for concrete implementation of Either or Step(this is used in PS)).

Using MonadError might not be correct as returning a is not failure it's just next iteration step towards getting b, but anyways I can't quite see how you think MonadErrorcould be useful here, an example implementation of chainRec for Identity using MonadError might help.

[i-am-tom]

Intuitively, a type-checker couldn't rectify that type because there's no way (via parametricity) to get from b to m b. I'm quite open to compilable examples to the contrary, though!

Again, I totally understand what it's meant to accomplish, although I'm not sure it requires the Free hammer in order to be useful. My point about MonadError was simply that if you have a sum type with some kind of "left" and "right" branch, it already has this capability built in, although I possibly stretched the metaphor by using a concrete example 😳

@safareli, thoughts on making chainRec (in whatever form) an instance method rather than a static one?

[safareli]

if you make it instance method then you should also require structure to be a Monad otherwise it will be more limiting then what we have now. and if you require monoid then structures which are not monad but are chain couldn't implement it so we loos number of instances which can exist.

[i-am-tom]

The first step of the loop is a -> m (Either a b); my suggestion is that we expect the user to make that first call in the few cases where it's needed. The majority of (practical) Chain types _are_ Monad types, and it's one extra explicit call for those who aren't - again, I don't think anyone's given any examples where Monad would be required to write such a ChainRec. I guess more concrete examples of the objections would help? I'm struggling to find any myself 😞

[safareli]

Map is not a Monad but can be ChainRec. in scalaz and cats (both are scala libs) there is no monad constraint on ChainRec

[safareli]

if you think step function (forall c. a -> c, b -> c, a) -> m c should instead be a -> m (Either a b) you should provide a way to do that we didn't went with this pass as it will ask library authors as well as users of those libs to use some specific Either which we didn't wanted. if you think it's good way to go or know some better way please say why and how.
also to note for example sanctuary defines function you want using there own either type (which delegates to current chainRec) https://sanctuary.js.org/#chainRec

[i-am-tom]

but I can still feed Map into my a -> m (Either a b), right?

I mentioned in my reply to @Avaq that we _could_ introduce Bifoldable and then specify that as a requirement? That way, we wouldn't specifically require Either, but can be sure that we have a fantasyland-specified interface for dealing with these cases? I'll play with some sample code in the morning!

[safareli]

if chainRec requires Monad then Map can't be chainRec as it's not a Monad

actually Bifoldable constraint could be a good way to go. before we thought about having some interface like thing for it but actually no one mentioned Bifoldable then so we went with function way.

class Bifoldable p where
  bifoldr :: forall a b c. (a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
  bifoldl :: forall a b c. (c -> a -> c) -> (c -> b -> c) -> c -> p a b -> c
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> p a b -> m

I would be happy with

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

And library author could just call bifoldMap Left Right

update

it's not quite true as Tuple is bifoldable :/

so we can't use Bifoldable for it

[i-am-tom]

Ah, that is a damn shame. I guess the only applicable structure is coproduct, which is, well, a sum type :/ Curses! I'll keep thinking.

[ivenmarquardt]

I think the underlying problem is that the spec doesn't specify the short circuiting mechanism (i.e. how to trigger the base case) of chainRec, but leave the details to the consumers. You can either (no pun intended) specify a type class or not, but I don't think it is a good idea to specify it partially. In its current form the type signature is not very useful, since it doesn't really help to infer possible implementations.

[safareli]

Again type could be more helpful if we used custom data types:

data Step a b = Loop a | Done b
tailRecM :: forall a b. (a -> m (Step a b)) -> a -> m b

but we don't

[paldepind]

Why not do something similar to #224?

data Step a b = Loop a | Done b can be encoded as {done: boolean, value: A}. People can even implement Either so that is has a done property which is true for Left and false for Right. Then the Either can be used directly in place of the object.

[ivenmarquardt]

I see, FL is meant for type constraints only, not for types per se. However, with ChainRec two functions are introduced, which express the recursive protocol. Alternatively, one could use functions that represent sum types, i.e. a n-ary function for each n-ary value constructor (or a value for nullary constructors). The Either type would be Either :: forall r . (a -> r) -> (b -> r) -> r. And you could produce a value by applying the corresponding catamorphism, e.g. Right :: b -> (a -> r) -> (b -> r) -> r, which represents the value constructor of this encoding.

There is no need to use a generic Either of course. An ordinary sum type without functor/applicative/monad constraints could be used instead: Step and Loop/Done, which emphasizes its purpose.

I think Church encoding was already suggested in an earlier related thread. There seems to be a lot discussions on this topic - sorry for bringing it up again.

[safareli]

Passing constructors to iterator is almost church encoding I think.

And one could easily guess which constructor is for done, just by type ( (c. (a -> c, b -> c, a) -> m c, a) -> m b to be able to return something of type m b i.e. for loop to end, you need to construct c using b -> c as there is no other way to get b out of the loop)

[alexandru]

My 2¢ ... I like the current signature.

Here's what I currently have:

export interface ChainRec<F> extends Chain<F> {
  chainRec<A, B>(f: <C>(next: (a: A) => C, done: (b: B) => C, a: A) => HK<F, C>, a: A): HK<F, B>
}

That's actually understandable IMO and not very different from the proposed:

export interface ChainRec<F> extends Chain<F> {
  chainRec<A, B>(f: (a: A) => HK<F, Either<A, B>>, a: A): HK<F, B>
}

I mean, without some documentation to understand how this signature works (e.g. keep calling f until a Right(b) is returned) and some practice to understand the use-cases, it's not that obvious.

N.B. There's no way to specify an Either data type as an interface, because you need the data constructor as well.

So either impose an Either on all implementing libraries, which would suck because your Either is probably not going to be my ideal Either and also because implementing libraries will not inter-operate on other essential data types anyway. Or leave it like it is.

The current encoding is awesome because it has no dependencies on data types. Introduce dependencies on data types and the specification will be much less useful than it currently is.

[gabejohnson]

@alexandru see #280 and #281 for proposals that get around specifying an implementation.