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 imperativeImperative programs are a sequence of statements that change a programs state. This is probably the dominant paradigm for programming languages today. Languages from Assembler to Python are built around this concept and most modern languages still allow you to program in this style. 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 functionalFunctional languages are built around the concept of composable functions. Such languages support higher order functions which can take other functions as arguments or return new functions as their result, following the rules of the Lambda Calculus. 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 interfaceA TypeScript construct that defines the shape of an object, specifying the types of its properties and methods. 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 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.

Solutions

A live version of the solutions can be accessed here. However, let’s walk through it. Consider the definition of a LazySequence

interface LazySequence<T> {
   value: T;
   next():LazySequence<T>;
}

The take function creates a LazySequence of the first n elements by returning the current value and recursively calling itself with n decremented and the next element of the sequence until n reaches 0, at which point it returns undefined to signify the end.

function take<T>(n: number, seq: LazySequence<T>): LazySequence<T> | undefined {
  if (n) {
    return {
      value: seq.value,
      next: () => take(n - 1, seq.next()),
    } as LazySequence<T>;
  }
  return undefined;
}

We can define the three map/filter/reduce functions with similar logic.

function map<T, U>(
  f: (value: T) => U,
  seq: LazySequence<T> | undefined
): LazySequence<U> | undefined {
  if (!seq) {
    return undefined; // If the sequence is undefined, return undefined
  }
  return {
    value: f(seq.value), // Apply the function to the current value
    next: () => map(f, seq.next()), // Recursively apply the function to the next elements
  };
}

function filter<T>(
  predicate: (value: T) => boolean,
  seq: LazySequence<T> | undefined
): LazySequence<T> | undefined {
  if (!seq) {
    return undefined; // If the sequence is undefined, return undefined
  }
  if (predicate(seq.value)) {
    return {
      value: seq.value, // If the current value matches the predicate, include it
      next: () => filter(predicate, seq.next()), // Recursively filter the next elements
    };
  } else {
    return filter(predicate, seq.next()); // Skip the current value and filter the next elements
  }
}

function reduce<T, U>(
  f: (accumulator: U, value: T) => U,
  seq: LazySequence<T> | undefined,
  initialValue: U
): U {
  if (!seq) {
    return initialValue; // If the sequence is undefined, return the initial value
  }
  // Recursively apply the accumulator function to the next elements and the current value
  return reduce(f, seq.next(), f(initialValue, seq.value));
}

Using this code, we can solve the first euler problem

function sumOfFirstNNaturalsNotDivisibleBy3Or5(n: number): number {
  const naturals = naturalNumbers(); // Generate the natural numbers sequence
  // Take the first n elements and filter out those not divisible by 3 or 5
  const filtered = filter(
    (x) => x % 3 === 0 || x % 5 === 0,
    take(n - 1, naturals)
  );

  // Sum the remaining elements using reduce
  return reduce((acc, x) => acc + x, filtered, 0);
}

// Example usage
console.log(sumOfFirstNNaturalsNotDivisibleBy3Or5(1000));

233168

Glossary

Eager Evaluation: A strategy where expressions are evaluated immediately as they are bound to variables.

IIFE (Immediately Invoked Function Expression): A JavaScript function that runs as soon as it is defined, used to create local scopes and encapsulate code.

Lazy Evaluation: A strategy where expressions are not evaluated until their values are needed, allowing for the creation of infinite sequences and delayed computations.