lists

Complete

Summary

Shortcuts

map(f, null) => null
map(f, list(null)) => list(f(null))

append(null, null) => null
append(list(a), null) => list(a)

enum_list(0, n-1) => list(0,...,n-1) : length = n
enum_list(1, n) => list(1,...,n) : length = n
build_list(f, n) => list(f(0),...f(n-1)) : length = n

for_each(f, xs) // like map but doesn't return a list
filer(pred, xs) // preserves true only
accumulate(f, initial, null) => initial
accumulate(f, initial, list(a)) => f(a, initial)

Concept

A list is either:

null
or a pair, whose tail is a list(ie. tail can be null also)

Think of it as a linked list, where each “node” contains the value(any type) of at the current index, and the pointer to the next node

const x = pair(1, pair(null, pair(2, null)));
// or
const x = list(1, null, 2);

// Box notation: [1, [2, [3, null]]]

List Processing Functions

Function	Action	Visualise	Examples
pair(x, y)	Makes a pair from `x` and `y`.
head(p)	Returns the head (first component) of the pair `p`.		head(pair(a,b)) -> a
tail(p)	Returns the tail (second component) of the pair `p`.		head(pair(a,b)) -> b
is_null(xs)	Returns true if `xs` is the empty list null, and false otherwise.		is_null(null) -> true, is_null(pair(1, null)) -> false
list(x1, x2,…, xn)	Returns a list with n elements. The first element is `x1`, the second `x2`, etc.
length(xs)	Returns the length of the list `xs`.		length(list(1, 2)) -> 2
list_ref(xs, n)	Returns the element of list `xs` at position `n`. (List indexing)		list_ref(list(1, 2), 0) -> 1
append(xs, ys)	Returns a list that results from appending the list `ys` to the list `xs`.		append(list(1, 2), list(3, 4)) -> list(1, 2, 3, 4)
reverse(xs)	Returns new list containing the elements of `xs` in reverse order.		reverse(list(1, 2, 3)) -> list(3, 2, 1)
map(f, xs)	Returns a list where unary function `f` is applied to each element in the list `xs`.	list(f(x1), f(x2), … f(xn))	map(x => x * x, list(1, 2, 3)) -> lisr(1, 4, 9) (Square each Element)
filter(pred, xs)	Returns a list of the elements from `xs` that the unary function pred returns true from.		filter(x => x % 2 === 0, list(1, 2, 3, 4)) -> list(2, 4) (Even Only)
accumulate(f, initial, xs)	Applies the binary function `f` to the nth element and `initial`, then to the (n-1)th element and the previous result, etc, up until the 1st element of `xs`.	f(x1, f(x2, … f(xn, initial) … )	accumulate((h, t) => h + t, 0, list(1, 2, 3)) -> 6 (Sum)

Application

Identifying lists

Example	is_list
null	true
pair(1, null)	true
pair(1, pair(2, null))	true
pair(1, pair(2, 3))	false
pair(pair(1, 2), pair(3, null))	true
pair(null, pair(null, null))	true

Implementing list processing functions

function length(xs) { 
	return is_null(xs)            
		   ? 0             
		   : 1 + length(tail(xs));
}

function append(xs, ys) {     
	return is_null(xs)            
		   ? ys            
		   : pair(head(xs), append2(tail(xs), ys));
}

function reverse(xs) {
	function rev(xs, reversed) {
		return is_null(xs)
			   ? null
			   : rev(tail(xs),
				     pair(head(xs), reversed)));
	}
	return rev(xs, null);
}

Higher order list processing functions

function map(f, xs) {
	return is_null(xs)            
		   ? null            
		   : pair(f(head(xs)), map(f, tail(xs)));
}

function filter(pred, xs) {
	return is_null(xs)
		   ? null            
		   : pred(head(xs))            
		   ? pair(head(xs), filter(pred, tail(xs)))            
		   : filter(pred, tail(xs));
} 

function accumulate(op, initial, xs) {     
	return is_null(xs)            
		   ? initial            
		   : op(head(xs),                  
				accumulate(op, initial, tail(xs)));
}

Bonus

function zip(xs, ys) {
	return is_null(xs) || is_null(ys)
		   ? null
		   : pair(pair(head(xs), head(ys)),
				  zip(tail(xs), tail(ys)));
}