Seq instance `.foldRight` has performance implications about cats HOT 7 CLOSED

this is a good catch, but there is no reason to Eval.later(fa.length) imo. I would either just do val length = fa.length or lazy val length = fa.length.

Let's consider two cases:

1. fa.length == 0, in which case it is very fast, in in that case we neve call f.
2. fa.length > 0, in which case we have to call f at least once and evaluate fa.length

So I think eagerly evaluating it is fine. That said, I guess it is possible you would never evaluate the result, in which case we could avoid evaluating fa.length if we use a lazy val.

Finally... there is a deeper issue here...

fa(i) is O(N) for many Seq. We really shouldn't use that. That said... why aren't we just calling this:

from cats.

@johnynek Sure, I'll do that.

from cats.

So when could this be a part of release? I'm asking because I'm excited about my first contribution and also expecting a business impact so it's good to have some estimate in hand. Is there an appetite for a patch version maybe?

from cats.

If snapshots work for you, you can already use 2.10-7499220-SNAPSHOT.

from cats.

Good catch, that seems reasonable to me!

I used .value on the length Eval for simplicity but it can be just as well flatMapped

I'm wondering if we can do something like this:

  Eval.defer {
    val length = fa.length
    def loop(i: Int): Eval[B] = if (i < length) f(fa(i), Eval.defer(loop(i + 1))) else lb
    loop(0)
  }

from cats.

I would either just do val length = fa.length

this defies laziness which is desired IMO

or lazy val length = fa.length

lazy val synchronizes whole class as opposed to Eval which should synchronize only itself iirc

why aren't we just calling iterateRight

That would be great! I'm all for it.

from cats.

@rudolmi do you want to send a PR changing Seq to use iterateRight?

from cats.