RaList: Purely Functional Random-Access Lists

7.7

top ← prev up next →

RaList: Purely Functional Random-Access Lists

Random-access lists are a purely functional data structure for representing lists of values. A random-access list may act as a drop in replacement for the usual sequential list data structure (cons?, cons, car, cdr), which additionally supports fast index-based addressing and updating (list-ref, list-set).

This document outlines the API for the random-access list library. This implementation is based on Okasaki, FPCA ’95.

1 Random-Access Lists

(require data/ralist)

package: ralist

In addition to data/ralist, there is a data/ralist/contract module that provides the same bindings but with checked contracts. The only difference is performance and error checking. See Checked and Unchecked contracts for details.

Random-access lists look and behave much like their sequential access counterparts. The main difference is that list-ref and list-set take time that is logarithmic, rather than linear, in the size of the list:

> (list 0 1 2 3)
(0 1 2 3)
> (cons 1 2)
(1 . 2)
> (car (cons 1 2))
1
> (cdr (cons 1 2))
2
> (map (lambda (i) (/ 1 i))
(list 1 2 3))
(1 1/2 1/3)
> (list-ref (list 'x 'y 'z) 2)
'z
> (list-set (list 'x 'y 'z) 2 'q)
(x y q)

This can have a big impact on efficiency of accessing elements in a list by their index. For example, getting the last element of a sequential list takes time proportional to the length of the list, but can be done much faster with random-access lists:

> (module m racket/base
    (require data/ralist)
    (define ls (build-list 100000 values))
    (time (for ([i 1000]) (last ls))))
> (require 'm)
cpu time: 1 real time: 1 gc time: 0

Compare this with the timing for sequential lists:

> (module n racket/base
    (require racket/list)
    (define ls (build-list 100000 values))
    (time (for ([i 1000]) (last ls))))
> (require 'n)
cpu time: 402 real time: 403 gc time: 0

On the other hand, while list operations such as cons, car, and cdr take constant time just like their sequential-list counterparts, the constant factors are usually worse. In particular, cdr may allocate memory. For example, here is the same program, but last is computed by iteratively taking the cdr of the list instead of (list-ref xs (sub1 (length xs))):

> (module o racket/base
    (require data/ralist)
    (define ls (build-list 100000 values))
    (define (last xs)
      (if (empty? (cdr xs)) (car xs) (last (cdr xs))))
    (time (for ([i 1000]) (last ls))))
> (require 'o)
cpu time: 7072 real time: 7080 gc time: 56

Compare this with the performance of using sequential lists:

> (module p racket/base
    (require racket/list)
    (define ls (build-list 100000 values))
    (define (last xs)
      (if (empty? (cdr xs)) (car xs) (last (cdr xs))))
    (time (for ([i 1000]) (last ls))))
> (require 'p)
cpu time: 390 real time: 390 gc time: 0

There are several benchmarks described in the Benchmarks section comparing the performance of random-access lists to sequential-access lists as well as mutable data structures such as vectors. In general, random-access lists are well-suited for situations requiring variable-length lists that are mostly accessed by indexed.

1.1 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.2 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.

procedure
(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.3 Iterations and Comprehensions

syntax
(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.4 Values

value
empty : empty?

The empty list.

Example:

> empty
'()

procedure
(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)

procedure
(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)

procedure
(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

procedure
(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

procedure
(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

procedure
(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

procedure
(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)
first+rest: contract violation
  expected: ra:cons?
  given: '()
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:cons? ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:48.2
> (first+rest (cons 1 2))
first+rest: contract violation
  expected: ra:list?
  given: (1 . 2)
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:cons? ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:48.2

Failures without contracts:

> (first+rest empty)
ra:first+rest: expected cons, given: ()
> (first+rest (cons 1 2))
1
2

procedure
(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)
first: contract violation
  expected: ra:cons?
  given: '()
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:cons? ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:49.2
> (first (cons 'x 'y))
first: contract violation
  expected: ra:list?
  given: (x . y)
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:cons? ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:49.2

Failures without contracts:

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

procedure
(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)
rest: contract violation
  expected: ra:cons?
  given: '()
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:cons? ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:50.2
> (rest (cons 'x 'y))
rest: contract violation
  expected: ra:list?
  given: (x . y)
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:cons? ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:50.2

Failures without contracts:

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

procedure
(car+cdr xs) →
any/c 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)
car+cdr: contract violation
  expected: ra:cons?
  given: '()
  in: the 1st argument of
      (-> ra:cons? any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:51.2

Failures without contracts:

> (car+cdr empty)
ra:car+cdr: expected cons, given: ()

procedure
(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)
car: contract violation
  expected: ra:cons?
  given: '()
  in: the 1st argument of
      (-> ra:cons? any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:52.2

Failures without contracts:

> (car empty)
ra:car: expected cons, given: ()

procedure
(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)
cdr: contract violation
  expected: ra:cons?
  given: '()
  in: the 1st argument of
      (-> ra:cons? any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:53.2

Failures without contracts:

> (cdr empty)
ra:cdr: expected cons, given: ()

procedure
(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: contract violation
  expected: (count>/c 3)
  given: (x y z)
  in: the ls argument of
      (->i
       ((ls (i) (count>/c i))
        (i natural-number/c))
       any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:81.2
> (list-ref (list* 'x 'y 'z) 2)
list-ref: contract violation
  expected: (count>/c 2)
  given: (x y . z)
  in: the ls argument of
      (->i
       ((ls (i) (count>/c i))
        (i natural-number/c))
       any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:81.2

Failures without contracts:

> (list-ref (list 'x 'y 'z) 3)
kons-size: contract violation
  expected: kons?
  given: '()
> (list-ref (list* 'x 'y 'z) 2)
kons-size: contract violation
  expected: kons?
  given: 'z

procedure
(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)
list-set: contract violation
  expected: (count>/c 3)
  given: (x y z)
  in: the ls argument of
      (->i
       ((ls (i) (count>/c i))
        (i natural-number/c)
        (x any/c))
       any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:85.2
> (list-set (list* 'x 'y 'z) 2 'c)
list-set: contract violation
  expected: (count>/c 2)
  given: (x y . z)
  in: the ls argument of
      (->i
       ((ls (i) (count>/c i))
        (i natural-number/c)
        (x any/c))
       any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:85.2

Failures without contracts:

> (list-set (list 'x 'y 'z) 3 'd)
kons-size: contract violation
  expected: kons?
  given: '()
> (list-set (list* 'x 'y 'z) 2 'c)
kons-size: contract violation
  expected: kons?
  given: 'z

procedure
(list-update xs i f) → cons?
  xs : (count>/c i)
  i : natural-number/c
  f : (procedure-arity-includes/c 1)

Returns (list-set xs i (f (list-ref xs i))).

procedure
(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.

procedure
(list-ref/update xs i f) →
any/c cons?
  xs : (count>/c i)
  i : natural-number/c
  f : (procedure-arity-includes/c 1)

Returns (values (list-ref xs i) (list-set xs i (f (list-ref xs i)))), but is more efficient.

procedure
(second xs) → any/c
xs : (and/c list? (count>/c 1))

Returns the second element of the list.

procedure
(third xs) → any/c
xs : (and/c list? (count>/c 2))

Returns the third element of the list.

procedure
(fourth xs) → any/c
xs : (and/c list? (count>/c 3))

Returns the fourth element of the list.

procedure
(fifth xs) → any/c
xs : (and/c list? (count>/c 4))

Returns the fifth element of the list.

procedure
(sixth xs) → any/c
xs : (and/c list? (count>/c 5))

Returns the sixth element of the list.

procedure
(seventh xs) → any/c
xs : (and/c list? (count>/c 6))

Returns the seventh element of the list.

procedure
(eighth xs) → any/c
xs : (and/c list? (count>/c 7))

Returns the eighth element of the list.

procedure
(ninth xs) → any/c
xs : (and/c list? (count>/c 8))

Returns the ninth element of the list.

procedure
(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))
second: contract violation
  expected: ra:list?
  given: (a b . c)
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:list? (count>/c 1)) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:64.2
> (second (list 'a))
second: contract violation
  expected: (count>/c 1)
  given: (a)
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:list? (count>/c 1)) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:64.2

Failures without contracts:

> (second (list* 'a 'b 'c))
'b
> (second (list 'a))
kons-size: contract violation
expected: kons?
given: '()

procedure
(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)
last: contract violation
  expected: ra:cons?
  given: '()
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:cons? ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:73.2
> (last (list* 1 2 3))
last: contract violation
  expected: ra:list?
  given: (1 2 . 3)
  in: an and/c case of
      the 1st argument of
      (-> (and/c ra:cons? ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:73.2

Failures without contracts:

> (last empty)
kons-rest: contract violation
expected: kons?
given: '()
> (last (list* 1 2 3))
2

procedure
(map f xs ...+) → list?
   f :
(or/c (is-true/c (zero? (count xs)))
      (procedure-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))
map: contract violation
  expected: (or/c (is-true/c (zero? (count xs)))
(procedure-arity-includes/c 2))
  given: #<procedure:add1>
  in: the f argument of
      (->i
       ((f
         (xs r)
         (or/c
          (is-true/c (zero? (count xs)))
          (procedure-arity-includes/c
           (add1 (mz:length r)))))
        (xs ra:list?))
       #:rest
       (r
        (xs)
        (listof
         (and/c list? (count=/c (count xs)))))
       any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:114.2
> (map + (list 1 2 3) (list 4))
map: contract violation
  expected: (listof (and/c ra:list? (count=/c 3)))
  given: '((4))
  in: the r argument of
      (->i
       ((f
         (xs r)
         (or/c
          (is-true/c (zero? (count xs)))
          (procedure-arity-includes/c
           (add1 (mz:length r)))))
        (xs ra:list?))
       #:rest
       (r
        (xs)
        (listof
         (and/c list? (count=/c (count xs)))))
       any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:114.2

Failures without contracts:

> (map add1 (list 1 2 3) (list 4 5 6))
add1: arity mismatch;
the expected number of arguments does not match the given
number
  expected: 1
  given: 2
  arguments...:
   1
   4
> (map + (list 1 2 3) (list 4))
+: contract violation
  expected: number?
  given: '#s(node 1 2 3)
  argument position: 1st
  other arguments...:
   4

procedure
(foldr f b xs ...+) → any
   f :
(or/c (is-true/c (zero? (count xs)))
      (procedure-arity-includes/c (+ 2 (mz:length ...))))
  b : any/c
  xs : list?

Like foldr but for random-access lists.

procedure
(foldl f a xs ...+) → any
   f :
(or/c (is-true/c (zero? (count xs)))
      (procedure-arity-includes/c (+ 2 (mz:length ...))))
  a : any/c
  xs : list?

Like foldl but for random-access lists.

procedure
(andmap f xs ...+) → any
   f :
(or/c (is-true/c (zero? (count xs)))
      (procedure-arity-includes/c (add1 (mz:length ...))))
  xs : (and/c list? (count=/c (count xs)))

Like andmap but for random-access lists.

procedure
(ormap f xs ...+) → any
   f :
(or/c (is-true/c (zero? (count xs)))
      (procedure-arity-includes/c (add1 (mz:length ...))))
  xs : (and/c list? (count=/c (count xs)))

Like ormap but for random-access lists.

procedure
(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)

procedure
(build-list n f) → list?
  n : natural-number/c
   f :
(or/c (is-true/c (zero? n))
      (procedure-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)
build-list: contract violation
  expected: (or/c (is-true/c (zero? n))
(procedure-arity-includes/c 1))
  given: 'not-function
  in: the f argument of
      (->i
       ((n natural-number/c)
        (f
         (n)
         (or/c
          (is-true/c (zero? n))
          (procedure-arity-includes/c 1))))
       any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:108.2

Failures without contracts:

> (build-list 5 'not-function)
application: not a procedure;
expected a procedure that can be applied to arguments
  given: 'not-function
  arguments...:
   2

procedure
(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))
length: contract violation
  expected: ra:list?
  given: (1 2 . 3)
  in: the 1st argument of
      (-> ra:list? any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:60.2

Failures without contracts:

> (length (list* 1 2 3))
2

procedure
(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

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

procedure
(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)
append: contract violation
  expected: ra:list?
  given: 3
  in: an element of
      the rest argument of
      (->* () #:rest (listof ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:61.2
> (append 1 (list 2 3))
append: contract violation
  expected: ra:list?
  given: 1
  in: an element of
      the rest argument of
      (->* () #:rest (listof ra:list?) any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:61.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

procedure
(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))
reverse: contract violation
  expected: ra:list?
  given: (1 2 . 3)
  in: the 1st argument of
      (-> ra:list? any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:62.2

Failures without contracts:

> (reverse (list* 1 2 3))
kons-tree: contract violation
expected: kons?
given: 3

procedure
(range n) → list?
n : natural-number/c

Returns a list of natural numbers ranging from 0 to n-1 in ascending order.

Examples:

> (range 0)
'()
> (range 10)
(0 1 2 3 4 5 6 7 8 9)

Failures with contracts:

> (range (list 1 2 3))
range: contract violation
  expected: natural-number/c
  given: (1 2 3)
  in: the 1st argument of
      (-> natural-number/c any)
  contract from:
      <pkgs>/ralist/data/ralist/contract.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/ralist/data/ralist/contract.rkt:63.2

Failures without contracts:

> (range (list 1 2 3))
arithmetic-shift: contract violation
  expected: exact-integer?
  given: (1 2 3)
  argument position: 1st
  other arguments...:
   -1

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

2 Contracts

(require data/ralist/contract)

package: ralist

procedure
(count=/c n) → flat-contract?
n : natural-number/c

Returns a flat contract that requires the input to have a count equal to n.

procedure
(count>/c n) → flat-contract?
n : natural-number/c

Returns a flat contract that requires the input to have a count greater than n.

procedure
(is-true/c x) → flat-contract?
x : any/c

Returns a flat contract that requires nothing of its input, and returns x, i.e. it produces a contract for the predicate (lambda (_) x).

3 Tests

(require data/ralist/run-tests)

package: ralist

Runs all unit tests for this package.

3.1 Tree tests

(require data/ralist/tests/tree)

package: ralist

value
tree-tests : test-suite?

Example:

> (run-tests tree-tests)
13 success(es) 0 failure(s) 0 error(s) 13 test(s) run
0

3.2 RaList tests

(require data/ralist/tests/ra-list)

package: ralist

value
ra-list-tests : test-suite?

Example:

> (run-tests ra-list-tests)
439 success(es) 0 failure(s) 0 error(s) 439 test(s) run
0

3.3 Garden fence tests

(require data/ralist/tests/garden-fence)
	package: ralist

value
garden-fence-tests : test-suite?

Example:

> (run-tests garden-fence-tests)
80 success(es) 0 failure(s) 0 error(s) 80 test(s) run
0

3.4 Frequency counting tests

(require data/ralist/tests/freq-count)

package: ralist

value
freq-count-tests : test-suite?

Example:

> (run-tests freq-count-tests)
5 success(es) 0 failure(s) 0 error(s) 5 test(s) run
0

4 Benchmarks

(require data/ralist/run-benchmarks)

package: ralist

Runs all of the benchmarks for this package.

4.1 Random-access vs. Sequential-access lists

(require data/ralist/benchmarks/ra-list)
	package: ralist

This benchmark compares the performance of typical list operations for random and sequential lists.

procedure
(run-ra-list-benchmark) → void?

Runs this benchmark.

4.2 Contracted vs. Uncontracted bindings

(require data/ralist/benchmarks/contract)
	package: ralist

This benchmark compares the performance of the contracted and uncontracted bindings.

procedure
(run-contract-benchmark) → void?

Runs this benchmark.

4.3 Frequency counting

(require data/ralist/benchmarks/freq-count)
	package: ralist

This benchmark compares an number of imperative and functional solutions to the problem of counting the frequencies of each number in a given list of numbers.

See the thread starting here for discussion.

procedure
(run-freq-count-benchmark) → void?

Runs this benchmark.

4.4 Garden fence encryption

(require data/ralist/benchmarks/garden-fence)
	package: ralist

This benchmark compares solutions to the problem of garden fence encryption.

Garden fence encryption works as follows: you are given a plain text message (String) and a key (Nat). You scramble the message by a process that depends on the given key, producing a cipher text message (String) of the same length as the given plain text message. The scrambled message can be de-scrambled to obtain the original message by an inverse process when it is given the same key.

procedure
(encrypt s k) → string?
s : string?
k : natural-number/c

Produce the cipher text of the given string using the given key.

procedure
(decrypt s k) → string?
s : string?
k : natural-number/c

Produce the plain text of the given string using the given key.

Examples:

> (encrypt "diesisteinklartext" 6)
"dkinleiasertittxse"
> (decrypt "dkinleiasertittxse" 6)
"diesisteinklartext"

The process of scrambling a message works in a zigzag form. The key gives the number of lines to the zigzag. So suppose we want to encrypt the message "diesisteinklartext" with the key 6. Imagine the characters of the string are arranged in a zigzag, or wave, or even fence-like pattern, where the height of the wave, or zigzagging fency thing is 6:

;;;; 1. d k = (d k) = "dk"

;;;; 2. i n l = (i n l) = "inl"

;;;; 3. e i a = (e i a) = "eia"

;;;; 4. s e r t = (s e r t) = "sert"

;;;; 5. i t t x = (i t t x) = "ittx"

;;;; 6. s e = (s e) = "se"

The characters are grouped by line, forming the lists above. The lists are appended in order to obtain the resulting cipher text: "dkinleiasertittxse".

The following solutions are included in the benchmark:

An imperative, vector-based algorithm.
A functional translation of the above using random-access lists.
A functional algorithm designed by output structure.
A combinator style algorithm.
A cyclic sequence algorithm.

See the thread starting here and here for discussion.

procedure
(run-garden-fence-benchmark) → void?

Runs this benchmark.

top ← prev up next →