Data structures in math

• They are everywhere: tuples, sets, multisets, etc
• Remember the lambda calculus: Simplicity
• What is the simplest data structure possible?
• A pair:
  • created in math using tuple notation (5,4)
  • accessed in math using a pattern: Let p be (x,y), for some x and y ...

Pairs in JediScript

function coordinates_4_3(dimension) {
    if (dimension === "x") {
        return 4;
    } else if (dimension === "y") {
        return 3;
    } else {
        return "error";
    }
}
/* Access: */   ... coordinates_4_3("y") ...

Works, but is it good?

That's quite good for access, but pretty bad for creating the data structure

function coordinates_4_3(dimension) {
    if (dimension === "x") {
        return 4;
    } else {
        return 3;
    }
}

Idea (as usual): Abstraction

function make_coordinates(x, y) {
    return function (dimension) {
               if (dimension === "x") {
                   return x;
               } else {
                   return y;
               }
           };
}

That's much better

Some renaming: Pairs

function make_pair(x, y) {
    return function (index) {
               if (index === "first") {
                   return x;
               } else {
                   return y;
               }
           };
}
function first(pair) {
    return pair("first");
}
function second(pair) {
    return pair("second");
}

Alternative implementation

function make_pair(x, y) {
    return function (select) {
               return select(x,y);
           };
}
function first(pair) {
    return pair(function(x, y) { return x; });
}
function second(pair) {
    return pair(function(x, y) { return y; });
}

Checking is_pair: First attempt

var tag = function() { return true; }
function make_pair(x, y) {
    return function (select) {
               return select(x,y,tag);
           };
}
function first(pair) {
    return pair(function(x, y, z) { return x; });
}
function second(pair) {
    return pair(function(x, y, z) { return y; });
}
function is_pair(pair) {
    return pair(function(x, y, z) { return z === tag; });
}

Checking is_pair: Second attempt

function pair_lib(fun_name) {
    var tag = function() { return true; }
    function make_pair(x, y) { ...tag... };
    function first(pair) { ... };
    function second(pair) { ... };
    function is_pair(pair) { ...tag... };
    return (fun_name === "make_pair") ? make_pair
           : (fun_name === "first") ? first
             : (fun_name === "second") ? second
               : (fun_name === "is_pair") ? is_pair;
}

Case study: Rational numbers

What is a rational number?

A pair, consisting of a denominator and a numerator

function make_rat(n, d) {
    return pair(n, d);
}
function numer(x) {
    return first(x);
}
function denom(x) {
    return second(x);
}

Addition of Rational Numbers

function add_rat(x, y) {
    return make_rat(numer(x) * denom(y) +
                    numer(y) * denom(x),
                    denom(x) * denom(y));
}

Subtraction of Rational Numbers

function sub_rat(x, y) {
    return make_rat(numer(x) * denom(y) -
                    numer(y) * denom(x),
                    denom(x) * denom(y));
}

Multiplication of Rational Numbers

function mul_rat(x, y) {
    return make_rat(numer(x) * numer(y),
                    denom(x) * denom(y));
}

Division of Rational Numbers

function div_rat(x, y) {
    return make_rat(numer(x) * denom(y),
                    denom(x) * numer(y));
}

Equality: First attempt

function equal_rat(x, y) {
    return numer(x) === numer(y) && denom(x) === denom(y);
}

Equality: Second attempt

function equal_rat(x, y) {
    return numer(x) * denom(y) === numer(y) * denom(x);
}

Printing

function rat_to_string(x) {
    return numer(x) + " / " + denom(x);
}

Playing with Rational Numbers

var one_half  = make_rat(1, 2);

var one_third = make_rat(1, 3);

rat_to_string(add_rat(one_half, one_third));

rat_to_string(mul_rat(one_half, one_third));

rat_to_string(add_rat(one_third, one_third));

Returns 2 / 6!

First approach

Reduce when make a rational

function make_rat(n, d) {
    var g = gcd(n, d);
    return pair(n / g, d / g);
}

Second approach

Reduce when accessing

function make_rat(n, d) {
    return pair(n, d);
}
function numer(x) {
    var g = gcd(first(x), second(x));
    return first(x) / g;
}
function denom(x) {
    var g = gcd(first(x), second(x));
    return second(x) / g;
}

Third approach

Reduce when displaying

function make_rat(n, d) { return pair(n, d); }
function numer(x) { return first(x); }
function denom(x) { return second(x); }

function rat_to_string(x) {
    var g = gcd(numer(x), denom(x));
    return (numer(x) / g) + " / " + (denom(x) / g);
}

Summary of Case Study on Rationals

• Pairs can be used to represent rational numbers
• Operations are implemented using constructor and accessor functions
• A library hides the internal representation of the data
• Implementation details remain invisible to the user of the library

Making lists with pairs: Motivation

var highest_denom = pair( pair(50, 20), pair(10, 5));

What if we want the values except the first?

var highest_denom_2 = pair( 20, pair(10, 5));

Removing the next value works differently!

var highest_denom_3n = pair(10, 5));

Idea: Introduce discipline

Make sure that first(pair) always has the data and second(pair) always has the remaining elements:

var highest_denom = pair(50, pair(20, pair(10, 5)));

Special case

What if we are at the end?

var highest_denom = pair(10, 5);

var rest = second(highest_denom);

...gives us a value, not the remaining elements!

Idea: Introduce a base case: A value that represents the empty list.

How to represent the empty list

It doesn't really matter!

One straightforward idea is to use another "dummy" function

function empty_list() { return true; }

highest_denom using the empty list

var highest_denom = 
pair(50, pair(20, pair(10, pair(5, empty_list))));

highest_denom using the empty list (in style)

var highest_denom = pair(50, 
                         pair(20, 
                              pair(10, 
                                   pair(5, 
                                        empty_list))));

Lists in JediScript: Naming

• first renamed to head
• second renamed to tail

Think of snakes

Special symbol for empty_list: []

List Discipline in JediScript

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

highest_denom using JediScript

var highest_denom = pair(50, 
                         pair(20, 
                              pair(10, 
                                   pair(5, []);

...head(highest_denom)...

...head(tail(tail(highest_denom)))..

JediScript's List Library list.js

• pair(x, y): returns pair made of x and y
• is_pair(p): returns true iff p is a pair
• []: represents the empty list
• is_empty_list(xs): returns true iff xs is the empty list
• head(xs): returns the head (first component) of list xs
• tail(xs): returns the tail (second component) of list xs
• list(x1,...,xn): returns list whose first element is x1, whose second element is x2 etc and whose last element is xn

Representing pairs with box-and-pointer diagrams

• pair(1, 2) is represented by a box that contains the two values
• pair(1, pair(3, 4)) is drawn using a pointer to a second box

Representing pairs in the Web Console

The truth is: We use zero-element arrays for the empty list and two-element arrays for pairs.

This leads to a very nice display of lists in the Web Console.

Catching errors

The three functions that query the structure of lists have expectations for their arguments:

• is_empty_list(xs): expects an empty list or a pair as xs
• head(xs): expects a pair as xs
• tail(xs): expects a pair as xs

Otherwise: Something "terrible" happens!

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 in an 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);
}

Summary

• JediScript update
• Equality
• Data, an old hat
• Case study: Rational numbers
• Lists