doco srfi-1 delete, delete-duplicates

* doco srfi-1 delete, delete-duplicates
@ 2003-05-12 23:50 Kevin Ryde
  2003-05-13  2:26 ` Rob Browning
  0 siblings, 1 reply; 9+ messages in thread
From: Kevin Ryde @ 2003-05-12 23:50 UTC (permalink / raw)

Some new words to propose for srfi-1 delete and delete-duplicates.
The behaviour described is per the srfi-1 spec, the words are by me.

Conditions like the arg order of the calls and the common tail in the
returns are new, insofar as they weren't described before, but
presumably no-one would expect guile to deviate from the spec, so in
that sense there's no change.

I was sorely tempted to change the "=" formal parameter to something
like "eproc", to avoid any chance of it being confused with the core
"=" procedure.  But if that's to be done then I suppose it should be
throughout the chapter, not just in one node.

Deleting
--------

 - Scheme Procedure: delete x lst [=]
 - Scheme Procedure: delete! x lst [=]
     Return a list containing the elements of LST but with those equal
     to X deleted.  The returned elements will be in the same order as
     they were in LST.

     Equality is determined by the = predicate, or `equal?' if not
     given.  An equality call is made just once for each element, but
     the order in which the calls are made on the elements is
     unspecified.

     The equality calls are always `(= x elem)', ie. the given X is
     first.  This means for instance elements greater than 5 can be
     deleted with `(delete 5 lst <)'.

     `delete' does not modify LST, but the return might share a common
     tail with LST.  `delete!' may modify the structure of LST to
     construct its return.

 - Scheme Procedure: delete-duplicates lst [=]
 - Scheme Procedure: delete-duplicates! lst [=]
     Return a list containing the elements of LST but without
     duplicates.

     When elements are equal, only the first in LST is retained.  Equal
     elements can be anywhere in LST, they don't have to be adjacent.
     The returned list will have the retained elements in the same
     order as they were in LST.

     Equality is determined by the = predicate, or `equal?' if not
     given.  Calls `(= x y)' are made with element X being before Y in
     LST.  A call is made at most once for each combination, but the
     sequence of the calls across the elements is unspecified.

     `delete-duplicates' does not modify LST, but the return might
     share a common tail with LST.  `delete-duplicates!' may modify the
     structure of LST to construct its return.

     In the worst case, this is an O(N^2) algorithm because it must
     check each element against all those preceding it.  For long lists
     it is more efficient to sort and then compare only adjacent
     elements.

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

^ permalink raw reply	[flat|nested] 9+ messages in thread