lists

Complete

lang
/
js

Summary

Concept of linked lists, data & ptr to next node

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

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

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

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
Can be created using the list function
list(1, 2, 3) is the same as

Application

List Processing Summary 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)
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)));
}