Class 6

Algebraic Datatypes

An important and very convenient feature supported by many functional programming languages is the notion of algebraic datatypes (ADTs). ADTs provide type constructors for building user-defined immutable tree-like data structures. They are also known as variant types and (disjoint) sum types. Intuitively, you can think of ADTs as a mix of enumeration types and record types that you'll find in most imperative languages. Together with pattern matching, ADTs enable very powerful programming techniques.

Here is an example of an ADT in OCaml for representing binary search trees:

type tree =
  | Leaf
  | Node of int * tree * tree

This type definition specifies that a value of type tree is either a leaf node, Leaf, or an internal node, Node, which consists of an integer value, and two subtrees (the left and right subtree of the node). Leaf and Node are referred to as the variant constructors of the ADT tree.

The variant constructors Leaf and Node also serve as the value constructors for type tree:

# let empty = Leaf ;;
val empty : tree = Leaf

# let t = Node (3, Node (1, Leaf, Leaf), Node (6, Leaf, Leaf)) ;;
val t : tree = Node (3, Node (1, Leaf, Leaf), Node (6, Leaf, Leaf))

One nice feature of ADTs is that equality = is defined structurally on ADT values, similar to lists and tuples.

Pattern Matching ADTs

Just like lists and tuples, ADT values can be deconstructed using pattern matching. Given an ADT variant C of t1 of some ADT, this variant automatically introduces a constructor pattern C p1 where p1 must be a pattern that matches values of type t1. The constructor pattern then matches a value v if v is of the form C v1 for some value v1 that is matched by p1.

Here is how we can use pattern matching to define a function that checks whether a binary search tree is sorted:

let is_sorted t = 
  let rec check min max t = 
    match t with
    | Leaf -> true
    | Node (x, left, right) ->
      min <= x && x <= max && 
      check min x left &&
      check x max right
  in
  check min_int max_int t

Using the more compact function notation for functions that pattern match on their input values, the nested function check can also be written more compactly like this:

let rec check min max = function
| Leaf -> true
| Node (x, left, right) ->
  min <= x && x <= max && 
  check min x left &&
  check x max right

Polymorphic ADTs

ADT definitions can also be polymorphic. For instance, suppose we want to use a binary search tree data structure to implement maps of integer keys to values, but we want the data structure to be parametric in the type of values stored in the map. This can be done as follows:

type 'a tree =
  | Leaf
  | Node int * 'a * 'a tree * 'a tree

Now each Node value also stores a value of type 'a in addition to the associated int key, and the left and right two subtrees.

# let ti = Node (1, 2, Leaf, Leaf) ;;
val ti : int tree = Node (1, 2, Leaf, Leaf)

# let ts = Node (1, "banana", Leaf, Leaf) ;;
val ts : string tree = Node (1, "string", Leaf, Leaf)

Note that an ADT can also take multiple type parameters. For instance, if we want to abstract from both the type of values as well as the type of keys in our definition of the type tree, this can be done as follows:

type ('a, 'b) tree =
  | Leaf
  | Node 'a * 'b * ('a, 'b) tree * ('a, 'b) tree

The type ('a, 'b) tree now stands for a binary tree where each inner node stores two values, one of type 'a and one of type 'b. Example:

# Node ("banana", 2, Leaf, Leaf) ;;
- : (string, int) tree = Node ("banana", 2, Leaf, Leaf)

The option Type

One of the predefined ADTs of OCaml is the option type:

type 'a option =
  | None
  | Some of 'a

This type is useful for defining partial functions that may not always have a defined return value. For instance, here is how we can implement a function find that finds the value associated with a given key k in a map implemented as a binary search tree, if such an association exists:

let rec find k = function
  | Node (k1, v, left, right) ->
    if k1 = k then Some v
    else if k1 > k then find k left
    else find k right
  | Leaf -> None

The caller of find can now pattern-match on the return value to determine whether the key k was present in the tree and what the associated value v was in that case. The advantage of this implementation is that the static type checker will check for us that the client code will also consider the possibility that the key was not found by find.

Contrast this with the use of null as an indicator of an undefined return value in many other languages. The use of null values often leads to run-time errors because the null case is not handled by the client code and the compiler is unable to detect this at compile-time.

Tuples and Lists as ADTs

Note that both tuples and lists are just special cases of algebraic data types. Having tuples and lists as types that are built into the language is just a matter of convenience. One could just as well implement lists and tuples as user-defined types in a library. Here, is a user-defined version of the type 'a list:

type 'a mylist = 
  | Nil
  | Cons of 'a * 'a mylist

# let reverse xs = 
  let rec reverse_helper rev_xs = function
  | Cons (hd, tl) -> reverse_helper (Cons (hd, rev_xs)) tl
  | Nil -> rev_xs
  in reverse_helper Nil xs 
;;
val reverse: 'a mylist -> 'a mylist

# reverse (Cons (1, Cons (2, Cons (3, Nil)))) ;;
- : int mylist = Cons (3, Cons (2, Cons (1, Nil)))

And here is an ADT that implements pairs of values:

type ('a, 'b) pair =
  | Pair of 'a * 'b

let fst = function
  | Pair (a, _) -> a
  
let snd = function
  | Pair (_, b) -> b

Higher-Order Functions

In functional programming languages, functions are typically treated as "first-class citizens". That is, functions may take other functions as arguments and may again produce functions as return values. A function that takes another function as argument is called a higher-order function.

Higher-order functions provide a powerful mechanism for abstracting over common computation patterns in programs. This mechanism is particularly useful for designing libraries with rich interfaces that support callbacks to client code. We will study these mechanisms using the example of OCaml's list data type.

As a warm-up, suppose that we want to write a function sum_ints that takes the bounds a and b of a (half-open) interval [a,b) of integer numbers and computes the sum of the values in that interval. For example, sum_ints 1 4 should yield 6. The following recursive implementation does what we want:

let rec sum_ints a b =
  if a < b 
  then a + sum_ints (a + 1) b
  else 0

Now, consider the following function sum_squrs that computes the sum of the squares of the numbers in an interval [a,b):

let rec sum_squrs a b =
  if a < b 
  then a * a + sum_squrs (a + 1) b
  else 0

The functions sum_ints and sum_squrs are almost identical. They only differ in the summand that is added in each recursive call. In the case of sum_ints it is a, and in the case of sum_squrs, it is a * a (i.e. a squared). We can write a higher-order function sum that abstracts from these differences. The function sum takes another function f as additional parameter. The function f captures the computation that is performed in the summand:

let rec sum f a b =
  if a < b 
  then f a + sum (a + 1) b
  else 0

let square a = a * a
let sum_squrs a b = sum square a b

Instead of defining the function square explicitly, we can also provide it to sum as an anonymous function given by a lambda abstraction:

let sum_ints a b = sum (fun a -> a) a b
let sum_squrs a b = sum (fun a -> a * a) a b

Curried Functions

Reconsider our definition of sum_ints and sum_squrs in terms of sum:

let sum_ints a b = sum (fun a -> a) a b
let sum_squrs a b = sum (fun a -> a * a) a b

One annoyance with these definitions is that we have to redeclare the parameters a and b which are simply passed to sum. To simplify the definition further, we can take advantage of the fact that sum is a curried function. That is, instead of providing all parameters to sum at once, we simply partially apply sum and provide only the function f at the time when we define sum_ints and sum_squrs. The remaining parameters a and b are then provided when sum_ints respectively sum_squrs are called.

let sum_ints = sum (fun a -> a)
let sum_squrs = sum (fun a -> a * a)

Higher-Order Functions on Lists

A common use case of higher-order functions is to realize callbacks to client code from within library functions. We discuss this scenario using list-manipulating functions.

In the earlier examples we saw that functions operating on lists follow a common pattern: they traverse the list, decomposing it into its elements, and then apply some operation to each of the elements. We can extract these common patterns and implement them in more general higher-order functions that abstract from the specific operation that is performed on each element.

A particularly common operation on lists is to traverse a list and apply some function to each element, obtaining a new list. For example, suppose we have a list of numbers that we want to scale by a given factor to obtain a list of scaled values. The following function implements this operation:

let rec scale factor = function
  | [] -> []
  | x :: xs -> factor * x :: scale factor xs

A similar operation is implemented by the following function, which takes a list of numbers and increments each element to obtain a new list:

let rec incr xs = function
  | [] -> []
  | x :: xs -> 1 + x :: incr xs

The type of operation that is performed by scale and incr is called a map. We can implement the map operation as a higher-order function that abstracts from the concrete operation that is applied to each element in the list:

let rec map op = function
  | [] -> []
  | x :: xs -> op x :: map op xs

The map function transforms the input list xs by applying an operation op to each element in xs. Note that the order of the elements in the input list is preserved.

We can now redefine scale and incr as instances of map:

let scale factor = map (fun x -> factor * x)
let incr = map (fun x -> 1 + x)

Note that for any binary infix operator op, OCaml provides the special syntax (op) to turn the operator op into a curried function. That is, (op) expands to the function fun x y -> x op y. We can use this notation to simplify the definitions of scale and incr even further:

let scale factor = map (( *) factor)
let incr = map ((+) 1)

Please note the space in ( *) between the opening parenthesis and the multiplication operator. This is needed because in OCaml the sequence (* starts a (multi-line) comment.

The List module of OCaml standard library has a predefined function List.map that behaves exactly like our map function:

> List.map ((+) 1) [1; 2; 3]
- : int list = [2; 3; 4]

Folding Lists

We have seen that we can often identify common patterns in functions on data structures and implement them in generic higher-order functions. We can then conveniently reuse these generic functions, reducing the amount of code we have to write. In this section, we will look at the most general patterns for performing operations on lists, namely fold operations.

As a motivating example, consider the following function, which computes the sum of the values stored in a list of integers

let sum_list = function
  | [] -> 0
  | x :: xs -> x + sum_list xs

Consider a list xs of n integer values x1 to xn:

[x1; ...; xn]

Then unrolling the recursion of sum on xs yields the following computation

x1 + (x2 + (... (xn + 0)...))

That is, in the i-th recursive call, we add the current head xi to the sum of the values in the current tail. Here, we consider the sum of an empty list [] to be 0. If we represent this computation as a tree, this tree looks as follows:

      +
     / \
    x1  +
       / \
      x2 ... 
           \
            +
           / \
          xn  0

With this representation, it is easy to see how to generalize from the specific computation performed by the represented expression. That is, in the general case, instead of adding the current head to the sum of the current tail of the list, we apply a generic operation op in each step that combines the current head with the result of the recursive computation on the tail. Moreover, instead of starting with the specific initial value 0 for the empty list, we let the computation take an initial zero value z as auxiliary input. The resulting expanded recursive computation is then represented by the following tree:

      op
     / \
    x1  op
       / \
      x2 ... 
           \
            op
           / \
          xn  z

or using OCaml syntax, by the expression

op x1 (op x2 (... (op xn z) ...))

We refer to this type of computation as a fold of the list because the list is traversed and recursively folded into a single value. Note that the tree is leaning towards the right. We therefore refer to this type of fold operation as a fold-right. That is, the recursive computation is performed in right-to-left order of the values stored in the list.

The following higher-order function implements the fold-right operation:

let rec fold_right op xs z = 
  match xs with
  | [] -> z
  | x :: xs -> op x (fold_right op xs z)

We can now redefine sum_list in terms of fold_right:

let sum_list xs = fold_right (+) xs 0

# sum_list [1; 2; 3] ;;
- : int = 6

Many of the other functions that we have seen before perform fold-right operations on lists. In particular, we can define concat using fold_right as follows:

let concat xs ys = fold_right (fun z zs -> z :: zs) xs ys

or more compactly

let concat = fold_right (fun z zs -> z :: zs)

Also the higher-order function map is actually just a special case of a fold-right:

let map op xs = fold_right (fun x ys -> op x :: ys) xs []

All the above operations on lists have in common that they combine the elements in the input list and the result of the recursive computation in right-to-left order. We can also consider fold operations that perform the computation in left-to-right order:

op (... (op (op z x1) x2) ...) xn

The corresponding computation tree then looks as follows:

        op
       /  \
     ...  xn
     /
    op 
   /  \
  op  x2
 /  \
z   x1

Note that the tree is now leaning towards the left and the elements are combined in left-to-right order. We therefore refer to this type of computation as a fold-left.

The following function implements the fold-left operation on lists:

let rec fold_left op z = function
  | [] -> z
  | x :: xs -> fold_left op (op z x) xs

Since addition is associative and commutative, we can alternatively define sum_list using fold_left instead of fold_right:

let sum_list = fold_left (+) 0

In fact, this definition of sum_list is more efficient than our previous implementations because fold_left is tail-recursive, whereas our implementation of fold_right is not. Note that we were able to replace fold_right by fold_left in the sum_list computation because addition is associative and commutative. Hence, the order in which the elements in the list are processed does not matter. In general, if the operation op is not associative and commutative, then using fold_left and fold_right will yield different results.

For example, we can express reverse in terms of a fold-left as follows:

let reverse xs = fold_left (fun xs x -> x :: xs) [] xs

If we replaced fold_left by fold_right in this definition:

fold_right (fun x xs -> x :: xs) xs []

we would not obtain the correct result. The output list would be equal to the input list.

Since the functions fold_left and fold_right are so useful, they are already predefined in the List module of the standard library.

To get a glimpse of the expressive power of these higher-order functions, consider the following function, which computes the dot product of two vectors v1 and v2 represented as lists of floats.

let dot_prod v1 v2 = 
  List.map2 ( *.) v1 v2 |>
  List.fold_left (+.) 0.0 

Here, |> is reverse function composition, that is f x |> g equivalent to g (f x).

# dot_prod [3.; 2.; 1.] [1.; 2.; 3.]
- : float = 10.

It is instructive to re-implement this code snippet in a language like Java to appreciate how much more concise and comprehensive the implementation with higher-order functions is.

The basic idea of higher-order functions such as map, fold_right, and fold_left generalizes from lists to other data structures. So you will find these kinds of functions in most implementations of common data structures in the standard libraries of functional programming languages.

Practicing the use of fold_left and fold_right

If you have trouble deriving an implementation of a particular function on lists using fold_left/fold_right, here is a trick of how to go about it.

If you want an implementation that uses fold_right, then first write a non-tail-recursive function of this shape:

let rec your_function xs = 
  match xs with
  | [] -> (* xs is empty *)
  value_your_function_returns_for_empty_list
  | hd :: tl -> (* xs is non-empty *)
    (* solve the problem for tl recursively and store result in res *)
    let res = your_function tl in
    (* compute actual result for whole list from hd and res *)
    work_to_do_in_each_step_using_hd_and_res

Then this translates into the following equivalent implementation with fold_right:

let your_function xs = 
  List.fold_right 
    (fun hd res -> work_to_do_in_each_step_using_hd_and_res)
    xs
    value_your_function_returns_for_empty_list

Example:

let rec sum_list xs =
  match xs with
  | [] -> 0
  | hd :: tl -> 
    let res = sum_list tl in
    hd + res

gives:

let sum_list xs = List.fold_right (lambda hd res -> hd + res) xs 0

For using fold_left, you first need a tail-recursive implementation of this shape:

let your_function xs = 
  let rec your_function_helper xs res =
    match xs with
    | [] -> (* list is empty *)
      res
    | hd :: tl -> (* list is non-empty *)
      let res1 = work_to_do_in_each_step_using_hd_and_res in
      (* call the helper recursively on tl with the updated accumulator value res1 *)
      your_function_helper tl res1
  in
  your_function_helper xs value_your_function_returns_for_empty_list

Then this leads to an equivalent implementation with fold_left like this:

let your-function xs = 
  List.fold_left (fun res hd -> work_to_do_in_each_step_using_hd_and_res) 
  value_your_function_returns_for_empty_list 
  xs

Example:

let sum_list xs =
  let rec sum_list_helper xs res =
    match xs with
    | [] -> res
    | hd :: tl -> 
      let res1 = hd + res in
      sum_list_helper tl res1
  in
  sum_list_helper xs 0

gives

let sum_list xs = List.fold_left (fun res hd -> hd + res) 0 xs

So if you have trouble coming up with an implementation that uses fold_left/fold_right, try to follow this recipe. Once you have gone through a few examples like this, it will become natural to use the fold functions directly.