Lazy Evaluation
4 min read
Learning Outcomes
- Understand how functions can be used to delay evaluation of code until the result is actually required
- Understand how this lazy evaluation allows for the definition of infinite sequences
- Code and use lazily evaluated infinite number sequences
Introduction
Usually, expressions in imperative languages are fully evaluated, each step immediately after the previous step. This is called strict or eager evaluation. Functions, however, give us a way to execute code (or evaluate expressions) only when they are really required. This is called lazy evaluation. As an eager student at Monash University you will be unfamiliar with the concept of laziness, since you always do all your work as soon as possible because you love it so much. This is obviously the best strategy for most things in life (and definitely for studying for this course), but laziness as a programming paradigm can sometimes enable different ways to model problems. Early in our introduction to TypeScript we created a function setLeftPadding
that took as argument, either an immediate value or a function that returns a value (simplifying a bit):
function setLeftPadding(elem: Element, value: string | (()=>string)) {
if (typeof value === "string")
elem.setAttribute("style", `padding-left:${value}`)
else // value must be a function
elem.setAttribute("style", `padding-left:${value()}`)
}
We didn’t discuss this much at the time, but this potentially lets us delay the evaluation of an expression. We don’t have to have the value ready at the time of the function call, rather we can provide a computation to obtain the value at a later time.
This is the essence of how functional languages can elevate laziness to a whole paradigm, and it is a powerful concept. For one thing, it allows us to define infinite lists. Previously we defined an interface for List nodes:
interface IListNode<T> {
data: T;
next?: IListNode<T>;
}
Compare the following definition which uses a function to access the next element in the list instead of a simple property:
interface LazySequence<T> {
value: T;
next():LazySequence<T>;
}
Now we can define infinite sequences:
function naturalNumbers() {
return function _next(v:number):LazySequence<number> {
return {
value: v,
next: ()=>_next(v+1)
}
}(1)
}
Note that _next
is immediately invoked in the return. If you are like me you will need to look at this for a little to get your head around it. To summarise: we are defining a function in a returned expression and immediately invoking it with 1 as the starting value. This pattern is used so often in JavaScript it has an acronym: IIFE or Immediately Invoked Function Expression. It was one way of achieving encapsulation before ES6 introduced proper classes.
const n = naturalNumbers();
n.value
1
n.next().value
2
n.next().next().value
3
Exercise
- Create a function
take(n,seq)
which returns aLazySequence
of the firstn
elements of an infiniteLazySequence
of the sort generated bynaturalNumbers
. After returning then
th element,take
should returnundefined
to indicate the end. - Create
map
,filter
andreduce
functions (similar to those defined onArray.prototype
) for such a sequence and use them along withtake
to create a solution for Project Euler Problem 1 (encountered earlier): sum of first n natural numbers not divisible by 3 or 5. - Make a general purpose infinite sequence initialisation function that creates infinite lazy sequences. It will take as parameter a function to compute the next value from the current value. In other words, it should be a “factory” for functions like
naturalNumbers
. Thus, if we call our functioninitSequence
, theninitSequence(n=>n+1)
will return a function equivalent tonaturalNumbers
. - Use your general purpose sequence generator to generate fibonacci numbers.