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 a LazySequence of the first n elements of an infinite LazySequence of the sort generated by naturalNumbers. After returning the nth element, take should return undefined to indicate the end.
  • Create map, filter and reduce functions (similar to those defined on Array.prototype) for such a sequence and use them along with take 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 function initSequence, then initSequence(n=>n+1) will return a function equivalent to naturalNumbers.
  • Use your general purpose sequence generator to generate fibonacci numbers.