This is the list of former issues that I have closed out after discussion. In discussion, please refer to the relevant topic by its tag or header. That will help us stay organised as we range over a lot of different issues. To aid navigation, this document format can be parsed using emacs' outline mode. Add LIST-DIFFERENCE ? iota defn & naming Add SUBLIST ? Removing PROPER-LIST? map function termination condition FIND, FIND-TAIL n-ary alist functions in separate lib? FIND-TAIL applies pred to list cells or list elts? lists-as-sets funs put in separate module? Naming: REMOVE / DELETE conflicts More careful specification of error cases Argument order for FOLDL and FOLDR Add UNZIP1 ? destructive/linear-update Naming: ACONS or ALIST-CONS? Naming: PAIR-frob prefix vs frob-TAIL suffix MAKE-LIST's default fill argument Naming: CONS* or LIST* Naming: APPEND-REVERSE{!} or REVERSE-APPEND{!} Argument order of = equivalence predicates This document, along with current drafts of the reference implementation and the draft SRFI (in ASCII format) can be found at ftp://ftp.ai.mit.edu/people/shivers/srfi/srfi-1/closed-issues.txt I'll HTML'ize them for the final SRFI format when discussion is done. Related documents: ftp://ftp.ai.mit.edu/people/shivers/srfi/srfi-1/small-stuff.txt Minor issues -- typos, things I went ahead and changed without feeling they required discussion ftp://ftp.ai.mit.edu/people/shivers/srfi/srfi-1/issues.txt Open topics. -Olin ------------------------------------------------------------------------------- * Add LIST-DIFFERENCE ? Several people have asked for an LDIFF or LIST-DIFFERENCE function. I asked for examples of its use. After consideration of the function, and the examples sent me, I am against adding this routine. I have examined all the examples people have sent me of uses of LDIFF or LIST-DIFFERENCE. Without fail, they can be rewritten using other tools for more general or efficient implementations. In general, I have come to associate LIST-DIFFERENCE with sloppy coding. However, even if one is attached to some particular use of LIST-DIFFERENCE, it can always be written trivially in terms of UNFOLD: (LIST-DIFFERENCE A B) is equivalent to (UNFOLD (LAMBDA (L) (EQ? L B)) CAR CDR A) However, the UNFOLD idiom is not committed to the EQ? equality predicate. (I usually take a commitment to a particular equality predicate as a sign of poor design.) The following PERMUTE function is a frequent example given, credited to Duncan Smith (note that the versions I got all produced the buggy base case (permute '()) => (), instead of (()). (define (permute ls) (cond ((null ls) '(())) ; Was buggy. ((null? (cdr ls)) (list ls)) (else (mapcon (lambda (x) (mapcar (lambda (y) (cons (car x) y)) (permute (nconc (ldiff ls x) (cdr x))))) ls)))) With four more lines of code, we can eliminate the redundant scanning and rescanning performed by the LDIFF, for a much more efficient implementation: (define (permute ls) (if (pair? ls) (let lp ((rev-head '()) (tail ls) (ans '())) (if (pair? tail) (let ((x (car tail)) (tail (cdr tail))) (lp (cons x rev-head) tail (foldl (lambda (perm ans) (cons (cons x perm) ans)) ans (permute (reverse-append rev-head tail))))) ans)) '(()))) LIST-DIFFERENCE is sometimes used to parse lists with an infix separator element, as in this example, where we have a list of the form (x1 ... xn => y1 ... ym) Here's code that splits a list of this form into the pre-=> elements and the post-=> elements: (define (parse-signature spec) (let ((mid (memq '- spec))) (values (list-difference spec mid) (cdr mid)))) Now, we can always just replace the (LIST-DIFFERENCE SPEC MID) with the equivalent (UNFOLD (LAMBDA (L) (EQ? L MID)) CAR CDR SPEC) However, with two more lines of extra code, we can rewrite PARSE-SIGNATURE without LIST-DIFFERENCE or MEMQ, giving an implementation that runs twice as fast: (define (parse-signature spec) (let recur ((elts spec)) (let ((elt (car elts))) (if (eq? elt '-) (values '() (cdr elts)) (receive (front tail) (recur (cdr elts)) (values (cons elt front) tail)))))) Or, better yet, abstract out the pattern of "splitting at some element" into this routine: (define (split-at lis split?) (let recur ((elts spec)) (let ((elt (car elts))) (if (split? elt) (values '() (cdr elts)) (receive (front tail) (recur (cdr elts)) (values (cons elt front) tail)))))) ...and then define our PARSE-SIGNATURE function in terms of it: (define (parse-signature spec) (receive (front tail) (split-at spec (lambda (x) (eq? x '=>))) (values front (cdr tail)))) Similarly, we can use LIST-DIFFERENCE to save one line of code defining an all-but-the-last-element BUTLAST function. Writing the function without LIST-DIFFERENCE costs one extra line of code and runs twice as fast. (define (butlast L) (list-difference L (last-pair L))) (define (butlast lis) (let recur ((x (car lis)) (l (cdr lis))) (if (pair? l) (cons x (recur (car l) (cdr l))) '()))) LIST-DIFFERENCE is a loser. Votes: Punt LIST-DIFFERENCE: John Stone [I have received no further support for LIST-DIFFERENCE. I am considering this topic closed.] ------------------------------------------------------------------------------- * iota defn & naming Bowing to the general will, I am abandoning my original bounds-based iota functions :iota [from] to [step] -> list iota: [from] to [step] -> list and am adopting the simple count-based function proposed by Evans (iota count [start step]) ; start=0; step=1 ------------------------------------------------------------------------------- * Add SUBLIST ? Several people have requested (SUBLIST lis start end). I explicitly did not put this function in the library, since reaching into the middle of a list and taking out a specific, fixed subsegment seems contrary to the general idea of lists. But. I realise that many times we sleazily use lists as fixed tuples, and in cases like this, SUBLIST can be handy (e.g., the grammatical structure of sexp-based languages). I do *not* think, in any event, that SUBLIST is an acceptable replacement for TAKE and DROP. It is much clearer, to my eye, to use functions that specifically return prefixes or suffixes than to use the general SUBLIST function when this is what is desired. All the more so in the case of lists, where one must do a linear-time pass over the whole list just to get the final index to pass to SUBLIST. So some questions: - Should SUBLIST be added to the existing repertoire of TAKE & DROP funs? - If so, should we also add a linear-update SUBLIST! ? - Should I tweak the definition of SUBLIST to aid in indexing "from the right"? + I could make the END argument optional, defaulting to the length of the list. + I could make the END argument range over negative as well as non-negative indices, indicating offsets from the right without requiring the programmer to explicitly precompute the list length. E.g. (sublist '(a b c d e f) 2 -1) => '(c d e f) (sublist '(a b c d e f) 2 -2) => '(c d e) (sublist '(a b c d e f) 2 -3) => '(c d) I'm just throwing out as wide a spectrum of sublist-related stuff as I can think, here. Personally, I'm pretty indifferent on all of these questions, except that I do think overall library consistency requires us to pair SUBLIST! with SUBLIST -- neither or both, but not just the one. Votes: Don't add SUBLIST: John Stone Add SUBLIST: Egorov [This issue is closed. No SUBLIST.] ------------------------------------------------------------------------------- * Removing PROPER-LIST? This procedure is exactly LIST? While the name "PROPER-LIST?" is slightly clearer than "LIST?", it is not worth breaking with established use. I am removing PROPER-LIST? from the list-lib, and leaving LIST? in. [This issue is dead. I am instead punting LIST? for PROPER-LIST?, DOTTED-LIST?, and CIRCULAR-LIST?] ------------------------------------------------------------------------------- * map function termination condition From the original proposal: 3.When do n-ary mapping functions (MAP, MAP!, FOR-EACH, PAIR-FOR-EACH, APPEND-MAP, APPEND-MAP!, FILTER-MAP, MAP-IN-ORDER) terminate? 1.When any list runs out? 2.When the first list runs out? 3.All lists must be of equal length? My preferences are in the order listed. R4RS says #3. Hence this spec requires #1. Any changes to this *must* happen by the end of the SRFI discussion period. The consistent feedback has been to go with definition #1. If you feel otherwise, speak up now, otherwise I will regard this issue as closed. Below I list two representative remarks I have received on this issue. Donovan Kolbly Dylan, which has a fairly general collections mechanism, also takes approach #1. Generalizing lists, a collection in Dylan is regarded as a mapping from keys to values. The keys for lists and vectors are integers starting at zero. n-ary mapping functions do an intersection-join on the keys of their arguments, and hence, for the list case, only operate on the common keys, ie, along the shortest list. From: John David Stone As soon as any of the lists is exhausted (alternative 1 in Shivers's list). My second choice is Shivers's alternative 3: all lists must be the same length. [Votes are consistently in favor of choice #1. I am closing this issue.] ------------------------------------------------------------------------------- * FIND, FIND-TAIL n-ary "Will Fitzgerald" Since ANY, EVERY, FOLDL, FOLDR, PAIR-FOLDL, PAIR-FOLDR, and LIST-INDEX can take multiple lists as arguments, should FIND and FIND-TAIL do the same? I am uncomfortable with the idea of procedures whose return "arity" depends on their call arity. I would prefer to keep FIND and FIND-TAIL simple. Votes: Against: Olin, John Stone, lth [Issue is closed.] ------------------------------------------------------------------------------- * alist functions in separate lib? Separate: John David Stone , lth Together: Olin, Will Fitzgerald John David Stone Yes. The most conclusive point for me is that they take a different copy procedure -- that suggests that they are really a different data type and so deserve a separate library. Hmm -- I still prefer to keep the alist functions in the general list lib. [Issue is closed: together.] ------------------------------------------------------------------------------- * FIND-TAIL applies pred to list cells or list elts? List cells: List elts: Olin, John David Stone No one supports list cells. Good. Let's consider this issue closed. ------------------------------------------------------------------------------- * lists-as-sets funs put in separate module? Together: Olin, Will Fitzgerald Separate: John David Stone , lth stone: "It should be kept separate. Again the crucial argument is that sets are a different data type: EQUAL-AS-SETS? will not be the same as EQUAL?, for instance." In my view, lists-as-sets aren't a different data type, they are a particular use of lists. These functions are sufficiently useful to warrant being included in the general list lib. The list-set functions are found in SRFI-3 http://srfi.schemers.org/srfi-3/ [Issue closed. Together.] ------------------------------------------------------------------------------- * Naming: REMOVE / DELETE conflicts John David Stone "Sergei Egorov" The issue is that some Schemes use DELETE to name the functions that delete elements from lists using equality tests, and some use REMOVE. SRFI-1 has gone with DELETE, and uses REMOVE to name the functions that filter lists with a predicate. There are conflicts no matter which one I choose, and solid precedent over part of the community with the current choice: T, S48, MIT Scheme: delq/delv/delete/delq!/delv!/delete! Bigloo, Chez, MzScheme: remq/remove/remove! CommonLisp has both REMOVE and DELETE -- the former being pure, and the latter being destructive. This is a terrible naming convention; Scheme has the bang suffix, which makes for a much clearer and tighter linkage. We get no guidance here. (And CL's naming is probably why Scheme implementations have diverged on this issue. Urk.) Unless I hear of a good alternative name for list-lib's REMOVE, I will keep with the current uses of DELETE and REMOVE and their derived names. What is needed is a name to replace REMOVE that fits in with this trio: FILTER / PARTITION / ??? REMOVE is the best, most natural simple root I could think of. FILTER-NOT or NKEEP or KEEP-NOT are awkward. EXTIRPATE seems a little over-the-top. I am not a fan of the -IF suffix. It looks awkward to my eye; I associate IF with conditional forms, not variables bound to procedures. [Issue closed.] ------------------------------------------------------------------------------- * More careful specification of error cases Matthias Felleisen ...the specification for a procedure like TAKE should contain a sentence like "It is an error if is larger than the length of ." Furthermore, I believe that libraries should go even further and specify that "it is an error if a procedure whose i-th parameter is specified to be a receives an i-th argument that does not belong to the collection of ." Again, this gives the implementation the freedom to delay signaling an error until the non-listness of the argument is discovered or not to signal an error or to be preemptive in checking the nature of all arguments. Of course, the statement should be generalized over and as appropriate. A more careful specification of error cases is a good thing; I will work on this. I have already added a great deal of argument checking to the latest version of the reference implementation, per Matthias's prodding, and will make another pass over the spec. ------------------------------------------------------------------------------- * Argument order for FOLDL and FOLDR John David Stone points out that the n-list case tends to suggest (f ... ) rather than (f ... ) Good point, but I want consistency between the two functions. state-value last: srfi-1, SML, MzScheme, Scheme 48 state-value first: Haskell, MIT Scheme [Issue closed.] ------------------------------------------------------------------------------- * Add UNZIP1 ? Egorov: UNZIP1 is missing although it no less useful than other procedures of the UNZIP family: (unzip1 '((1) (2) (3))) => (1 2 3) This is just (MAP CAR list). But I will add the binding if there is demand for it; it seems like a reasonable thing to do simply for consistency, to avoid surprise. May I hear some opinions? Votes: Yes: Will Fitzgerald [Issue closed: add] ------------------------------------------------------------------------------- * destructive/linear-update Sperber has checked in verbally supporting weakening the spec for the bang procedures to be linear-update. Clinger claims some people claim side-effects are needed. Lars says he himself needs guaranteed side-effects. Lars supports having both linear-update and guaranteed side-effect bindings. Note that this doesn't complicate simple implementations as all -- it just means you implement the side-effect version, and bind it to both names. I'd like to hear more support for required-mutation. After *much* thought on this issue -- there are many possible directions one could choose, and all have advantages and disadvantages -- I have just recently arrived at the following proposal that will serve Lars' concerns, not bloat out the basic lib, and has what strikes me as a reasonably natural and concise naming convention. Let us proceed on the assumption that required-mutation is the rare case, albeit one we will support. We will use a *double* bang for these names -- extra emphasis!! Really change the list!! We can then place these procedures in a separate library, list-lib!!. Here are the procedures we'd add take!! drop!! append!! reverse-append!! append-map!! map!! filter!! partition!! remove!! del!! delq!! delv!! delete!! delq-duplicates!! delv-duplicates!! delete-duplicates!! del-duplicates!! alist-delete!! del-ass!! del-assq!! del-assv!! del-assoc!! reverse!! (Again, note that in most cases, these names will be bound to the exact same procedures to which their single-bang cousins will be bound.) Now if someone like Lars writes code that *relies*, e.g., due to sharing, on really performing side-effects, instead of simply *permitting* side-effects as an optimisation, e.g., due to non-sharing, the double-bangs will draw the eye to these semantically effectful operations. (What we are doing here is separating side-effects as pragmatics from side-effects as semantics.) An alternate would be to use a + suffix to indicate linear-update, and reserve ! for required-side-effect. We could still move all the required-side-effect procs to a segregated library. Note that Common Lisp essentially uses "linear update" semantics in the definition of its "destructive" ops. This is partly to hide implementation issues -- for example, destructively reversing a cdr-coded list performs effects very differently from destructively reversing a linked-list list. Lars is still not happy with this proposal, mostly for various sorts of backwards-compatibility issues with existing practice, implementations, conventions, code, etc. Note that you *can't*, in general, "require" functions to side-effect arguments that are lists -- the empty-list case can't be handled. Votes: !!: John Stone lth is against !! [This issue is closed. We are going with linear update. !! procs can be put in another lib.] ------------------------------------------------------------------------------- * Naming: ACONS or ALIST-CONS? acons: alist-cons: Lars Thomas Hansen , Will Fitzgerald I am indifferent, and am happy to go with Lars' suggestion. Could we have some more votes? [Issue closed: ALIST-CONS] ------------------------------------------------------------------------------- * Naming: PAIR-frob prefix vs frob-TAIL suffix E.g., pair-for-each or for-each-tail? pair-fold or foldl-tail? jpiitula & egorov egorov: 8) I prefer having TAIL- prefix for procedures working with consecutive cdrs of a list; PAIR- prefix does not have this "CDR" sound (PAIR-FOR-EACH may be a better name for tree browsing procedure) These procedures work directly with the pairs or cons cells that compose the list, hence the PAIR- lexeme. I don't like the TAIL- convention, as the function doesn't operate just on the tail of the argument list, but also on the list itself. Also, these functions *don't* operate on the tail of the list that is the empty list () -- which is certainly a tail. However, my preference for PAIR- is not a strong one. I would like to hear other opinions on this name choice. [Issue closed.] ------------------------------------------------------------------------------- * MAKE-LIST's default fill argument jpiitula: I think that MAKE-LIST should not allow the 'fill' argument to be left out; at least, the default value should be unspecified as in MAKE-VECTOR and MAKE-STRING (choice of #f seems a little random to me). I have changed MAKE-LIST's spec so that the default fill value is unspecified as suggested by jpiitula & egorov. Dissenters should speak up; but I don't think there will be any. [Issue closed] ------------------------------------------------------------------------------- * Naming: CONS* or LIST* General consensus is that CONS* is a better name. I have changed the name accordingly. [Issue closed.] ------------------------------------------------------------------------------- * Naming: APPEND-REVERSE{!} or REVERSE-APPEND{!} REVERSE-APPEND is the current name. T & S48 use APPEND-REVERSE Common Lisp: REVAPPEND Egorov votes for APPEND-REVERSE, and points out it visually matches up with the definition (append (reverse x) y). It is also consistent with the current Scheme uses I've found (T & Scheme 48). I will make the change. Are there any other runtimes or libs that export these procedures, and, if so, what are the chosen names? [Issue closed] ------------------------------------------------------------------------------- * Argument order of = equivalence predicates Egorov I would also left unspecified the behavior of procedures accepting equivalence predicates [=] when given non-commutative procedures; when in doubt, one can always use -IF variants. This is an excellent point. However, I suggest it would be more useful to address this issue by specifying more precisely how the = predicate is used. Spelling out how the equivalence proc is applied seems more useful to me, and would cost nothing. How do others feel about this? I can add language to the definitions saying that the comparison is made in this form (= key-param elet) Here's the extra language: For DEL, DEL! The = procedure is an equality predicate that is used to compare the elements Ei of LIST to the key X in this way: (= X Ei) The = predicate will be used to compare each element of LIST exactly once; the order in which it is applied to the various Ei is not specified. Thus, one can reliably remove all the numbers less than five from a list with (del < 5 list) For DEL-DUPLICATES DEL-DUPLICATES! The = procedure is an equality predicate that is used to compare the elements of LIST. If X comes before Y in LIST, then the comparison is performed (= X Y) The = predicate will be used to compare each pair of elements in LIST exactly once; the order in which it is applied to the various pairs is not specified. For MEM The = procedure is an equality predicate that is used to compare the elements Ei of LIST to the key X in this way: (= X Ei) The = predicate will be used to compare each element of LIST no more than once. For ASS The = procedure is an equality predicate that is used to compare the element keys Ki of ALIST's entries to the search-key X in this way: (= X Ki) The = predicate will be used to compare each key of ALIST no more than once. Thus one can reliably find the first entry of ALIST whose key is less than five with (ass < 5 ALIST) For ALIST-DELETE DEL-ASS ALIST-DELETE! DEL-ASS! The = procedure is an equality predicate that is used to compare the elements keys Ki of ALIST's entries to the key X in this way: (= X Ki) The = predicate will be used to compare each element key of ALIST exactly once; the order in which it is applied to the various Ki is not specified. Thus, one can reliably remove all entries of ALIST whose key is less than five with (del < 5 list) [Issue closed]