List.mesa
Copyright Ó 1985, 1986, 1991 by Xerox Corporation. All rights reserved.
Teitelman, December 14, 1982 3:45 pm
Rovner, May 13, 1983 10:21 am
Levin, August 8, 1983 4:50 pm
Russ Atkinson (RRA) February 20, 1985 12:15:13 pm PST
Beach, February 22, 1985 11:15:09 am PST
Doug Wyatt, November 14, 1986 4:19:55 pm PST
DIRECTORY
Atom USING [PropList, DottedPair, DottedPairNode],
Basics USING [Comparison];
List: CEDAR DEFINITIONS
= BEGIN
Note: unless otherwise noted, the operations listed below assume that the input list arguments are acyclic, and will produce acyclic lists. The user is cautioned that use of cyclic lists may result in either infinite loops or infinite recursion (producing a machine crash).
Types
AList: TYPE = Atom.PropList;
DottedPair: TYPE = Atom.DottedPair;
DottedPairNode: TYPE = Atom.DottedPairNode;
LORA: TYPE = LIST OF REF ANY;
Comparison: TYPE = Basics.Comparison;
CompareProc: TYPE = PROC[ref1: REF ANY, ref2: REF ANY] RETURNS [Comparison];
Predicates
EqLists: PROC [l1, l2: LORA] RETURNS [BOOL];
TRUE iff each of the corresponding elements of l1 and l2 are =.
Memb: PROC [ref: REF ANY, list: LORA] RETURNS[BOOL];
TRUE iff ref occurs in list.
Constructors
Append: PROC[l1: LORA, l2: LORA ¬ NIL] RETURNS[LORA];
Appends l2 to a copy of l1.
Remove: PROC[ref: REF ANY, list: LORA] RETURNS[LORA];
Removes all instances of ref from the list, returning a copy as far as necessary.
Reverse: PROC [list: LORA] RETURNS[LORA];
Returns a reversed copy of the list.
Union: PROC [l1, l2: LORA] RETURNS[LORA];
Returns the union of the two lists, but does not copy l2; this is really only a union if there were no duplicates in either list.
Intersection: PROC [l1, l2: LORA] RETURNS[LORA];
Returns the intersection of the two lists, but does not copy l1; this is really only a intersection if there were no duplicates in either list.
ListDifference: PROC [l1, l2: LORA] RETURNS[LORA];
Returns a list containing all elements in l1 not in l2. The returned list may share with l1.
LDiff: PROC [list, tailOfList: LORA] RETURNS[LORA];
Returns a list of those elements in list up to tailOflist. tailOflist must be a tail of list, i.e. eq to some number of cdrs of list, or else the signal NotATail is raised. If tailOflist is NIL, returns list. Otherwise, always returns new structure.
Constructors, but destructive to structure
Nconc: PROC [l1, l2: LORA] RETURNS[LORA];
like Append, but modifies l1; a cycle will be formed if any tail of l1 is EQ to any tail of l2. returns IF l1 # NIL THEN l1 ELSE l2
Nconc1: PROC [list: LORA, ref: REF ANY] RETURNS[LORA];
like Nconc except second argument is an element, not a list.
Returns IF list # NIL THEN list ELSE LIST[ref].
DRemove: PROC [ref: REF ANY, list: LORA] RETURNS[LORA];
like Remove, but removes the ref from the list destructively, and ONLY removes the first occurrence of ref.
DReverse: PROC [list: LORA] RETURNS[LORA];
like Reverse, but alters the list
DSubst: PROC [new, old: REF ANY, expr: LORA] RETURNS[LORA];
like Subst.
Extractors
NthTail: PROC[list: LORA, n: INT] RETURNS[LORA];
negative numbers mean count from the end, e.g. -1 means last tail.
returns NIL if n > Length[list].
NthElement: PROC[list: LORA, n: INT] RETURNS[REF ANY];
negative numbers mean count from the end, e.g. -1 means last element of list.
raises NotThatLong if fewer than ABS[n] elements.
Association List Operations
Assoc: PROC [key: REF ANY, aList: AList] RETURNS[REF ANY];
returns the value associated with key in aList (returns NIL if no such key)
DotCons: PROC [key, val: REF ANY] RETURNS [DottedPair];
equivalent to NEW[DottedPairNode ← [key, val]]
(slightly slower, but generates less code)
PutAssoc: PROC [key: REF ANY, val: REF ANY, aList: AList] RETURNS[AList];
returns a list containing the new association; PutAssoc alters the previous association if it was present, and otherwise places the new association at the tail of the old list.
Miscellaneous
Length: PROC [list: LORA] RETURNS[INT];
Returns the # of elements in the list
Map: PROC [list: LORA, proc: PROC[REF ANY, LORA]];
Calls proc for each element in the list with the REF contained in the element and the element itself. Equivalent to the following code:
FOR each: LORA ← list, each.rest UNTIL l = NIL DO
proc[each.first, each];
ENDLOOP;
Subst: PROC [new, old: REF ANY, expr: LORA] RETURNS [LORA];
Returns a copy of the list, substituing new for each occurence of old. Equivalent to the following code (but not recursive):
SELECT TRUE FROM
expr = NIL => RETURN [NIL];
old = expr.first => RETURN [CONS[new, Subst[new, old, expr.rest]]];
ENDCASE => RETURN [CONS[expr.first, Subst[new, old, expr.rest]]];
Kill: PROC [list: LORA];
Assigns NIL to the first and rest fields of every node in the list. This is useful when trying to get all of the list returned to free storage, since a conservatively retained list node will not then keep the rest ot the list in existence. Kill works for circular lists. Equivalent to:
WHILE list # NIL DO
next: LORA ← list.rest;
list.rest ← NIL;
list.first ← NIL;
ENDLOOP;
Sorting
Sort: PROC [list: LORA, compareProc: CompareProc ¬ Compare] RETURNS[LORA];
... destructively sorts the given list in increasing order according to compareProc. The sort is not stable, so order of equal elements is not preserved.
UniqueSort: PROC [list: LORA, compareProc: CompareProc ¬ Compare] RETURNS[LORA];
... is like Sort, but removes duplicates in a separate pass over the sorted list
Merge: PROC [x,y: LORA, compareProc: CompareProc] RETURNS [LORA];
... destructively merges two lists according to compareProc. If the input lists are sorted in increasing order, then the output list will be sorted in increasing order.
Compare: CompareProc;
.. a general (although slow) CompareProc that can sort lists where all of the elements are the same type. Element types supported are ROPE, REF INT, or ATOM.
Errors
NotATail: SIGNAL [list, tailOfList: LORA] RETURNS [LORA];
raised by LDiff
END.