Calling non-strict function in Scala with explicit types doesn't compile, inferred types works

Question

Working through the excellent "FP in Scala" by Chiusano Rúnar Bjarnason, had a strange compilation error when trying to implement Stream#takeWhile lazily through #foldRight. Given the following code in the book (also on GitHub):

trait Stream[+A] {
  def foldRight[B](z: => B)(f: (A, => B) => B): B = 
    this match {
      case Cons(h,t) => f(h(), t().foldRight(z)(f))
      case _ => z
}

case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

object Stream {
  def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
  def empty[A]: Stream[A] = Empty
}

I tried:

def takeWhile_fold(p: A => Boolean): Stream[A] =
  foldRight(empty[A])((it:A, acc:Stream[A]) => if (p(it)) cons(it, acc) else acc)

But this gives the compilation fault:

type mismatch;
[error]  found   : (A, fpinscala.laziness.Stream[A]) => fpinscala.laziness.Stream[A]
[error]  required: (A, => fpinscala.laziness.Stream[A]) => fpinscala.laziness.Stream[A]
[error]       foldRight(empty[A])((it:A, acc:Stream[A]) => if (p(it)) cons(it, acc) else ac

But if I remove the types on the lambda, it works:

def takeWhile_fold(p: A => Boolean): Stream[A] =
  foldRight(empty[A])((it, acc) => if (p(it)) cons(it, acc) else acc)

There is no way in Scala to state in the calling code that it should be a by-name parameter, is there? (Does it even make sense for the caller, it is the receiver that decides, right?) Attempting:

def takeWhile_fold(p: A => Boolean): Stream[A] =
  foldRight(empty[A])((it, acc: => Stream[A]) => if (p(it)) cons(it, acc) else acc)

Gives another compilation error:

[error]      identifier expected but '=>' found.
[error]       foldRight(empty[A])((it, acc: => Stream[A]) => if (p(it)) cons(it, acc) else acc)
                                            ^
[error]  ')' expected but '}' found.
[error] }
[error] ^
[error] two errors found

I've solved the exercise, but my questions are - why doesn't it work with explicit types? Do they enforce strictness somehow while the receiver must have non-strict? And if so, is there any syntax in Scala so the caller can signal that "yes, this is by-name parameters"?

Answer 1

Yes, by-name ends up being part of the signature. You can imagine that by-name parameters are implemented by the compiler by translating this:

def foo(n: => Int) = ... n ...

to this:

def foo(n: () => Int) = ... n() ...

A side effect of this is that, if you reference by-name parameters multiple times, they will be evaluated multiple times. So this:

def bar(n: => Int) = n + n
bar( { println("foo"); 5 } )

Will print foo twice before returning 10. It's the same as this:

def bar(n: () => Int) = n() + n()
bar { () => println("foo"); 5 }

As for whether you can explicitly state that a lambda takes by-name parameters... I'm not sure. I tried this:

def foo( f: ( => Int) => Int ) = f({ println("foo"); 5 })
foo { (a) => a + a }

Which worked. I tried these:

foo { (a : Int ) => a + a }
foo { (a : => Int ) => a + a }

Which failed.

The spec seems to indicate that the type property of formal parameters to functions are generated with the ParamType syntax rule, whereas the type property of anonymous functions parameters uses the plain Type rule. And the => by-name indicator is on ParamType.