CS1101S

Lecture 9: List and Tree Processing

12 September 2012

Martin Henz

Overview

• Basic functions
  • append
  • reverse
  • map
• Trees
• Equality
• Signal processing metaphor

Reading: SICP 2.1, 2.2.1, 2.2.2, 2.2.3

Review: Pairs

var p = pair(1, 2);

forms a pair with two components

head(p)

accesses the first component

tail(p)

accesses the second component

Review: List Discipline

pair(1,
     pair(2,
          pair(3,
               pair(4, []))))

A list is either the empty list [] or a pair whose tail is a list.

Recap: Shortcut for writing lists

pair(1,
     pair(2,
          pair(3,
               pair(4, []))))

can be written as:

list(1, 2, 3, 4)

and is printed as:

[1,[2,[3,[4,[]]]]]

Recap: Test for Empty List

is_empty_list([])

returns true

is_empty_list( list(1,2,3) )

returns false

is_empty_list enforces (something slightly weaker than) list discipline. If the argument is not the empty list or a pair, the computation stops and an error is displayed.

Computing the length of a list

The length of the empty list is 0, and the length of a non-empty list is one more than the length of its tail.

function length(xs) {
    if (is_empty_list(xs)) {
	return 0;
    } else {
	return 1 + length(tail(xs));
    }
}

Can we do this iteratively?

function length_iter(xs) {
    function len(xs, counted_so_far) {
        if (is_empty_list(xs)) {
            return counted_so_far;
        } else {
            return len(tail(xs), counted_so_far + 1);
        }
    }
    return len(xs, 0);
}

Appending (merging) two lists

Append list(1,3,5) and list(2,4) results in list(1,3,5,2,4)

How do we do it? What if the first list is empty? What if not?

Strategy for append(list1, list2)

If list1 is empty, return list2.

Otherwise, wishful thinking!

Append the tail of list1 to list2

Form a pair of the head of list1 and the result.

Appending lists

function append(xs, ys) {
    if (is_empty_list(xs)) {
	return ys;
    } else {
	return pair(head(xs),
		    append(tail(xs), ys));
    }
}

Append is not pair

var list1 = pair( list(1,2,3), list(4,5,6) );

var list2 = append( list(1,2,3), list(4,5,6) );

Reversing a list: First attempt

function reverse(lst) {
    if (is_empty_list(lst)) {
        return [];
    } else {
        return pair(reverse(tail(lst)), 
                    head(lst));
    }
}

What's wrong?

Reversing a list: Correct but naive

function reverse(lst) {
    if (is_empty_list(lst)) {
        return [];
    } else {
        return append(reverse(tail(lst)), 
                      list(head(lst)));
    }
}

Correct, but what about runtime?

Reversing a list efficiently

function reverse(xs) {
    function rev(original, reversed) {
	if (is_empty_list(original)) {
	    return reversed;
	} else {
	    return rev(tail(original), 
		       pair(head(original), 
                            reversed));
	}
    }
    return rev(xs,[]);
}

Order of growth? Time? Space? Scheme? JavaScript?

Scaling a list

Let us scale all elements of a list by a factor f.

function scale_list(items, factor) {
    if (is_empty_list(items)) {
        return [];
    } else {
        return pair(factor * head(items),
                    scale_list(tail(items), 
                               factor)
                   );
    }
}

Squaring a list

Let us square all elements of a list.

function square_list(items) {
    if (is_empty_list(items)) {
        return [];
    } else {
        return pair(square(head(items)),
                    square_list(tail(items))
                   );
    }
}

Abstraction: Map

Mapping: Applying a given function f element-wise to a given list.

The result is a list with same elements, except that f is applied to each of them.

map( square, list(1,2,3) );

Abstraction: Map (second example)

Mapping: Applying a given function f element-wise to a given list.

The result is a list with same elements, except that f is applied to each of them.

function scale_list(items, factor) {
    return map(function(x) { return factor * x; }, 
               items);
}

Definition of map

function map(fun, items) {
    if (is_empty_list(items)) {
        return [];
    } else {
        return pair(fun(head(items)),
                    map(fun, tail(items)));
    }
}

Overview

• Basic functions
  • append
  • reverse
  • map
• Trees
• Equality
• Signal processing metaphor

Reading: SICP 2.1, 2.2.1, 2.2.2, 2.2.3

Trees

A tree is a list whose elements are data items, or trees.

Consider:

var tree = pair(list(1,2), list(3, 4));

What is:

length(tree)?

Counting Leaves

Question: What is the number of data items in a tree, where lists don't count as data items?

Consider:

var tree = pair(list(1,2), list(3, 4));

What is:

count_leaves( tree )?

Counting Leaves: Idea

What is the base case?

Base case: The tree is a data item (not a list)

In that case we return 1

If the tree is a list, we must add the number of leaves of the list elements, using recursion

Counting Leaves

function count_leaves(tree) {
    function count_leaves_in_list(xs) {
        return (is_empty_list(xs)) ? 0
               : count_leaves(head(xs)) 
                 + count_leaves_in_list(tail(xs));
    }
    if (is_list(tree)) {
        return count_leaves_in_list(tree);
    } else {
        return 1;
    }
}

Scaling trees

Example: scale each leaf by a factor 10

var my_tree = list(1, list(2, list(3,4), 5), list(6, 7));

scale_tree(my_tree, 10)

should have the same result as:

list(10, list(20, list(30,40), 50), list(60, 70));

Scaling trees: Idea

Recap: Trees are lists of {trees or data items}

Idea: Map over the tree. If element is a data item, scale it. If not: recurse

Scaling trees: Implementation

function scale_tree(tree, factor) {
    return map(function(sub_tree) {
                   return (is_number(sub_tree)) 
                          ? factor * sub_tree
                          : scale_tree(sub_tree,
                                       factor);
               },
               tree);
}

Scaling trees: More General Implementation

function scale_tree(tree, factor) {
    return map(function(sub_tree) {
                   return (! is_list(sub_tree)) 
                          ? factor * sub_tree
                          : scale_tree(sub_tree,
                                       factor);
               },
               tree);
}

Abstraction: Mapping over trees

function map_tree(tree, f) {
    return map(function(sub_tree) {
                   return (! is_list(sub_tree)) 
                          ? f(sub_tree)
                          : map_tree(sub_tree, f);
               },
               tree);
}

Overview

• Basic functions
  • append
  • reverse
  • map
• Trees
• Equality
• Signal processing metaphor

Reading: SICP 2.1, 2.2.1, 2.2.2, 2.2.3

Equality in JediScript: ===

• Boolean values: super easy
• Strings: straightforward
• Numbers: Watch out:

  var big = Math.pow(2, 53);
  big === big + 1;
  

• Functions: All function values are created different.

Equality in JediScript: ===

• ...
• Functions: All function values are created different.
• All [] and pairs are created different.

Structural Equality: equal in JediScript

Idea: Check if two items have the same structure and corresponding leaves are ===

equal( list( list(1,2,3), list(4,5)),
       list( list(1,2,3), list(4,5)) )    => true

equal( list( list(1,2,3), list(4,5)),
       list( list(1,2,8), list(4,5)) )    => false

Exercise: Make a copy of a list

Idea: Copies of lists should always be equal, but never ===

function copy(xs) {
    return map(function(x) { return x; }, xs);
}

Overview

• Basic functions
  • append
  • reverse
  • map
• Trees
• Equality
• Signal processing metaphor

Reading: SICP 2.1, 2.2.1, 2.2.2, 2.2.3

Listening to Music

• Signal goes through stages of processing
• Plug-and-play: easy to add and replace components

Signal processing view of lists

• Producer: creates a list
• Filters: remove elements
• Mappers: modify elements
• Accumulator: consumes list and generates result

Producers: list

• list is the only function in JediScript with variable number of arguments
• Convenient way to make a list, using its extensional definition

Producers: build_list

• build_list(n,fun): Makes a list by applying fun to 0 ... n - 1
• Example:

  var squares = build_list(10,square)
  

Filters

• filter(pred, xs): Returns sublist of xs of elements x for which pred(x) returns true
• Example:

  filter(is_even, squares)
  

Mappers: Reviewing map

• map(fun, xs): result is a list with same elements as xs, except that fun is applied to each of them.
• Example:

  map( square, list(1,2,3) );
  

Accumulators

• accumulate: Works like fold but on lists
• accumulate(op, initial, xs): applies op successively to the elements of xs, starting with initial
• Example:

  accumulate(plus, 0, squares)
  

Example of Signal Processing

var squares = build_list(10, square);
var even_squares = filter(is_even, squares);
var half_even_squares 
= map(function(x) { return x / 2; },
      even_squares);
var result = accumulate(plus, 0, half_even_squares);

Benefits of Signal Processing

• Modularity: components are independent of each other, can be freely combined and re-used
• Clarity: separates data from processes
• Flexibility: components can be added and removed at will

Summary

• Basic functions
  • append
  • reverse
  • map
• Trees
• Equality
• Signal processing metaphor

Reading: SICP 2.1, 2.2.1, 2.2.2, 2.2.3