1 Bindings

(require (planet dvanhorn/ralist:3:1))

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. See the benchmark on Contracted vs. Uncontracted bindings for a performance comparison.

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)
> (for/fold ([sum 0]
             [rev-roots empty])
    ([i (in-list (list 1 2 3 4))])
    (values (+ sum i) (cons (sqrt i) rev-roots)))
10
(2 1.7320508075688772 1.4142135623730951 1)

1.4 Iterations and Comprehensions

(for/list ([id sequence-expr] ...) body ...+)

Iterates like for, but that the last expression in the bodys must produce a single value, and the result of the for/list expression is a list of the results in order.

Examples:
> (for/list ([i '(1 2 3)]
             [j "abc"]
             #:when (odd? i)
             [k #(#t #f)])
    (list i j k))
((1 #\a #t) (1 #\a #f) (3 #\c #t) (3 #\c #f))
> (for/list () 'any)
(any)
> (for/list ([i '()])
    (error "doesn't get here"))
'()

1.5 Match patterns

Coming soon.

1.6 Values

empty : empty?

The empty list.

Example:
> 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

(first+rest xs)

→

any/c

list?

xs : (and/c cons? list?)

The anti-cons for lists.

Example:

> (first+rest (list 1 2 3))
1
(2 3)

Failures with contracts:

> (first+rest empty)
contract violation: expected <(and/c ra:cons? ra:list?)>,
given (), which isn't ra:cons?
  contract on first+rest from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:cons? ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:57.2
> (first+rest (cons 1 2))
contract violation: expected <(and/c ra:cons? ra:list?)>,
given (1 . 2), which isn't ra:list?
  contract on first+rest from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:cons? ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:57.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)
contract violation: expected <(and/c ra:cons? ra:list?)>,
given (), which isn't ra:cons?
  contract on first from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:cons? ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:58.2
> (first (cons 'x 'y))
contract violation: expected <(and/c ra:cons? ra:list?)>,
given (x . y), which isn't ra:list?
  contract on first from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:cons? ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:58.2

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)
contract violation: expected <(and/c ra:cons? ra:list?)>,
given (), which isn't ra:cons?
  contract on rest from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:cons? ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:59.2
> (rest (cons 'x 'y))
contract violation: expected <(and/c ra:cons? ra:list?)>,
given (x . y), which isn't ra:list?
  contract on rest from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:cons? ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:59.2

Failures without contracts:

> (rest empty)
ra:rest: expected cons, given: ()
> (rest (cons 'x 'y))
'y

(car+cdr xs)

→

any/c

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)
contract violation: expected <ra:cons?>, given: '()
  contract on car+cdr from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract: (-> ra:cons? any)
        at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:60.2

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)
contract violation: expected <ra:cons?>, given: '()
  contract on car from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract: (-> ra:cons? any)
        at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:61.2

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)
contract violation: expected <ra:cons?>, given: '()
  contract on cdr from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract: (-> ra:cons? any)
        at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:62.2

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)
contract violation: expected <(count>/c 3)>, given: (x y z)
  contract on list-ref from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (->d ((x ...) (y ...)) () any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:90.2
> (list-ref (list* 'x 'y 'z) 2)
contract violation: expected <(count>/c 2)>, given: (x y .
z)
  contract on list-ref from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (->d ((x ...) (y ...)) () any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:90.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)
contract violation: expected <(count>/c 3)>, given: (x y z)
  contract on list-set from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (->d ((x ...) (y ...) (z ...)) () any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:95.2
> (list-set (list* 'x 'y 'z) 2 'c)
contract violation: expected <(count>/c 2)>, given: (x y .
z)
  contract on list-set from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (->d ((x ...) (y ...) (z ...)) () any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:95.2

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))).

(list-ref/set xs i v)

→

any/c

cons?

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.

(list-ref/update xs i f)

→

any/c

cons?

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))
contract violation: expected <(and/c ra:list? (count>/c
1))>, given (a b . c), which isn't ra:list?
  contract on second from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:list? (count>/c 1)) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:72.2
> (second (list 'a))
contract violation: expected <(and/c ra:list? (count>/c
1))>, given (a), which isn't (count>/c 1)
  contract on second from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:list? (count>/c 1)) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:72.2

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.

Example:

> (last (list 1 2 3))
3

Failures with contracts:

> (last empty)
contract violation: expected <(and/c ra:cons? ra:list?)>,
given (), which isn't ra:cons?
  contract on last from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:cons? ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:81.2
> (last (list* 1 2 3))
contract violation: expected <(and/c ra:cons? ra:list?)>,
given (1 2 . 3), which isn't ra:list?
  contract on last from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (-> (and/c ra:cons? ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:81.2

Failures without contracts:

> (last empty)
ra:list-ref: index -1 too large for: ()
> (last (list* 1 2 3))
2

(map f xs ...+) → list?

(or/c (is-true/c (zero? (count xs)))

(arity-includes/c (add1 (mz:length ...))))

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))
contract violation: expected <(or/c (is-true/c (zero?
(count xs))) (arity-includes/c 2))>, given:
#<procedure:add1>
  contract on map from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (->d ((x ...) (y ...)) () #:rest z ... any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:129.2
> (map + (list 1 2 3) (list 4))
contract violation: expected <(and/c ra:list? (count=/c
3))>, given (4), which isn't (count=/c 3)
  contract on map from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (->d ((x ...) (y ...)) () #:rest z ... any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:129.2

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

(or/c (is-true/c (zero? (count xs)))

(arity-includes/c (+ 2 (mz:length ...))))

b : any/c

xs : list?

Like foldr but for random-access lists.

(foldl f a xs ...+) → any

(or/c (is-true/c (zero? (count xs)))

(arity-includes/c (+ 2 (mz:length ...))))

a : any/c

xs : list?

Like foldl but for random-access lists.

(andmap f xs ...+) → any

(or/c (is-true/c (zero? (count xs)))

(arity-includes/c (add1 (mz:length ...))))

xs : (and/c list? (count=/c (count xs)))

Like andmap but for random-access lists.

(ormap f xs ...+) → any

(or/c (is-true/c (zero? (count xs)))

(arity-includes/c (add1 (mz:length ...))))

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

(or/c (is-true/c (zero? n))

(arity-includes/c 1))

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)
contract violation: expected <(or/c (is-true/c (zero? n))
(arity-includes/c 1))>, given: 'not-function
  contract on build-list from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (->d ((x ...) (y ...)) () any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:122.2

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))
contract violation: expected <ra:list?>, given: (1 2 . 3)
  contract on length from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract: (-> ra:list? any)
        at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:69.2

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)
contract violation: expected <ra:list?>, given: 3
  contract on append from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (->* () #:rest (listof ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:70.2
> (append 1 (list 2 3))
contract violation: expected <ra:list?>, given: 1
  contract on append from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract:
    (->* () #:rest (listof ra:list?) any)
  at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:70.2

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))
contract violation: expected <ra:list?>, given: (1 2 . 3)
  contract on reverse from
    (file
    /Users/dvanhorn/Documents/planet/ralist/contract.ss)
  blaming top-level
  contract: (-> ra:list? any)
        at:
/Users/dvanhorn/Documents/planet/ralist/contract.ss:71.2

Failures without contracts:

> (reverse (list* 1 2 3))
kons-tree: expects argument of type <struct:kons>; given 3

← prev up next →

1	Bindings
2	Contract
3	Tests
4	Benchmarks
	Index

1.1	Checked and Unchecked contracts
1.2	Pairs and Lists
1.3	Sequences
1.4	Iterations and Comprehensions
1.5	Match patterns
1.6	Values