5 Catenable List

Version: 5.0.1.3

5 Catenable List

(require (planet krhari/pfds:1:3/catenablelist))

Catenable Lists are nothing but lists with efficient catenation. They use a data-structucal bootstrapping technique called Structucal Abstraction. The data structure internally uses Physicist’s Queue to realize an amortized running time of O(1) for the operations first, rest, cons and cons-to-end.

(CatenableList A)

A catenable list of type A.

(list a ...) → (CatenableList A)

a : A

Function list creates a catenable list with the given inputs.

Example:
  > (list 1 2 3 4 5 6)
  - : (U Null (List Positive-Fixnum))
  #<List>

In the above example, (list 1 2 3 4 5 6) gives a Catenable List which is similar to lists but comes with efficient append operation.

empty

A empty catenable list.

(empty? catlist) → Boolean

catlist : (CatenableList A)

Function empty? takes a Catenable List checks if the given catenable list is empty.

Examples:

> (empty? (list 1 2 3 4 5 6))

- : Boolean

> (empty? empty)

- : Boolean

(cons a catlist) → (CatenableList A)

a : A

catlist : (CatenableList A)

Function cons takes an element and a catenable list and adds the given element to the front the given catenable list.

Example:

> (cons 10 (list 1 2 3 4 5 6))

- : (U Null (List Positive-Fixnum))

#<List>

In the above example, (cons 10 (list 1 2 3 4 5 6)) returns (list 10 1 2 3 4 5 6).

(cons-to-end a catlist) → (CatenableList A)

a : A

catlist : (CatenableList A)

Function cons-to-end takes an element and a catenable list and adds the given element to the rear end the given catenable list.

Example:

> (cons-to-end 10 (list 1 2 3 4 5 6))

- : (U Null (List Positive-Fixnum))

#<List>

In the above example, (cons-to-end 10 (list 1 2 3 4 5 6)) returns (list 1 2 3 4 5 6 10).

(first catlist) → A

catlist : (CatenableList A)

Function first takes a catenable list and returns the first element of the given catenable list.

Examples:

> (first (list 1 2 3 4 5 6))

- : Positive-Fixnum

> (first empty)

first: given list is empty

(rest catlist) → (CatenableList A)

catlist : (CatenableList A)

Function rest takes a catenable list and returns a catenable list without the first element of the given catenable list.

Examples:

> (rest (list 1 2 3 4 5 6))

- : (U Null (List Positive-Fixnum))

#<List>

> (rest empty)

rest: given list is empty

In the above example, (rest (list 1 2 3 4 5 6)) returns the rest of the given catenable list, (list 2 3 4 5 6).

(append cal1 cal2) → (CatenableList A)

cal1 : (CatenableList A)

cal2 : (CatenableList A)

Function append takes two catenable lists and appends the second catenable list to the end of the first catenable list.

Examples:
  > (define cal1 (list 1 2 3 4 5 6))
  > (define cal2 (list 7 8 9 10))
  > (append cal1 cal2)
  - : (U Null (List Positive-Fixnum))
  #<List>

In the above example, (append cal1 cal2) returns (list 1 2 3 4 5 6 7 8 9 10).

(->list cal) → (Listof A)

cal : (CatenableList A)

Function ->list takes a clist and returns a list of elements which are in the same order as in the catenable list.

Examples:

> (->list (list 1 2 3 4 5 6))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5 6)

> (->list empty)

- : (Listof Nothing)

'()

(reverse cal) → (List A)

cal : (List A)

Function reverse takes a vlist and returns a reversed vlist.

Example:
  > (->list (reverse (list 1 2 3 4 5 6)))
  - : (Listof Positive-Fixnum)
  '(6 5 4 3 2 1)

(map func clst1 clst2 ...) → (CatenableList A)

func : (A B ... B -> C)

clst1 : (CatenableList A)

clst2 : (CatenableList B)

Function map is similar to map for lists.

Examples:

> (->list (map add1 (list 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(7 6 5 4 3 2)

> (->list (map * (list 1 2 3 4 5 6) (list 1 2 3 4 5 6)))

- : (Listof Exact-Positive-Integer)

'(36 25 16 9 4 1)

(foldl func init clst1 clst2 ...) → C

func : (C A B ... B -> C)

init : C

clst1 : (CatenableList A)

clst2 : (CatenableList B)

Function foldl is similar to foldl

foldl currently does not produce correct results when the given function is non-commutative.

Examples:
  > (foldl + 0 (list 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (foldl * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(foldr func init clst1 clst2 ...) → C

func : (C A B ... B -> C)

init : C

clst1 : (CatenableList A)

clst2 : (CatenableList B)

Function foldr is similar to foldr

foldr currently does not produce correct results when the given function is non-commutative.

Examples:
  > (foldr + 0 (list 1 2 3 4 5 6))
  - : Exact-Nonnegative-Integer
  21
  > (foldr * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))
  - : Exact-Positive-Integer
  518400

(andmap func lst1 lst2 ...) → Boolean

func : (A B ... B -> Boolean)

lst1 : (CatenableList A)

lst2 : (CatenableList B)

Function andmap is similar to andmap.

Examples:
  > (andmap even? (list 1 2 3 4 5 6))
  - : Boolean
  #f
  > (andmap odd? (list 1 2 3 4 5 6))
  - : Boolean
  #f
  > (andmap positive? (list 1 2 3 4 5 6))
  - : Boolean
  #t
  > (andmap negative? (list -1 -2))
  - : Boolean
  #t

(ormap func lst1 lst2 ...) → Boolean

func : (A B ... B -> Boolean)

lst1 : (CatenableList A)

lst2 : (CatenableList B)

Function ormap is similar to ormap.

Examples:
  > (ormap even? (list 1 2 3 4 5 6))
  - : Boolean
  #t
  > (ormap odd? (list 1 2 3 4 5 6))
  - : Boolean
  #t
  > (ormap positive? (list -1 -2 3 4 -5 6))
  - : Boolean
  #t
  > (ormap negative? (list 1 -2))
  - : Boolean
  #t

(build-list size func) → (CatenableList A)

size : Natural

func : (Natural -> A)

Function build-list is similar to build-list.

Examples:

> (->list (build-list 5 (λ:([x : Integer]) (add1 x))))

- : (Listof Integer)

'(1 2 3 4 5)

> (->list (build-list 5 (λ:([x : Integer]) (* x x))))

- : (Listof Integer)

'(0 1 4 9 16)

(make-list size func) → (CatenableList A)

size : Natural

func : A

Function make-list is similar to make-list.

Examples:

> (->list (make-list 5 10))

- : (Listof Positive-Fixnum)

'(10 10 10 10 10)

> (->list (make-list 5 'sym))

- : (Listof 'sym)

'(sym sym sym sym sym)

(filter func que) → (CatenableList A)

func : (A -> Boolean)

que : (CatenableList A)

Function filter is similar to filter.

Examples:

> (define que (list 1 2 3 4 5 6))

> (->list (filter (λ: ([x : Integer]) (> x 5)) que))

- : (Listof Positive-Fixnum)

'(6)

> (->list (filter (λ: ([x : Integer]) (< x 5)) que))

- : (Listof Positive-Fixnum)

'(4 3 2 1)

> (->list (filter (λ: ([x : Integer]) (<= x 5)) que))

- : (Listof Positive-Fixnum)

'(5 4 3 2 1)

(remove func que) → (CatenableList A)

func : (A -> Boolean)

que : (CatenableList A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (->list (remove (λ: ([x : Integer]) (> x 5))

(list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 4 3 2 1)

> (->list (remove (λ: ([x : Integer]) (< x 5))

(list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6 5)

> (->list (remove (λ: ([x : Integer]) (<= x 5))

(list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6)

← prev up next →

1	Queues
2	Deques
3	Heaps
4	Random Access Lists
5	Catenable List
6	VList
7	Streams
8	Red-Black Trees
9	Tries
10	Sets