1 Bindings
| (require (planet dvanhorn/ralist:1:12)) |
1.1 Checked and Unchecked contracts
This library provides bindings for list operations in two forms: the first assumes all contracts are met, the second checks.
The observable differences are in their failure modes – what happens when the contract is not met – and execution times. While the unchecked operations are free to fail in any way (which includes not failing at all in some cases), if the user of this library violates the contract, the checked bindings will fail with a contract violation exception with appropriate blame. On the other hand, the unchecked bindings avoid any overhead associated with the contract check, which can be significant.
The checked bindings are designed to be complete in their checking of contract properties, regardless of computational expense. The unchecked bindings are designed to be fast and to give reasonable error messages to any violation that can easily be detected. Given inputs that satisfy the contract, both versions produced equivalent results.
The main module provides bindings for list operations with unchecked contracts. Where appropriate, examples are given demonstrating the differences in failure modes for the checked and unchecked bindings.
1.2 Pairs and Lists
A pair combines exactly two values. The first value is accessed with the car procedure, and the second value is accessed with the cdr procedure. Pairs are not mutable.
A list is recursively defined: it is either the constant empty, or it is a pair whose second value is a list.
A list can be used as a single-valued sequence (see Sequences). The elements of the list serve as elements of the sequence. See also in-list.
1.3 Sequences
Random-access lists implement the sequence interface, so (list? x) implies (sequence? x), and elements of a list may be extracted with any of the for syntactic forms.
| (in-list xs) → list? |
| xs : list? |
Returns a sequence equivalent to xs. Since lists are sequences, this is a list identity function, but an in-list application can provide better performance when it appears directly in a for clause.
Examples: | ||||
| > (in-list (list 1 2 3)) | ||||
(1 2 3) | ||||
| ||||
10 | ||||
(2 1.7320508075688772 1.4142135623730951 1) |
1.4 Match patterns
Coming soon.
1.5 Values
| empty : empty? |
The empty list.
Examples: |
| > empty |
() |
| (cons x y) → cons? |
| x : any/c |
| y : any/c |
Cons x onto y. When (list? y), (cons x y) constructs a list.
Examples: |
| > (cons 'x empty) |
(x) |
| > (cons 'x (cons 'y empty)) |
(x y) |
| > (cons 'x 'y) |
(x . y) |
| (list x ) → list? |
| x : any/c |
Returns a list containing the given xs as its elements.
Examples: |
| > (list) |
() |
| > (list 'x 'y 'z) |
(x y z) |
| (list* x tail) → any |
| x : any/c |
| tail : any/c |
Returns a list containing the given xs as its elements and tail as its tail. When (list? tail), (list* x ... tail) constructs a list.
Examples: |
| > (list* empty) |
() |
| > (list* 'x 'y (list 'p 'q)) |
(x y p q) |
| > (list* 1 2 3) |
(1 2 . 3) |
| > (list* 1) |
1 |
| (empty? x) → boolean? |
| x : any/c |
Is x the empty list?
Examples: |
| > (empty? empty) |
#t |
| > (empty? (list)) |
#t |
| > (empty? (cons 'x empty)) |
#f |
| > (empty? 'x) |
#f |
| (cons? x) → boolean? |
| x : any/c |
Is x a pair?
Examples: |
| > (cons? empty) |
#f |
| > (cons? (list)) |
#f |
| > (cons? (cons 'x empty)) |
#t |
| > (cons? 'x) |
#f |
| (list? x) → boolean? |
| x : any/c |
Is x a list? Takes O((log2 (count x))).
Examples: |
| > (list? empty) |
#t |
| > (list? (list)) |
#t |
| > (list? (cons 'x empty)) |
#t |
| > (list? 'x) |
#f |
| ||||||||
| xs : (and/c cons? list?) |
The anti-cons for lists.
Examples: |
| > (first+rest (list 1 2 3)) |
1 |
(2 3) |
Failures with contracts: | ||
| > (first+rest empty) | ||
| ||
| ||
ra:list?)>, given: () | ||
| > (first+rest (cons 1 2)) | ||
| ||
| ||
ra:list?)>, given: (1 . 2) |
Failures without contracts: |
| > (first+rest empty) |
ra:first+rest: expected cons, given: () |
| > (first+rest (cons 1 2)) |
1 |
2 |
| (first xs) → any |
| xs : (and/c cons? list?) |
Returns the first element of the list xs.
Examples: |
| > (first (cons 'x empty)) |
x |
| > (first (list 1 2 3)) |
1 |
Failures with contracts: | ||
| > (first empty) | ||
| ||
| ||
ra:list?)>, given: () | ||
| > (first (cons 'x 'y)) | ||
| ||
| ||
ra:list?)>, given: (x . y) |
Failures without contracts: |
| > (first empty) |
ra:first: expected cons, given: () |
| > (first (cons 'x 'y)) |
x |
| (rest xs) → list? |
| xs : (and/c cons? list?) |
Returns the rest of the element of the list xs.
Examples: |
| > (rest (cons 'x empty)) |
() |
| > (rest (list 1 2 3)) |
(2 3) |
Failures with contracts: | ||
| > (rest empty) | ||
| ||
| ||
ra:list?)>, given: () | ||
| > (rest (cons 'x 'y)) | ||
| ||
| ||
ra:list?)>, given: (x . y) |
Failures without contracts: |
| > (rest empty) |
ra:rest: expected cons, given: () |
| > (rest (cons 'x 'y)) |
y |
| ||||||||
| xs : cons? |
The anti-cons for pairs.
Examples: |
| > (car+cdr (cons 1 2)) |
1 |
2 |
| > (car+cdr (list 1 2 3)) |
1 |
(2 3) |
Failures with contracts: |
| > (car+cdr empty) |
top-level broke the contract (-> ra:cons? any) on car+cdr; |
expected <ra:cons?>, given: () |
Failures without contracts: |
| > (car+cdr empty) |
ra:car+cdr: expected cons, given: () |
| (car p) → any |
| p : cons? |
Returns the first component of the pair p.
Examples: |
| > (car (cons 1 2)) |
1 |
| > (car (list 1 2 3)) |
1 |
Failures with contracts: |
| > (car empty) |
top-level broke the contract (-> ra:cons? any) on car; |
expected <ra:cons?>, given: () |
Failures without contracts: |
| > (car empty) |
ra:car: expected cons, given: () |
| (cdr p) → any |
| p : cons? |
Returns second component of the pair p.
Examples: |
| > (cdr (cons 1 2)) |
2 |
| > (cdr (list 1 2 3)) |
(2 3) |
Failures with contracts: |
| > (cdr empty) |
top-level broke the contract (-> ra:cons? any) on cdr; |
expected <ra:cons?>, given: () |
Failures without contracts: |
| > (cdr empty) |
ra:cdr: expected cons, given: () |
| (list-ref xs i) → any/c |
| xs : (count>/c i) |
| i : natural-number/c |
Returns the element of xs at position i. This operation runs in O((min i (log2 (count xs)))).
Examples: |
| > (list-ref (list 'x 'y 'z) 0) |
x |
| > (list-ref (list 'x 'y 'z) 1) |
y |
| > (list-ref (list 'x 'y 'z) 2) |
z |
| > (list-ref (list* 'x 'y 'z) 0) |
x |
Failures with contracts: | ||
| > (list-ref (list 'x 'y 'z) 3) | ||
| ||
| ||
| > (list-ref (list* 'x 'y 'z) 2) | ||
| ||
|
Failures without contracts: |
| > (list-ref (list 'x 'y 'z) 3) |
ra:list-ref: index 3 too large for: (x y z) |
| > (list-ref (list* 'x 'y 'z) 2) |
ra:list-ref: index 2 too large for: (x y . z) |
| (list-set xs i x) → cons? |
| xs : (count>/c i) |
| i : natural-number/c |
| x : any/c |
Returns a chain of pairs identical to xs, except x is the ith element. This operation runs in O((min i (log2 (count xs)))).
Examples: |
| > (list-set (list 'x 'y 'z) 0 'a) |
(a y z) |
| > (list-set (list 'x 'y 'z) 1 'b) |
(x b z) |
| > (list-set (list 'x 'y 'z) 2 'c) |
(x y c) |
| > (list-set (list* 'x 'y 'z) 0 'a) |
(a y . z) |
Failures with contracts: | ||
| > (list-set (list 'x 'y 'z) 3 'd) | ||
| ||
| ||
(x y z) | ||
| > (list-set (list* 'x 'y 'z) 2 'c) | ||
| ||
| ||
(x y . z) |
Failures without contracts: |
| > (list-set (list 'x 'y 'z) 3 'd) |
ra:list-ref/update: index 3 too large for: (x y z) |
| > (list-set (list* 'x 'y 'z) 2 'c) |
ra:list-ref/update: index 2 too large for: (x y . z) |
| (list-update xs i f) → cons? |
| xs : (count>/c i) |
| i : natural-number/c |
| f : (arity-includes/c 1) |
Returns (list-set xs i (f (list-ref xs i))).
| ||||||||
| xs : (count>/c i) | ||||||||
| i : natural-number/c | ||||||||
| v : any/c |
Returns (values (list-ref xs i) (list-set xs i v)), but is more efficient.
| ||||||||
| xs : (count>/c i) | ||||||||
| i : natural-number/c | ||||||||
| f : (arity-includes/c 1) |
Returns (values (list-ref xs i) (list-set xs i (f (list-ref xs i)))), but is more efficient.
| (second xs) → any/c |
| xs : (and/c list? (count>/c 1)) |
Returns the second element of the list.
| (third xs) → any/c |
| xs : (and/c list? (count>/c 2)) |
Returns the third element of the list.
| (fourth xs) → any/c |
| xs : (and/c list? (count>/c 3)) |
Returns the fourth element of the list.
| (fifth xs) → any/c |
| xs : (and/c list? (count>/c 4)) |
Returns the fifth element of the list.
| (sixth xs) → any/c |
| xs : (and/c list? (count>/c 5)) |
Returns the sixth element of the list.
| (seventh xs) → any/c |
| xs : (and/c list? (count>/c 6)) |
Returns the seventh element of the list.
| (eighth xs) → any/c |
| xs : (and/c list? (count>/c 7)) |
Returns the eighth element of the list.
| (ninth xs) → any/c |
| xs : (and/c list? (count>/c 8)) |
Returns the ninth element of the list.
| (tenth xs) → any/c |
| xs : (and/c list? (count>/c 9)) |
Returns the tenth element of the list.
Examples: |
| > (second (list 'a 'b)) |
b |
| > (third (list 'a 'b 'c)) |
c |
| > (fourth (list 'a 'b 'c 'd)) |
d |
| > (fifth (list 'a 'b 'c 'd 'e)) |
e |
| > (sixth (list 'a 'b 'c 'd 'e 'f)) |
f |
| > (seventh (list 'a 'b 'c 'd 'e 'f 'g)) |
g |
| > (eighth (list 'a 'b 'c 'd 'e 'f 'g 'h)) |
h |
| > (ninth (list 'a 'b 'c 'd 'e 'f 'g 'h 'i)) |
i |
| > (tenth (list 'a 'b 'c 'd 'e 'f 'g 'h 'i 'j)) |
j |
Failures with contracts: | ||
| > (second (list* 'a 'b 'c)) | ||
| ||
| ||
(count>/c 1))>, given: (a b . c) | ||
| > (second (list 'a)) | ||
| ||
| ||
(count>/c 1))>, given: (a) |
Failures without contracts: |
| > (second (list* 'a 'b 'c)) |
b |
| > (second (list 'a)) |
ra:list-ref: index 1 too large for: (a) |
| (last xs) → any/c |
| xs : (and/c cons? list?) |
Returns the last element of the list.
Examples: |
| > (last (list 1 2 3)) |
3 |
Failures with contracts: | ||
| > (last empty) | ||
| ||
| ||
ra:list?)>, given: () | ||
| > (last (list* 1 2 3)) | ||
| ||
| ||
ra:list?)>, given: (1 2 . 3) |
Failures without contracts: |
| > (last empty) |
ra:list-ref: index -1 too large for: () |
| > (last (list* 1 2 3)) |
2 |
| (map f xs ) → list? | ||||||||
| ||||||||
| xs : (and/c list? (count=/c (count xs))) |
Applies f to each element of xss from the first element to the last. The f argument must accept the same number of arguments as the number of supplied xss. The result is a list containing each result of f in order.
Examples: |
| > (map 0 empty) |
() |
| > (map add1 empty) |
() |
| > (map add1 (list 0 1 2)) |
(1 2 3) |
| > (map (lambda (x y) (+ x y)) (list 1 2 3) (list 4 5 6)) |
(5 7 9) |
Failures with contracts: | ||
| > (map add1 (list 1 2 3) (list 4 5 6)) | ||
| ||
| ||
(zero? (count xs))) (arity-includes/c 2))>, given: | ||
#<procedure:add1> | ||
| > (map + (list 1 2 3) (list 4)) | ||
| ||
| ||
ra:list? (count=/c 3)))>, given: ((4)) |
Failures without contracts: |
| > (map add1 (list 1 2 3) (list 4 5 6)) |
add1: expects 1 argument, given 2: 1 4 |
| > (map + (list 1 2 3) (list 4)) |
+: expects type <number> as 1st argument, given: #s(node 1 |
2 3); other arguments were: 4 |
| (foldr f b xs ) → any | ||||||||
| ||||||||
| b : any/c | ||||||||
| xs : list? |
Like foldr but for random-access lists.
| (foldl f a xs ) → any | ||||||||
| ||||||||
| a : any/c | ||||||||
| xs : list? |
Like foldl but for random-access lists.
| (andmap f xs ) → any | ||||||||
| ||||||||
| xs : (and/c list? (count=/c (count xs))) |
Like andmap but for random-access lists.
| (ormap f xs ) → any | ||||||||
| ||||||||
| xs : (and/c list? (count=/c (count xs))) |
Like ormap but for random-access lists.
| (make-list n x) → list? |
| n : natural-number/c |
| x : any/c |
Returns a list with n elements, all of which are x. Equivalent to (build-list n (lambda (i) x)).
Examples: |
| > (make-list 0 'x) |
() |
| > (make-list 5 'x) |
(x x x x x) |
| (build-list n f) → list? | ||||||||
| n : natural-number/c | ||||||||
|
Creates a list of n elemenents by applying f to the integers from 0 to (sub1 n).
Examples: |
| > (build-list 0 'not-function) |
() |
| > (build-list 0 (lambda (i) i)) |
() |
| > (build-list 10 values) |
(0 1 2 3 4 5 6 7 8 9) |
| > (build-list 5 (lambda (x) (* x x))) |
(0 1 4 9 16) |
Failures with contracts: | ||
| > (build-list 5 'not-function) | ||
| ||
| ||
(arity-includes/c 1))>, given: not-function |
Failures without contracts: |
| > (build-list 5 'not-function) |
procedure application: expected procedure, given: |
not-function; arguments were: 2 |
| (length xs) → natural-number/c |
| xs : list? |
Returns the length of the list. This operation runs in O((log2 (length xs))).
Examples: |
| > (length empty) |
0 |
| > (length (list 1 2 3)) |
3 |
Failures with contracts: |
| > (length (list* 1 2 3)) |
top-level broke the contract (-> ra:list? any) on length; |
expected <ra:list?>, given: (1 2 . 3) |
Failures without contracts: |
| > (length (list* 1 2 3)) |
2 |
| (count xs) → natural-number/c |
| xs : any/c |
Returns the number of cons chained together to form xs. O((log2 (count xs))).
Examples: |
| > (count empty) |
0 |
| > (count 'x) |
0 |
| > (count (list 1 2 3)) |
3 |
| > (count (list* 1 2 3)) |
2 |
| (list-tail xs i) → list? |
| xs : list? |
| i : natural-number/c |
Returns the list after the first i elements of xs. This operation, like its pair counterpart runs in O(i).
| (append xs ) → list? |
| xs : list? |
| (append xs v) → any/c |
| xs : list? |
| v : any/c |
Returns a list with all the elements of the given lists in order.
Examples: |
| > (append) |
() |
| > (append empty empty empty) |
() |
| > (append (list 1 2 3) (list 4) (list 5 6)) |
(1 2 3 4 5 6) |
| > (append (list 1 2 3) 4) |
(1 2 3 . 4) |
| > (append 5) |
5 |
Failures with contracts: | ||
| > (append 3 5) | ||
| ||
| ||
given: (3 5) | ||
| > (append 1 (list 2 3)) | ||
| ||
| ||
given: (1 (2 3)) |
Failures without contracts: |
| > (append 3 5) |
ra:first+rest: expected cons, given: 3 |
| > (append 1 (list 2 3)) |
ra:first+rest: expected cons, given: 1 |
| (reverse xs) → list? |
| xs : list? |
Returns a list with all the elements of xs in reverse order.
Examples: |
| > (reverse empty) |
() |
| > (reverse (list 1 2 3)) |
(3 2 1) |
Failures with contracts: |
| > (reverse (list* 1 2 3)) |
top-level broke the contract (-> ra:list? any) on reverse; |
expected <ra:list?>, given: (1 2 . 3) |
Failures without contracts: |
| > (reverse (list* 1 2 3)) |
kons-tree: expects argument of type <struct:kons>; given 3 |