Libraries for Vicare Scheme: lists low

23.16 Low level utilities

The following bindings are exported by (vicare containers lists low).

Function: %and/or-null? ell ...: This is the implementation of and/or-null?. Return two values being the return values of and-null? and or-null? applied to the list arguments.

Function: %and/or-eq? list-of-clists1 list-of-clists2

Given two lists of lists (possibly circular), compare with eq? the sublists from the arguments, and return two boolean values:

True if each sublist from list-of-clists1 is eq? to its homologous from list-of-clists2.
True if at least one sublist from list-of-clists1 is eq? to its homologous from list-of-clists2.

list-of-clists1 and list-of-clists2 are meant to have the same length, but this is not tested. The iteration will stop when the end of the shorter list is found.

To understand how this function is used, consider the following:

(define (circular-list= item= . list-of-clists)
  (let-values (((and-nil or-nil)
               (apply %and/or-null? list-of-clists)))
    (cond (and-nil #t)
          (or-nil  #f)
          (else
           (let loop ((cells list-of-clists))
             (let-values (((cars cdrs) (%cars/cdrs* cells)))
               (or
                (null? cars)
                (and
                 (apply item= cars)
                 (let-values (((and-eq or-eq)
                              (%and/or-eq? list-of-clists cdrs)))
                   (cond (and-eq #t)
                         (or-eq  #f)
                         (else (loop cdrs))))))))))))

Function: %cars list-of-lists

Function: %cars list-of-lists who

Return the list of cars of the sublists of list-of-lists, which must be a non–empty list of lists.

If all the sublists are null: The return value is null. If at least one sublist, but not all, is null: Raise an assertion violation using who as value for the &who condition. who defaults to #f.

Function: %cars* list-of-lists: Like %cars but accept sublists of different length. If at least one sublist is null: The return value is null.

Function: %cdrs list-of-lists

Function: %cdrs list-of-lists who

Return the list of cdrs of the sublists of list-of-lists, which must be a non–empty list of lists.

Function: %cdrs* list-of-lists: Like %cdrs but accept sublists of different length. If at least one sublist is null: The return value is null.

Function: %cars/cdrs list-of-lists: Given a list of sublists, return two values being the list of cars and the list of cdrs from list-of-lists. If the sublists are detected not to have equal length, raise an error.

Function: %cars/cdrs* list-of-lists: Like %cars/cdrs, but accept lists of different length. If a list in list-of-lists is null: Return 2 null values.

Function: %cars+cdrs*/no-test list-of-lists: Like %cars/cdrs*, but do not test if one sublist is null. If one sublist is null, the behaviour is undefined.

Function: %cars+knil list-of-lists knil

Function: %knil+cars list-of-lists knil

Function: %cars+knil list-of-lists knil who

Function: %knil+cars list-of-lists knil who

Return the list of cars of the sublists of list-of-lists, which must be a non–empty list of lists. %cars+knil adds knil as last value. %knil+cars adds knil as first value.

Function: %cars+knil* list-of-lists knil
Function: %knil+cars* list-of-lists knil: Like %cars+knil and %knil+cars, but accept sublists of different length. If at least one sublist is null: The return value is null.

Function: %cars+knil/cdrs list-of-lists knil

Function: %knil+cars/cdrs list-of-lists knil

Function: %cars+knil/cdrs list-of-lists knil who

Function: %knil+cars/cdrs list-of-lists knil who

Given that list-of-lists must be a non–empty list of lists, return two values: The list of cars and the lists of cdrs of the sublists. %cars+knil/cdrs adds knil as last value of the cars. %knil+cars/cdrs adds knil as first value of the cars.

If all the sublists are null: The return values are both null. If at least one sublist, but not all, is null: Raise an assertion violation using who as value for the &who condition. who defaults to #f.

Function: %cars+knil/cdrs* list-of-lists knil
Function: %knil+cars/cdrs* list-of-lists knil: Like %cars+knil/cdrs and %knil+cars/cdrs, but accept sublists of different length. If at least one sublist is null: The return value is null.

Queues

The following macros handle queue values: Pairs whose car is a list and whose cdr is the last pair in the list. They allow user friendly insertion of elements at the end of the list. Experiments show that building a list in reverse and then applying reverse to it, is almost always faster than using these queue macros.

          -----------
  queue  | car | cdr |
          -----------
            |     |
        ----       ----------------
       |                           |
       v                           v
      ---    ---    ---    ---    ---
list | | |->| | |->| | |->| | |->| | |->()
      ---    ---    ---    ---    ---
      |      |      |      |      |
      o      o      o      o      o

Syntax: %make-queue obj: Build and return a new queue having obj as first argument. Takes care of evaluating obj only once.

Syntax: %list->queue ell: Embed list into a queue and return it. Takes care of evaluating ell only once.

Syntax: enqueue! queue obj: Enqueue obj at the end of queue and return a new queue value. Takes care of evaluating obj only once, but evaluates queue multiple times.

Syntax: %queue-list-ref queue: Return the list inside of queue. It is a synonym of car.

Syntax: %queue-last-pair-ref queue: Return the last pair of the list inside of queue. It is a synonym of cdr.

Examples of building a list using a queue:

(define max-value+1 10)

(do ((i 1 (+ 1 i))
     (l (%make-queue 0) (%enqueue! l i)))
    ((= i max-value+1)
     (%queue-list-ref l)))
⇒ '(0 1 2 3 4 5 6 7 8 9)

(let loop ((l (%make-queue 0))
           (i 1))
  (if (= i max-value+1)
      (%queue-list-ref l)
    (loop (%enqueue! l i) (+ 1 i))))
⇒ '(0 1 2 3 4 5 6 7 8 9)

which is the same of doing:

(define max-value+1 10)

(do ((i 1 (+ 1 i))
     (l '(0) (cons i l)))
    ((= i max-value+1)
     (reverse l)))
⇒ '(0 1 2 3 4 5 6 7 8 9)

(let loop ((l '(0))
           (i 1))
  (if (= i max-value+1)
      (reverse l)
    (loop (cons i l) (+ 1 i))))
⇒ '(0 1 2 3 4 5 6 7 8 9)