DIRECTORY Atom USING [PropList, DottedPair, DottedPairNode], Basics USING [Comparison] ; List: CEDAR DEFINITIONS = BEGIN 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; EqLists: PUBLIC PROC [l1, l2: LIST OF REF ANY] RETURNS [BOOLEAN] ; 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]}; 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]; 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] = 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. NthTail: PROC[list: LIST OF REF ANY, n: INT] RETURNS[LIST OF REF ANY]; NthElement: PROC[list: LIST OF REF ANY, n: INT] RETURNS[REF ANY]; 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]}; 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]; 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]; 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; NotATail: SIGNAL [list, tailOfList: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- raised by LDiff END. Zedited 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 Types Predicates: EqLists, Memb true each of the corresponding elements of l1 and l2 are =. constructors of lists: Cons, Append, Reverse, Remove, Union, Intersection, ListDifference ... like some constructors, but destructive to structure: Nconc, DReverse, DSubst ... like Append except second argument is an element, not a list extractors: NthTail NthElement, Car, Cdr, Cadr, Cddr, etc. negative numbers mean count from the end, e.g. -1 means last tail. returns NIL if n > Length[list]. negative numbers mean count from the end, e.g. -1 means last element of list. raises NotThatLong if fewer than ABS[n] elements. AList operations: Assoc, DotCons, PutAssoc miscellaneous: Length, Map, Subst Sorting Errors Э╩уЦ "Cedar" styleШJЪЬ.Щ.JЪЬ,Щ,JЩ-Ъ╧k Ш JЪЬЭЬ(Ш2JЪЬЭЬ ШJШЧJШJЪ╧lЬЭЬЭЬШJЪЭШheadЩJЪЬЭЬШJЪЬЭЬШ#JЪЬЭЬШ+JШЪ╧nЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШLJЪЬЭЬШ%ЧЧЪЬ╤npr ЩЪЯЬЭЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬШCJЪЬ;Щ;ЧЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШBJЪЬЭШJЪЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШVJЪЭЬЭЬШЧЧЪЬ╨prGЩ^ЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШJJЪЬЭЬЭЬЭЬШ#ЧJЪ!ЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬ╧c(ШБЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШDJЪЬЭЬЭЬШ ЧJЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШLJЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШAJЪЯЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ?JЪЯЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШGJЪЯЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬвШiJЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШIЧЪЬ6бЩQJЪЯЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬвШNЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШKJЪв<Щ