▼Functional Data Structures in Typed Scheme
On this page:
list
empty?
cons
cons-to-end
first
rest
append
->list
map
foldl
foldr
filter
remove
Version: 5.0.1.2
  ← prev  up  next → 

5 Catenable List

 (require "catenablelist.ss")

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

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

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

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

  '()

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

  '(2 3 4 5 6 7)

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

  - : (Listof Exact-Positive-Integer)

  '(1 4 9 16 25 36)

(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

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