[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: srfi-44@xxxxxxxxxxxxxxxxx*Subject*: Re: Procedures (interfaces)*From*: "Bradd W. Szonye" <bradd+srfi@xxxxxxxxxx>*Date*: Tue, 21 Oct 2003 00:20:47 -0700*Delivered-to*: srfi-44@xxxxxxxxxxxxxxxxx*In-reply-to*: <20031021011250.GA26398@xxxxxxxxxxxxxxxxxxx>*Mail-followup-to*: srfi-44@xxxxxxxxxxxxxxxxx*References*: <20031016200629.GE2858@xxxxxxxxxxxxxxx> <20031020182528.GA26827@xxxxxxxxxxxxxxxxxx> <20031020191331.GB4433@xxxxxxxxxxxxxxx> <20031020203620.GB28213@xxxxxxxxxxxxxxxxxx> <20031021004429.GE4433@xxxxxxxxxxxxxxx> <20031021011250.GA26398@xxxxxxxxxxxxxxxxxxx>*User-agent*: Mutt/1.4i

As promised, here is my suggestion for revising the collection procedures. I tried to remain faithful to the original, and I tried to avoid even minor changes. No, really! Nevertheless, I'm sure that it will look like a big change. Therefore, let me preface my revision with some rationales. Feel free to question or reject them -- as you've already seen, I'm amenable to leaving things the way they are if you have a good reason to do so. Organization - With the new attributes like reversible, it was too difficult to organize procedures by collection type. Instead, I list them all by procedure type (constructor, accessor, etc.) with a "defined for:" clause below each usage example. I think I correctly specified all of the interfaces, but please double-check them if you decide to use this. Dictionaries - I generalized the collection-building procedures to work well with dictionaries. For example, *-add can now build a dictionary; just give it a (cons key value) pair, like you do in the dictionary constructor. Likewise, *-remove can remove a mapped value; it returns the removed key and value as a pair. There's also a specialized *-add-key (for convenience's sake) and *-remove-key (for necessity's sake). I removed the *-put function, but added a note to *-set-key that some dictionaries may permit key addition via that procedure. In other words, the "add-or-set" operation is optional. Removal and deletion - All remove-type procedures now return the modified collection and the removed value. If it's a dictionary, remove returns a key-value pair. Set! compatible with R5RS - The original specification for *-set! was incompatible with R5RS vector-set!, which modifies the vector in-place and returns an unspecified value. I changed *-set! to match that, and I changed *-set (the functional version) to return the modified collection and the previous value. *=? and <=?: I added question marks for consistency with functions like string=?. I also removed the elt= argument and changed the definition so that it was no longer necessary. I was reluctant to make this change, but I felt that the original version just wasn't viable. The main problem, once again, is that a single equivalence predicate just doesn't work for dictionaries. I considered passing (cons key=? val=?) to the procedure, but that wouldn't work for non-dictionaries. In the end, I went with the *=? interface, partly because it makes for a trivial implementation of string=?. I think that's all of the major changes. Here's the revision: PROCEDURES Many procedures accept an optional procedure (thunk) to handle failure. If a procedure cannot perform the requested operation (because the collection has a fixed size, is immutable, does not permit duplicate values, does not contain a requested value, would become unordered, etc.), it returns the value of invoking the thunk with no arguments. The default thunk signals an error. CONSTRUCTORS procedure: make-% {key<? | key=?} {val<? | val=?} => % defined for: all collections Constructs a new % collection. Some collections may require ordering or equivalence functions during construction. Dictionaries may require comparison functions for both keys and values. (Ordered collections should derive their equivalence functions from the ordering function whenever possible.) procedure: % {key<? | key=?} {val<? | val=?} value ... => % defined for: all collections Constructs a new % collection with the values as its contents. Some collections may require ordering or equivalence functions during construction. Dictionaries may require comparison functions for both keys and values. (Ordered collections should derive their equivalence functions from the ordering function whenever possible.) procedure: *-copy * => * defined for: all collections Returns a new collection of the same type as the argument with the same contents but distinct storage. The copy is shallow; that is, it copies values in a way that preserves object identity. TYPE PREDICATES procedure: collection? value => value procedure: %? value => value defined for: all collections Returns a true value iff the provided value supports the interface for the type (%) named in the predicate. CARDINALITY OPERATORS procedure: *-empty? collection => boolean Returns a true value iff the collection is known to be empty. This function should return false if it is known that there are values within the collection, or if it is unknown whether any values exist. procedure: *-size collection => exact integer defined for: all collections If the collection has a concept of size, this function returns the number of values or mappings in the collection. If it does not, #f must be returned. If possible, this should return the number of times collection-fold will call the fold-function before halting. procedure: *-count * value => exact integer defined for: all collections Counts the number of times value occurs in the collection, according to the collection's equivalence function. procedure: *-key-count * value => exact integer defined for: dictionaries Counts the number of times key occurs in the collection, according to the collection's key-equivalence function. EQUIVALENCE AND TOTAL ORDERING RELATIONS procedure: *=? *... => boolean defined for: all collections Returns a true value if all collections are equal. Two collections are equal if they have the same equivalence function (if any) and the same *-count for each value. Dictionaries must also have the same key-equivalence function (if any), the same *-key-count for each key, and the same value mapped to each key. Sequences and ordered collections must have the same ordering. When comparing types of collections with different equality rules, use the least strict rule. procedure: *<? *... => boolean defined for: all collections Returns a true value if all collections are ordered from least to greatest, using an implementation-defined total order. procedure: *-equivalence-function * => procedure defined for: bags, sets, and dictionaries Returns the value equivalence function for the collection. procedure: *-key-equivalence-function * => procedure defined for: dictionaries Returns the key equivalence function for the dictionary. procedure: *-ordering-function * => procedure defined for: ordered bags, sets, and dictionaries Returns the value ordering function for the collection. procedure: *-key-ordering-function * => procedure defined for: ordered dictionaries Returns the key ordering function for the dictionary. ENUMERATIONS procedure: collection-fold collection f seed ... => seed ... defined for: all collections Enumerates all values in the sequence in an arbitrary order. For sequences and ordered collections, this may be the same as *-fold-left, or it may be the most efficient order. procedure: *-fold-left * f seed ... => seed ... defined for: sequences and ordered collections Enumerates all values from left to right (least to greatest, if ordered). procedure: *-fold-right * f seed ... => seed ... defined for: sequences and ordered collections Enumerates all values from right to left (greatest to least, if ordered). procedure: *-fold-keys * f seed ... => seed ... defined for: dictionaries Enumerates all dictionary keys and values in an arbitrary order. procedure: *-fold-keys-left * f seed ... => seed ... defined for: sequential and ordered dictionaries Enumerates all dictionary keys and values from left to right (least to greatest, if ordered). procedure: *-fold-keys-right * f seed ... => seed ... Enumerates all dictionary keys and values from right to left (greatest to least, if ordered). procedure: *->list collection => list defined for: all collections Returns a newly allocated list containing the collection's values. If the collection is a sequence or an ordered collection, the list must contain the values in the same order as a left enumeration. procedure: *-keys->list collection => list defined for: dictionaries Returns a newly allocated list containing the collection's keys. If the dictionary is also a sequence or an ordered collection, the list must contain the keys in the same order as a left key enumeration. ACCESSORS procedure: *-get * [thunk] => value defined for: all collections Returns an arbitrary value from a collection. procedure: *-get-key * key [thunk] => value defined for: dictionaries Returns the value mapped by the given key. procedure: *-get-left * [thunk] => value defined for: sequences and ordered collections Returns the leftmost value in the sequence or the least value in the ordered collection. procedure: *-get-right * [thunk] => value defined for: reversible sequences and reversible ordered collections Returns the rightmost value in the sequence or the greatest value in the ordered collection. procedure: *-ref * position [thunk] => value defined for: sequences and ordered collections Returns the value stored in the sequence in the given position, which must be an exact integer between 0 and one less than the collection's size. (Some sequences may extend the range of allowed positions.) procedure: *-contains? * value => boolean defined for: bags, sets, and dictionaries Returns a true value if the collection contains any instances of the requested value. VALUE MUTATORS procedure: *-set * position new-value [thunk] => * value procedure: *-set! * position new-value [thunk] => unspecified defined for: sequences and ordered collections Replaces the value stored in the sequence in the given position, which must be an exact integer between 0 and one less than the collection's size. (Some sequences may extend the range of allowed positions.) The *-set procedure returns two values: the modified collection and the position's previous value. The *-set! procedure modifies the original collection destructively and returns an unspecified value. procedure: *-set-key * key new-value [thunk] => * value procedure: *-set-key! * key new-value [thunk] => unspecified defined for: sequences and ordered collections Replaces the value mapped to the key, which must already exist. The *-set-key procedure returns two values: the modified collection and the key's previous mapped value. The *-set-key! procedure modifies the original collection destructively and returns an unspecified value. procedure: *-update * position f [thunk] => * procedure: *-update! * position f [thunk] => unspecified defined for: sequences and ordered collections Updates the value stored in the sequence in the given position to the result of applying the one-argument function f to the previous value. (An update may be more efficient than the equivalent get-f-set expression, and it may permit atomic or thread-safe operation.) The *-update procedure returns the modified collection. The *-update! procedure modifies the original collection and returns an unspecified value. procedure: *-update-key * key f [thunk] => * procedure: *-update-key! * key f [thunk] => unspecified defined for: sequences and ordered collections Updates the value mapped by key to the result of applying the one-argument function f to the previous value. (An update may be more efficient than the equivalent get-f-set expression, and it may permit atomic or thread-safe operation.) The *-update-key procedure returns the modified collection. The *-update-key! procedure modifies the original collection and returns an unspecified value. COLLECTION MUTATORS When adding or inserting a value into a dictionary, the new value must be a key-value pair, unless the procedure is specifically defined for dictionaries. Likewise, when removing or deleting a dictionary value, the returned value is a key-value pair. A key-value pair is a Scheme pair whose car is the key and whose cdr is the mapped value: (cons key value). procedure: *-clear[!] * [thunk] => * defined for: all collections Returns an empty collection of the same type as the argument. procedure: *-add[!] * new-value [thunk] => * defined for: all collections Returns a collection of the same type with the new value added. procedure: *-add-each[!] * source-collection [thunk] => * defined for: all collections As *-add, except that it adds each of the values in the source collection. If the source collection contains duplicate values, it adds each duplicate individually. If the destination collection is a dictionary, the source must provide key-value pairs. procedure: *-add-key[!] * new-key mapped-value [thunk] => * defined for: dictionaries Returns a collection of the same type with the new key mapped to the given value. procedure: *-remove[!] * value [thunk] => * value defined for: all collections except those with fixed size Removes a single instance of the given value. Returns the modified collection and the removed value. procedure: *-remove-every[!] * value => * list defined for: all collections Removes every instance of the given value. Returns the modified collection and the removed value. Note: If the collection contains no matching values, the procedure does not invoke the failure thunk; it returns (values * '()). procedure: *-remove-each-from[!] * source-collection [thunk] => % list procedure: *-remove-every-from[!] * source-collection [thunk] => % list defined for: all collections As *-remove and *-remove-every, repeated for each value in the source collection. If the source collection has duplicate values, the *-remove-each-from procedure will remove those values multiple times. Duplicate values have no effect on the *-remove-every-from procedure. procedure: *-remove-left[!] * [thunk] => * value defined for: flexible sequences and ordered collections Removes the leftmost value in the sequence or the least value in the ordered collection. Returns the updated collection and the value removed. procedure: *-remove-right[!] * [thunk] => * value defined for: reversible sequences and reversible ordered collections Removes the rightmost value in the sequence or the greatest value in the ordered collection. Returns the updated collection and the value removed. procedure: *-remove-key[!] * key [thunk] => * pair defined for: dictionaries Removes a single mapping with the given key. Returns the modified dictionary and the removed key-value pair. procedure: *-remove-every-key[!] * key [thunk] => * list defined for: dictionaries Removes every mapping with the given key. Returns the modified dictionary and a list of the removed key-value pairs. Like *-remove-every, this procedure returns an empty list instead of invoking the failure thunk. procedure: *-remove-each-key-from[!] * source [thunk] => * list procedure: *-remove-every-key-from[!] * source [thunk] => * list defined for: dictionaries As *-remove-key and *-remove every-key, except that they remove each key found in the source collection. If the source collection is another dictionary, use its keys as the source; otherwise, use the source collection's values. Examples: (dictionary-remove-every-key-from dict1 dict2) Removes every key from dict1 that is also a key of dict2. (dictionary-remove-every-key-from my-dict my-bag) Removes every key from my-dict that is a value of my-bag. (dictionary-remove-every-key-from my-dict '(hello goodbye)) Removes the mappings keyed to 'hello and 'goodbye. These procedures return two values: The modified dictionary and a list of key-value pairs. procedure: *-insert[!] * position new-value [thunk] => * defined for: flexible sequences Returns a collection of the same type with the new value inserted before the given position, increasing the collection's size by one. If the position is not equal to the collection's initial size, the procedure will shift all previous values right by one, starting at the insertion point. procedure: *-insert-left * new-value [thunk] => * defined for: flexible sequences As *-insert, except that it inserts the new value at position 0. procedure: *-insert-right * new-value [thunk] => * defined for: reversible sequences As *-insert, except that it inserts the new value at the end of the sequence. procedure: *-delete[!] * n [thunk] => * value defined for: flexible sequences and ordered collections Deletes the nth position in the collection (which may shift subsequent values to the left). Returns the resulting collection and the value at the deleted position. The position must be an exact integer within the collection's range. procedure: *-delete-left * [thunk] => * defined for: flexible sequences and ordered collections As *-delete, except that it deletes the value at position 0. procedure: *-delete-right * [thunk] => * defined for: reversible sequences and reversible ordered collections As *-delete, except that it deletes the value at the end of the sequence. SET OPERATIONS procedure: *-union[!] * ... => * defined for: sets Returns the set union of one or more sets. The resulting set contains the values of all input sets. procedure: *-intersection[!] * ... => * defined for: sets Returns the set intersection of one or more sets. The resulting set contains the values common to all input sets. procedure: *-difference[!] * ... => * defined for: sets Returns the set difference between the first set and the union of all subsequent sets. The resulting set contains the values of the first set which appear in no subsequent set. Returns an empty set if given no arguments. -- Bradd W. Szonye http://www.szonye.com/bradd

**Follow-Ups**:**Re: Procedures (interfaces)***From:*Taylor Campbell

**Re: Procedures (interfaces)***From:*scgmille

**References**:**s/-LEFT//g?***From:*Bradd W. Szonye

**Re: s/-LEFT//g?***From:*scgmille

**Re: s/-LEFT//g?***From:*Bradd W. Szonye

**Re: s/-LEFT//g?***From:*scgmille

**Re: s/-LEFT//g?***From:*Bradd W. Szonye

**Procedures (interfaces)***From:*Bradd W. Szonye

- Prev by Date:
**Procedures (interfaces)** - Next by Date:
**Re: Traits, dictionaries** - Previous by thread:
**Procedures (interfaces)** - Next by thread:
**Re: Procedures (interfaces)** - Index(es):