CS 312 Recitation 4:
Lists, Map, Fold and Tail Recursion

Lists in SML

SML has singly-linked lists built-in. The empty list is written as [], nonempty lists are written as[e₁, ..., e_n], where the e_i are all expressions of the same type.

The type of a list is specified as t list where t is the type of the list elements. For example

val il: int list = [1, 2, 3]

The :: operator appends an element onto a list. For instance 1::[2,3] produces the list [1,2,3]. :: is also used extensively in pattern matching, to specify the element at the head of the list and the remainder of the list, as in h::t.

Two lists are appended together using the @ operator, for instance [1,2]@[3] produces the list [1,2,3].

Note that while the :: operator runs in constant time, the @ operator takes time linear in the length of its first argument. Consider an implementation of @, showing how the first list is "copied" in constructing the result.

Map

Recall from lecture that map applies a function to each element of a list, constructing a new list as a result. We can define an uncurried version of map as

fun mapU (f, []) = []
  | mapU (f,h::t) = f(h) :: mapU(f,t)

As with foldl, we can define a curried version, either by currying the uncurried one or directly.

fun curry2 f x y = f(x,y)

fun map' f s = curry2 mapU f s

fun map'' f [] = []
  | map'' f (h::t) = f(h) :: map'' f t

Using map we can define a function to make a copy of a list (with an anonymous function),

fun id s = map' (fn (x) => x) s

The power of fold

Folding is a very powerful operation. We can write many other list functions in terms of fold. In fact map can naturally be defined using foldr,

fun map''' f s = foldr' (fn (x, y) => (f x) :: y) [] s

The accumulator function simply applies f to each element and builds up the resulting list, starting from the empty list.

The entire map-reduce paradigm can thus actually be implemented using foldl and foldr. However, it is often conceptually useful to think of map as producing a list and of reduce as producing a value.

What about using foldl to define map? If we simply replace the foldr call with foldl in the above definition what happens? Contrast linear time mapReverse with quadratic time map using foldl and @.

Another useful variation on mapping is filter, which selects a subset of a list according to some criterion, and could be defined as

fun filter f s = foldr' (fn(x,y) => if f(x) then x::y else y) [] s

The function f takes just one argument, the predicate for determining membership in the resulting list. Now we can easily filter a list of integers for the even ones:

fun evens s = filter (fn(x) => x mod 2 = 0) s

Determining the length of a list is another operation that can easily be defined in terms of folding.

fun length' [] = 0
  | length' (h::t) = 1 + length' t

fun length'' s = foldl' (fn (_, y) => 1 + y) 0 s

What about using foldr for this?

You should try writing some functions using map, foldl and foldr. These primitives as they can be incredibly useful. Even in languages that do not have these operations built-in, they are useful ways of thinking about structuring many computations.

Tail Recursion

A tail recursive function is one where the final computation of the function is a recursive call; there is no remaining work to be done when the recursive call returns with a value. A tail recursive function can be implemented as an iteration by the compiler. That is, a tail recursive function is analogous to a loop in an imperative programming language. The key is that there is no "state" that needs to be saved on each recursive call, because a value is passed unchanged from the final recursive call all the way back to the initial call. Thus no "call stack" is needed as in general (non tail recursive) recursion.

Consider the following function to sum a list of integers:

fun sumIntlist (s:int list):int =
  case s of
    [] => 0
  | h::t => h + (sumIntlist t)

Is this function tail recursive or not? No, because an addition needs to be performed once the recursive sumIntlist call returns. Thus the recursive call is not the last thing to be done.

Here is a tail recursive function that computes the same value. Note that it uses an internally defined "helper" function. This is a common structure to tail recursive programs. The result is built up in an argument to the recursive call, and this result is returned as the value of the last recursive call (and thus all the previous recursive calls as well, because in tail recursion nothing is done to the returned value).

fun sumIntlistIter (s:int list):int =
  let fun helper (s: int list, accum: int): int = 
        case s of 
	  [] => accum
	| h::t => helper(t, h + accum)
    in 
	helper(s, 0)
    end

See how the last operation performed by helper is a recursive call to helper.

Now lets look back at foldl and foldr. Which is tail recursive?

fun foldl' f a [] = a
  | foldl' f a (h::t) = foldl' f (f (h, a)) t

fun foldr' f a [] = a
  | foldr' f a (h::t) = f(h, (foldr' f a t))

For long lists its generally better to use the tail recursive version, but often for lists this ends up reversing the list. A common idiom is thus to explicitly reverse the result.

Function Composition

Recall the compose function that we considered in the last recitation:

fun compose f g x = f(g(x))

This (curried) function is useful for implementing such common idioms. In fact SML has a bulit-in infix operator o that composes two functions. For example,

val concatStringList : string list->string = (foldl (op^) "") o rev

val printInt = print o Int.toString

CS 312 Recitation 4: Lists, Map, Fold and Tail Recursion

Lists in SML

Map

The power of fold

Tail Recursion

Function Composition

CS 312 Recitation 4:
Lists, Map, Fold and Tail Recursion