Functional programming creates a lot of benefits in creating a distributed system. You will deal with fewer bugs in a concurrent environment because everything is immutable. It also helps us local reasoning and composition - we can construct applications and programs like lego building blocks that will produce a predictable outcome. With having a predictable outcome, we can understand code to scale with the size of the codebase.
However, there is also a downside if you strictly make everything “pure” and immutable. For instance, in my previous articles, having a functional data structure, such as List, can be costly. Let’s take the below as an example:
List(1,2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2)
Each of these operations above will make its input and create a new intermediate List on the output. The expression above for the map
function will introduce a new List(2,3,4,5)
. Then, it goes to filter
function and filters out all the odd numbers, which produces a new List, List(2,4)
that gets a pass to the last map
operation. Each transformation gets to produce a shortlist that gets used as an input to the next transformation and is then immediately discarded. If we manually produce a trace for its output evaluation, it will be something like this:
List(1,2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2)
List(2,3,4,5).filter(_ % 2 == 0).map(_ * 2)
List(2,4).map(_ * 2)
List(4, 8)
You must be thinking right now - the syntax is compositional and succinct, but the performance and memory usage are terrible. Ideally, we will want to fuse the sequence transformation on each element like this in one go. We don’t want to wait for all the List to finished transforming the first element to have its second transformation. We also don’t want to create a temporary list element in the middle of each change.
How do we do that?
We can change the structure to a while loop and for a loop. However, we want to persist in the compositional structure of the transformation rather than writing monolithic circuits. One way of doing this is to make your data structure non-strict (lazy).
What is non-strict (lazy)?
Before we talk about what is a non-strict, I want to explain what is strict.
The formal definition of strictness is - “If an expression’s evaluation runs forever or throws an error instead of returning a definite value, we say that the expression doesn’t terminate, or that it evaluates to bottom. A function f
is strict if the expression f(x)
evaluates to bottom for all x that value to bottom.”
Simply put, if a function is strict, it means that function will evaluate all of its arguments. Let’s take an example:
def add[A](a:A, b:A): A = a + b
add(1,2)
Function add
will received an evaluated arguments of 1
and 2
. If we do something like this:
add(sys.error("something wrong"), sys.error("something wrong"))
It evokes the arguments first before function add
has a chance to evaluate the value of its arguments.
Strictness is the norm in programming languages, and indeed most programming language support functions that expects its arguments to be evaluated.
Non-strictness means that the function can choose not to evaluate one or more of its arguments first when evoking that function.
Non-strictness is widely used in programming languages, and you most certainly familiar with the concept. One example is when a short-circuit happens in a boolean operation, &&
and ||
. Although the boolean operation is a built-in syntax within the language, we can think of it as a function that chooses not to evaluate the next one, depending on the result of the first evaluation.
false && (1 + 1 == 2)
The following expression will not be evaluated because the first expression returns a false
.
If you would like to create an operation of &&
in scala it will be something like this:
def and(a: () => Boolean, b: () => Boolean): Boolean = if(!a()) {
false
} else if(!b()) {
false
} else {
true
}
The argument that we pass unevaluated has a () =>
syntax, usually, it is called a thunk. The () =>
means that you pass in a function with zero arguments. Then, inside the function, a()
evokes that function.
Since this has been widely used in Scala, we have more beautiful syntax, : =>
, which is usually called _pass by name.
Therefore, the above function can be translate to this:
def and(a: => Boolean, b: => Boolean): Boolean =
if(!a) {
false
} else if(!b) {
false
} else {
true
}
Note that these evaluated functions are not cached. Therefore, if you call them multiple times, it will get evoked numerous times. To memoized the value that is evaluated, you have to use lazy val
. It assessed the value lazily once and memoized the result after.
Lazy List (Stream)
Now you know the definition of non-strictness and Laziness. Let’s solve the first example by re-create our List to “Lazy” ones.
Intuition
We will first define the definition of the Lazy List. Then, we will create foldRight
functions, the generic function of transforming values, and foldRight
to create map
and filter
for our Lazy List. Lastly, I will explain how the programs flow and why it is much more performant to use Lazy List than the regular immutable List.
Definition of Lazy List
Let’s defined Lazy List:
sealed trait LazyList[+A]
case class Cons[A](head: () => A, tail: () => LazyList[A]): LazyList[A]
case object End extends LazyList[Nothing]
object LazyList {
def cons[A](head: => A, tail: => LazyList[A]): LazyList[A] = {
lazy val h = head
lazy val t = tail
Cons(() => h, () => t)
}
def empty[A]: LazyList[A] = End
}
The above implementation is a simple example of a Lazy List. The cons
and empty
is a smart constructor for caching any object instantiation.
This is similar to the regular List, except everything is a thunk. This way, we need to force arguments to evaluate the function definition.
Separate program Description and Evaluation
Now that you see how everything is non-strict, we can separate the description and its evaluation. In my previous article, How to Write Data processing Application in FS2, all values inside the Stream are a description of the program, until there is unsafeRunSync
.
A significant theme of Functional programming is about separation concerns. For instance, functions as first-class describe some computation in the body but will execute if we supply the arguments to those functions. We used Option
to capture the program’s description that there is some error that occurred. However, it leaves the decisions of what to do with those errors as its separate concern. With Lazy List, we build up the computation of a sequence of elements without evaluating them, only running those elements when we need them.
This has a significant advantage: we can describe an abundant expression more than we need and evaluate only a portion of it. You will see that in the example of foldRight
below.
Implement foldRight
Let’s define the implementation of foldRight
:
sealed trait LazyList[+A] {
def foldRight[B](z: => B)(f: (A, => B) => B): B = this match {
case Cons(h, t) => f(h(), t().foldRight(z)(f))
case Empty => z
}
}
One major difference with the regular foldRight
in List is that the B
is a pass-by name. It means that the function t().foldRight(z)(f)
will be evaluated depends on the function f
. In regular list, it will be a recursive call to t().foldRight(z)(f)
until it hits base case. Over here, it will depend on how the f
function is implemented.
Let’s take an example of defining a function exists
which will check if the value exist in the List:
def exists[A](lst:LazyList[A], p: A => Boolean): Boolean = lst.foldRight(false)((a, b) => p(a) || b )
This function will traverse through the list until p(a)
returns true. Once p(a)
returns true, it won’t evaluate b
and short-circuit. We cannot do that with a strict function foldRight
since it will recursively call t().foldRight(z)(f)
until the function hits a base case.
Implement Map and Filter
Back to the first example above:
List(1,2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2)
Let’s define map
and filter
functions.
By implementing a generic recursive function foldRight
, we can apply map
and filter
using foldRight
in a non-strict manner.
sealed trait LazyList[+A] {
def map[B](f: A => B): B = foldRight[LazyList[B]](empty[B])((a,b) => cons(f(a), b))
def filter(f: A => Boolean): LazyList[A] = foldRight[LazyList[B]](empty[B])((a,b) => if(f(a)) cons(a, b) else b)
}
When we defined map
and filter
in a non-strict way, the implementation doesn’t fully generate the answer. Even when the function unfolds, it will just do enough work to generate the requested elements.
Let’s trace layer on layer how our first example works:
Since we are using LazyList
, we need to execute a toList
function that will force evaluation on the subsequent LazyList
.
sealed trait LazyList[+A] {
// ... map, foldRight, and filter implementation here
def toList:List[A] = this match {
case Cons(h, t) => h() :: t().toList
case Empty => Nil
}
}
object LazyList {
// all the smart ctor such as cons, empty is here
apply[A](a:A*): LazyList[A] = if(a.isEmpty) empty else cons(a.head, apply(a.tail: _*))
}
Mimicking the above example with LazyList
:
LazyList(1,2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2).toList
Tracing on how this program runs:
LazyList(1,2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2).toList
Cons(2, LazyList(2,3,4).map(_ + 1)).filter(_ % 2 == 0).map(_ * 2).toList
Cons(2, LazyList(2,3,4).map(_ + 1).filter(_ % 2 == 0)).map(_ * 2).toList
Cons(4, LazyList(2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2)).toList
4 :: LazyList(2,3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2).toList
4 :: Cons(3, LazyList(3,4).map(_ + 1)).filter(_ % 2 == 0).map(_ * 2).toList
4 :: LazyList(3,4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2).toList
4 :: Cons(4, LazyList(4).map(_ + 1)).filter(_ % 2 == 0).map(_ * 2).toList
4 :: Cons(4, LazyList(4).map(_ +1).filter(_ % 2 == 0)).map(_ * 2).toList
4 :: Cons(8, LazyList(4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2)).toList
4 :: 8 :: LazyList(4).map(_ + 1).filter(_ % 2 == 0).map(_ * 2).toList
....
Now, the filter
and the map
transformation are interleaved - it will add one with the map
on that element, and test with filter
to see if that element is divisible by 2, and multiply that output by 2. All the aspects inside LazyList are not divided by two; then, it will keep calling the next element until it creates a Cons(a, b)
. The toList
function is to force to evaluate the subsequent component if it is another Lazy List.
Note: If you run val lst = LazyList(2,2,2).map(_ + 1).filter(_ % 2 == 0)
. Then, print(lst)
it will evaluate the entire List without needing to foce evaluation on all the elements in the Lazy List.
The incremental nature of Lazy List transformation also has significant consequences on the memory usage. Because the intermediary List is not generated, the transformation only requires enough working memory to store and transform the current elements. Thus, the garbage collector can reclaim the space allocated for the values emitted by the map, and as soon as the filter determined, it is not needed.
Takeaway
- By evaluating data structure in a non-strict manner, we can separate the description with its evaluation.
- Using the non-strict function, we can optimize the transformation and only transform the required elements in the List.