Traversable.foldRight considered harmful

[regiskuckaertz]

Right folds are lazy by nature. A better type would be:

def foldRight[S, A](fa: F[A])(s: => S)(f: (A, => S) => S): S

This is how the fold can short-circuit instead of traverse the whole structure.

[adamgfraser]

@regiskuckaertz This is definitely a good topic. I think the main issue here is that this signature is not stack safe. I think we could do a version with ZPure that short circuits and would be stack safe.

[regiskuckaertz]

that would be amazing! Is stack-safety a guarantee you want to provide by default? It is quite strong. I wonder if this is not too limiting, but admittedly there are not many lazy data structures in Scala.

[sideeffffect]

Would it work like this https://github.com/scala/scala-collection-contrib/pull/18 ?

[adamgfraser]

@sideeffffect Blast from the past, right!

I spent some time on this yesterday and I think unfortunately it is more complicated. We can definitely implement some kind of stack safe lazy fold on a concrete data structure, using a signature like that or lazyFoldRight from the same source.

However, I think for this to be an operator on Traversable we would want to be able to implement a lazy fold in terms of foreach and I don't think that is possible in a stack safe way.

The basic problem is that to short circuit we need to call zipWith after traversing each element of the structure before continuing the traversal so we can short circuit, as in the second implementation below. However, this is not stack safe.

// stack safe but not lazy
def foreach[G[+_]: IdentityBoth: Covariant, A, B](list: List[A])(f: A => G[B]): G[List[B]] =
  list.foldRight[G[List[B]]](Nil.succeed)((a, bs) => f(a).zipWith(bs)(_ :: _))

// lazy but not stack safe
def foreach[G[+_]: IdentityBoth: Covariant, A, B](list: List[A])(f: A => G[B]): G[List[B]] =
  list match {
    case Nil => Nil.succeed
    case h :: t => f(h).zipWith(foreach(t)(f))(_ :: _)
  }

And I don't think we can use another effect like ZPure to provide stack safety in the second case because while G could potentially short circuit, we don't have a way for G to signal that it has short circuited so that we can short circuit the traversal with ZPure as well.

I am continuing to work on this but I think it is a tricky problem.

[regiskuckaertz]

oh I did not see that. Yeah I agree, this is a tough one. The trick used in PureScript is to write foldr in terms of foldMap and vice versa, then ask the use to provide an implementation for at least one of them; perhaps you could do the same with foldRight/foreach?