edited by Teitelman, December 14, 1982 3:45 pm
edited by Paul Rovner, May 13, 1983 10:21 am
Last Edited by: Levin, August 8, 1983 4:50 pm
DIRECTORY
Atom USING [PropList, DottedPair, DottedPairNode],
Basics USING [Comparison]
;
List: CEDAR DEFINITIONS =
BEGIN
Types
AList: TYPE = Atom.PropList;
DottedPair: TYPE = Atom.DottedPair;
DottedPairNode: TYPE = Atom.DottedPairNode;
CompareProc:
TYPE =
PROC[ref1:
REF
ANY, ref2:
REF
ANY]
RETURNS [Comparison];
Comparison: TYPE = Basics.Comparison;
Predicates: EqLists, Memb
EqLists:
PUBLIC
PROC [l1, l2:
LIST
OF
REF
ANY]
RETURNS [
BOOLEAN] ;
true each of the corresponding elements of l1 and l2 are =.
Memb:
PROC [ref:
REF
ANY, list:
LIST
OF
REF
ANY]
RETURNS[
BOOLEAN]
= INLINE
{UNTIL list = NIL DO IF list.first = ref THEN RETURN[TRUE]; list ← list.rest; ENDLOOP;
RETURN[FALSE]};
constructors of lists: Cons, Append, Reverse, Remove, Union, Intersection, ListDifference ...
Cons:
PROC [ref:
REF
ANY, list:
LIST
OF
REF
ANY]
RETURNS [
LIST
OF
REF
ANY]
= INLINE {RETURN[CONS[ref, list]]};
Append: PROC[l1: LIST OF REF ANY, l2: LIST OF REF ANY ← NIL] RETURNS [LIST OF REF ANY]; -- if l2 is NIL, copies top level of l1.
CopyTopList:
PROC[list:
LIST
OF
REF
ANY]
RETURNS [
LIST
OF
REF
ANY]
= INLINE {RETURN[Append[list]]};
Remove: PROC[ref: REF ANY, list: LIST OF REF ANY] RETURNS[LIST OF REF ANY];
Reverse: PROC [list: LIST OF REF ANY] RETURNS[LIST OF REF ANY];
Union: PROC [l1, l2: LIST OF REF ANY] RETURNS[LIST OF REF ANY];
Intersection: PROC [l1, l2: LIST OF REF ANY] RETURNS[LIST OF REF ANY];
ListDifference: PROC [l1, l2: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- all elements in l1 not in l2
LDiff: PROC [list, tailOfList: LIST OF REF ANY] RETURNS[LIST OF REF ANY];
like some constructors, but destructive to structure: Nconc, DReverse, DSubst ...
Nconc: PROC [l1, l2: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- like Append
Nconc1:
PROC [list:
LIST
OF
REF
ANY, ref:
REF
ANY]
RETURNS[
LIST
OF
REF
ANY]
like Append except second argument is an element, not a list
= INLINE {
z: LIST OF REF ANY ← list;
IF z = NIL THEN RETURN[Cons[ref, NIL]];
UNTIL z.rest = NIL DO z ← z.rest; ENDLOOP;
z.rest ← Cons[ref, NIL];
RETURN[list];
};
DRemove: PROC [ref: REF ANY, list: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- like Remove
DReverse: PROC [list: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- like Reverse
DSubst: PROC [new, old: REF ANY, expr: LIST OF REF ANY] RETURNS[LIST OF REF ANY] ; -- like Subst.
extractors: NthTail NthElement, Car, Cdr, Cadr, Cddr, etc.
NthTail:
PROC[list:
LIST
OF
REF
ANY, n:
INT]
RETURNS[
LIST
OF
REF
ANY];
negative numbers mean count from the end, e.g. -1 means last tail.
returns NIL if n > Length[list].
NthElement:
PROC[list:
LIST
OF
REF
ANY, 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.
Cdr:
PROC[list:
LIST
OF
REF
ANY]
RETURNS[
LIST
OF
REF
ANY]
= INLINE
{RETURN[IF list = NIL THEN NIL ELSE list.rest]};
Cddr:
PROC[list:
LIST
OF
REF
ANY]
RETURNS[
LIST
OF
REF
ANY]
= INLINE
{RETURN[IF list = NIL OR list.rest = NIL THEN NIL ELSE list.rest.rest]};
Car:
PROC[list:
LIST
OF
REF
ANY]
RETURNS[
REF
ANY]
= INLINE
{RETURN[IF list = NIL THEN NIL ELSE list.first]};
Cadr:
PROC[list:
LIST
OF
REF
ANY]
RETURNS[
REF
ANY]
= INLINE
{RETURN[IF list = NIL OR list.rest = NIL THEN NIL ELSE list.rest.first]};
AList operations: Assoc, DotCons, PutAssoc
Assoc: PROC [key: REF ANY, aList: AList] RETURNS[REF ANY];
DotCons: PROC [key, val: REF ANY] RETURNS [DottedPair];
PutAssoc: PROC [key: REF ANY, val: REF ANY, aList: AList] RETURNS[AList];
miscellaneous: Length, Map, Subst
Length: PROC [list: LIST OF REF ANY] RETURNS[INT];
Map: PROC [list: LIST OF REF ANY, proc: PROCEDURE[REF ANY, LIST OF REF ANY]] ;
Subst: PROC [new, old: REF ANY, expr: LIST OF REF ANY] RETURNS [LIST OF REF ANY];
Sorting
Sort: PROC [list: LIST OF REF ANY, compareProc: CompareProc ← Compare]
RETURNS[LIST OF REF ANY];
UniqueSort: PROC [list: LIST OF REF ANY, compareProc: CompareProc ← Compare]
RETURNS[LIST OF REF ANY];
Compare: CompareProc;
Errors
NotATail: SIGNAL [list, tailOfList: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- raised by LDiff
END.