Demonstration of implementing foldRight with by-name parameter

folds.scala

/*
 This is a demonstration of foldLeft and foldRight in scala using
 by-name parameters to process infinite streams and to short-circuit
 computations that can finish early.
 */

import scala.annotation.tailrec

/*
 foldLeft can be written in tail recursive form. The recursive call is not
 conditioned, it always happens, so there is no hope of "short-circuiting"
 the computation or computing over infinite streams.
*/

@tailrec
def myFoldLeft[A,B](as: Stream[A], zero: B)(f: (B, A) => B): B = as match {
  case Stream.Empty => zero
  case a #:: tail => myFoldLeft(tail, f(zero, a))(f)
}

/*
 Notice the difference with the Scala definition: the second argument to f
 is passed by name to favor lazyness. If f doesn't evaluate it's second
 argument, the recursive call never happens, and we can short circuit and
 compute over infinite streams.

 Passing zero by name is less important.

 There is no tail recursion, stack accumulates.
*/
def myFoldRight[A,B](as: Stream[A], zero: => B)(f: (A, => B) => B): B = as match {
  case Stream.Empty => zero
  case a #:: tail => f(a, myFoldRight(tail, zero)(f))
}


/*
 Implementing find in terms of myFoldRight. The computation is short-circuited
 as soon as an element is found, even if the Stream is infinite.
*/
def find[A](as: Stream[A])(f: A => Boolean): Option[A] =
  myFoldRight(as, Option.empty[A]) { (a, res) =>
    if (f(a))
      // short circuit happens because we don't evaluate res, which was a by-name parameter to the function
      Option(a)
    else
      // only here the recursive call happens via myFoldRight
      res
  }

/*
 Implementing filter in terms of myFoldRight. It can process infinite
 streams with no issues
*/
def filter[A](as: Stream[A])(f: A => Boolean): Stream[A] =
  myFoldRight(as, Stream.empty[A]) { (a, res) =>
    if (f(a))
      // In the Stream code #:: uses cons, which takes the right argument by name, so
      // the recursive call doesn't happens until evaluation
      a #:: res
    else
      res
  }

/*
 Trying to implement filter in terms of foldLeft leaves us with a
 reversed stream. Adding a call to reverse would "work" but it would
 give us a fully evaluated Stream (ugly)
*/
def filterL[A](as: Stream[A])(f: A => Boolean): Stream[A] =
  myFoldLeft(as, Stream.empty[A])((res, a) => if (f(a)) a #:: res else res)

// 42 as find of a finite stream
val fortytwo = find(Stream.range(1,100,1))(_ > 41)
  // $> Some(42)

// 42 as find of an infinite stream
val fortytwooooooo = find(Stream.from(1))(_ > 41)
  // $> Some(42)

// Finite stream of even numbers
val even = filter(Stream.range(1,100,1))(_ % 2 == 0)
  // $>  Stream(2, ?)
val lasteven = even.take(10).last
  // $> lasteven: Int = 20


// Infinite stream of even numbers
val evennnnnnn = filter(Stream.from(1))(_ % 2 == 0)
// $>  Stream(2, ?)
val lastevennnnnnn = evennnnnnn.take(10).last
// $> lastevennnnnnn: Int = 20

// Finite stream of odd numbers
val oddLeft = filterL(Stream.range(1,10,1))(_ % 2 != 0)
  // notice oddLeft ends up fully evaluated
  // $> oddLeft: Stream[Int] = Stream(9, ?)

// Infinite stream of odd numbers
//val oddLeftttttttt = filterL(Stream.from(1))(_ % 2 != 0)
  // This loops forever! As we said, the recursive call
  // is unconditional