Skip to content

Instantly share code, notes, and snippets.

@paraseba
Created May 30, 2018 14:04
Show Gist options
  • Save paraseba/ff3fd89f7e1ec5244a73f1209d9bd81c to your computer and use it in GitHub Desktop.
Save paraseba/ff3fd89f7e1ec5244a73f1209d9bd81c to your computer and use it in GitHub Desktop.
Demonstration of implementing foldRight with by-name parameter
/*
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment