Version: 5.0.1.3

### 5Catenable 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)) #

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 #f > (empty? empty) - : Boolean #t

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

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

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 1 > (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)) # > (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)) #

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)