Lazy Fold Right

LazyFold.scala

type Lazy[A] = () => A

def foldRight[A, B](xs: List[A], z: B)(f: (A, Lazy[B]) => B): B =
  xs match {
    case Nil    => z
    case h :: t => f(h, () => foldRight(t, z)(f)) 
  }

def find[A](xs: List[A])(p: A => Boolean): Option[A] = {
  val init = Option.empty[A]
  def ite(a: A, rest: Lazy[Option[A]]): Option[A] =
    if (p(a)) Some(a) else rest()

  foldRight[A, Option[A]](xs, init)(ite(_, _))
}


// For a quick example
val ss: List[Int] = (1 to 20).toList
def is13(i: Int): Boolean = {
  val b = i == 13
  if (b) println(s"$i IS YAI 13") else println(s"$i IS NOT 13")
  b
}

find(ss)(is13)