New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

IO.map should never be strictly evaluated #92

Closed
alexandru opened this Issue Dec 5, 2017 · 1 comment

Comments

2 participants
@alexandru
Member

alexandru commented Dec 5, 2017

Currently map is defined like this:

  final def map[B](f: A => B): IO[B] =
    this match {
      case Pure(a) => try Pure(f(a)) catch { case NonFatal(e) => RaiseError(e) }
      case ref @ RaiseError(_) => ref
      case _ => flatMap(a => Pure(f(a)))
    }

Unfortunately this map operation is not equivalent with a flatMap(f.andThen(pure)) because by not suspending execution it can trigger stack overflow errors.

As use-case, here's a toy Iterant implementation:

import cats.effect.IO

sealed trait Iterant[+A] {
  override def toString = "Iterant"
}

case class Next[+A](head: A, rest: IO[Iterant[A]]) extends Iterant[A]
case class Suspend[+A](rest: IO[Iterant[A]]) extends Iterant[A]
case class Halt(ex: Option[Throwable]) extends Iterant[Nothing]

// And a filter operation
def filter[A](f: A => Boolean)(stream: Iterant[A]): Iterant[A] =
  stream match {
    case Next(a, rest) => 
      val tail = rest.map(filter(f))
      if (f(a)) Next(a, tail) else Suspend(tail)
    case Suspend(rest) =>
      Suspend(rest.map(filter(f)))
    case Halt(_) => 
      stream
  }

The filter is pretty straightforward. Now lets build an already evaluated stream and filter it:

val stream = (0 until 1000000).foldLeft(Halt(None) : Iterant[Int]) { 
  (acc, elem) => Next(elem, IO.pure(acc)) 
}

filter((x: Int) => x % 2 == 0)(stream)
//=> StackOverflowException

Currently this filter operation blows with a StackOverflowException.

Why this is bad

Having users to remember which operations are safe and which operations can blow up in their face and in what contexts makes for a really bad user experience. io.map(f) should be equivalent with io.flatMap(x => pure(f(x))) in all contexts, safety comes before performance.

Also monix.tail.Iterant is a real example shipping in Monix 3.0 which is generic over F[_] data types, making use of cats.effect.Sync.

So I'd like a test for this to be in SyncLaws.

@mpilquist

This comment has been minimized.

Member

mpilquist commented Dec 5, 2017

Nice catch, I definitely agree this should be fixed.

I don't have a strong opinion on whether this should be in SyncLaws or in a unit test for IO.

@mpilquist mpilquist closed this in fad700d Dec 14, 2017

mpilquist added a commit that referenced this issue Dec 14, 2017

Merge pull request #96 from alexandru/issue-92-map-laws
Fix #92: Sync.map should suspend evaluation
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment