Scala Functional Design & Programming - Chapter 5 (5)
Table of Contents
I bought "Scala Functional Design & Programming - A Comprehensive Guide to Functional Programming by Scalaz Contributors".
I'll read it bit by bit and summarize each chapter.
This time, I'll cover Chapter 5. It's about lazy evaluation.
Chapter 5
This chapter deals with non-strictness, which is essentially lazy evaluation. This is a very functional programming-like concept and has a significant impact on execution efficiency. I want to delve deeper into it.
Scala's Non-Strict Functions
This is often represented in the form of ↓ in JS.
def hoge(f: () => Int) = ... f()
hoge( () => 21 )
This form is called a thunk and is commonly used. Even in JS libraries, the name "redux-thunk" is used.
However, writing it every time is cumbersome, so in Scala, the initial empty parentheses are omitted, and the parentheses are not needed when calling it either. Convenient!
def hoge(f: => Int) = ... f
When retrieving a value from a sink, the result is not cached, so it's necessary to put it in a lazy constant.
lazy val x = f
This way, x is evaluated when it's first used, and the result is cached.
Stream
After introducing the smart constructor for caching, it's time for the usual practice problems.
Create a
toListfor Stream.
def toList: List[A] = {
this match {
case Cons(h, t) => h() :: t().toList
case _ => Nil
}
}
This works, but it's not tail-recursive, so it's slow. The answer also included a solution using reverse and tailrec with mutable.ListBuffer.
Create
take,drop, andtakeWhilefor Stream.
def take(n: Int): Stream[A] =
this match {
case Cons(h, t) if n > 0 => cons(h(), t().take(n - 1))
case _ => Empty
}
def drop(n: Int): Stream[A] =
this match {
case Cons(h, t) if n > 0 => t().drop(n - 1)
case _ => this
}
def takeWhile(p: A => Boolean): Stream[A] =
this match {
case Cons(h, t) if p(h()) => cons(h(), t().takeWhile(p))
case _ => Empty
}
In the answer for take, it's pointed out that when n == 1, an unnecessary t() is called, so it's better to branch for n == 1. It's a small but important detail.
Next, the implementation of exists is explained, which utilizes Stream to stop evaluating as soon as it finds a match. foldRight is also implemented in a way that stops evaluating as soon as it finds a match.
Here's another practice problem.
Implement
forAllto check if all elements satisfy a condition.
def forAll(p: A => Boolean): Boolean =
foldRight(true)((a, b) => p(a) && b)
I was able to write it without thinking about Stream at all. It's truly generalized.
Implement
takeWhileusingfoldRight.
def takeWhile2(p: A => Boolean): Stream[A] =
foldRight(Empty: Stream[A])((a, b) => if (p(a)) cons(a, b) else Empty)
Implement
headOptionusingfoldRight.
def headOption: Option[A] = foldRight(None: Option[A])((a, _) => Some(a))
If the list is empty, it returns None, so this implementation is straightforward. The second argument b is not evaluated, so the loop doesn't occur, and Stream is utilized properly.
Implement
map,filter,append, andflatMapusingfoldRight.
I realized that the type specification for Empty can be done in this way, which is convenient.
def map[B](f: A => B): Stream[B] =
foldRight(Empty: Stream[B])((a,b) => cons(f(a), b))
def filter(f: A => Boolean): Stream[A] =
foldRight(Empty: Stream[A])((a,b) => if(f(a)) cons(a, b) else b)
When I wrote it enthusiastically, I encountered a compile error for append. It's a problem related to covariance and contravariance, which I didn't fully understand, so I had to rely on another site.
It's very easy to understand. I'm not sure if I can use it fluently, but I was able to avoid the variance check for now.
def append[B>:A](a: => Stream[B]): Stream[B] =
foldRight(a)((c,d) => cons(c, d))
def flatMap[B>:A](s: A => Stream[B]): Stream[B] =
foldRight(Empty: Stream[B])((a,b) => s(a).append(b))
By using these functions to process Stream, only the necessary parts are evaluated, and unnecessary instances are not generated. Even when processing heavy lists, it's very efficient.
st.map(---).filter(---)
st.filter(---).headOption
The order of loop application itself seems to change, so Stream is also called "first-class loop". It's also memory-friendly because the filtered-out elements and newly generated elements are immediately garbage-collected.
Next, I'll cover the basics of Stream and then move on to infinite streams, which are often cited as examples.
Create a function
constantthat generates an infinite stream of a specified value.
def constant[A](a: A): Stream[A] = cons(a, constant(a))
It's simple, but it's a bit wasteful to create a new cons every time. A better approach is to create a lazy object and reuse it.
def constant2[A](a: A): Stream[A] = {
lazy val v: Stream[A] = Cons(() => a, () => v)
v
}
Create a function
fromthat generates an infinite stream ofn,n+1,n+2, ...
def from(n: Int): Stream[Int] = cons(n, from(n+1))
Create a function
fibsthat generates a Fibonacci sequence stream.
def fibs(): Stream[Int] = {
def loop(i1: Int, i2: Int): Stream[Int] = cons(i2, loop(i1 + i2, i1))
loop(1, 0)
}
It's a common example.
Create a more general stream generation function
unfoldand use it to implementfibs,from,constant, andones.
def u_fibs(): Stream[Int] =
unfold((0, 1))(a => Some(a._1, (a._2, a._1 + a._2)))
def u_fibs2(): Stream[Int] =
unfold((0, 1))(a => {
a match {
case (i1, i2) => Some(i1, (i2, i1 + i2))
}
})
def u_fibs3(): Stream[Int] =
unfold((0, 1)) { case (i1, i2) => Some(i1, (i2, i1 + i2)) }
def u_from(n: Int): Stream[Int] =
unfold(n)(s => Some(s, s + 1))
def u_constant(n: Int): Stream[Int] =
unfold(n)(s => Some(s, s))
def u_ones: Stream[Int] =
unfold(1)(s => Some(s, s))
There are three implementations of fibs, but they're all the same. When separating variables, I can omit match and write it more concisely.
Implement
map,take,takeWhile,zipWith, andzipAllusingunfold.
def u_take(n: Int): Stream[A] =
unfold((this, n)) {
case (Cons(h, t), i) if i > 0 => Some(h(), (t(), i-1))
case _ => None
}
def u_takeWhile(f: A => Boolean): Stream[A] =
unfold(this) {
case Cons(h, t) if f(h()) => Some(h(), t())
case _ => None
}
def zipWith[B, C](l2: Stream[B])(f: (A, B) => C): Stream[C] = {
unfold((this, l2)) {
case (Cons(h1, t1), Cons(h2, t2)) => Some(f(h1(), h2()), (t1(), t2()))
case _ => None
}
}
def zipAll[B](l2: Stream[B]): Stream[(Option[A], Option[B])] = {
unfold((this, l2)) {
case (Empty, Cons(h2, t2)) => Some((None, Some(h2())), (Empty, t2()))
case (Cons(h1, t1), Empty) => Some((Some(h1()), None), (t1(), Empty))
case (Cons(h1, t1), Cons(h2, t2)) => Some((Some(h1()), Some(h2())), (t1(), t2()))
case _ => None
}
}
According to the answer, zipAll returns (Option[A], Option[B]), so I followed that.
Implement
startsWith.
def startsWith[B](s: Stream[B]): Boolean =
zipAll(s).takeWhile(_._2.isDefined).forAll({
case (Some(a), Some(b)) => a == b
case _ => false
})
I paired the two streams and took the prefix part, then checked if all elements matched.
Implement
tailsusingunfold.
It seems like I can implement it by gradually reducing the stream. I need to explicitly append an empty stream.
def tails: Stream[Stream[A]] =
unfold(this) {
case Empty => None
case s => Some(s, s.drop(1))
}.append(Stream(empty))
Implement
scanRightby generalizingtails.
I didn't understand, so I checked the answer. It seems like it's generating a memoized variable and using foldRight. It's strange that unfold is not used here, even though it was used in tails.
Thoughts
I finally finished it. It looks light, but it's actually heavy. I still need to practice to master it, but it seems like the range of applications will expand greatly depending on whether I know it or not. It's essential for efficient processing, and it's said to improve modularity by separating description and evaluation.
There are many examples in the next chapter, and it seems like there's still a lot to learn.
Next:
