Re: [Scheme-reports] Proposed new SRFI for immutable lists

Some initial thoughts:

Should these procedures take SRFI 114 comparators instead of equality predicates?

Are cycles actually possible in strict immutable structures? When you create a head node, there's no way for it to have a circular link to a tail node that doesn't exist yet.

Personally I am fond of first, second, etc.; I think they are more readable than car, cadr, etc.

The immutable set data structures I have in mind do set-theoretic operations in O(n) time, though constructing them from an unordered list is O(n log n).

I would ditch xipair and factor out parameter rotation to a "flip" procedure, probably in a separate library or SRFI, as defined in Chicken ( http://wiki.call-cc.org/man/4/Unit%20data-structures#combinators ).

Best regards,
Kevin Wortman

On Sun, Aug 31, 2014 at 7:50 PM, John Cowan <cowan@x> wrote:

Note: The SRFI number is not yet official and is therefore subject to change.

Abstract:

Scheme currently does not provide immutable pairs corresponding to its
existing mutable pairs, although most uses of pairs do not exploit
their mutability. The Racket system takes the radical approach of
making Scheme's pairs immutable, and providing a minimal library of
mutable pairs with procedures named mpair?, mcons, mcar, mcdr, set-mcar!,
set-mcdr!. This SRFI takes the opposite approach of leaving Scheme's pairs
unchanged and providing a full set of routines for creating and dealing
with immutable pairs. The sample implementation is portable and efficient.

Rationale:

Rather than attempting to design this library from scratch, I have chosen
the conservative option of modifying SRFI 1. Consequently, most of the
rationale given in that document applies to this one as well. I have
made the following changes:

* Removed all linear-update procedures ending in !

* Removed all references to circular lists (there will be a future SRFI for
immutable bidirectional cycles).

* Removed first, second , etc., which are mostly used for poor man's records.

* Removed the O(n2) lists-as-sets procedures (there will be a future SRFI
supporting O(n log n) immutable sets).

* Inserted an i at a judicious place in each identifier, usually at the
beginning. However, because "icons" means something else in both ordinary
English and computer jargon, the basic constructor and its immediate
relatives are named ipair, xipair and ipair* instead.

* Added procedures for conversion between ordinary and immutable pairs, lists,
and trees.

* Added an analogue of apply for applying a procedure to an immutable list of
arguments.

SRFI: http://www.ccil.org/~cowan/temp/srfi-116.html
Implementation: http://www.ccil.org/~cowan/temp/ilists.tar.gz

Please send comments to <srfi-116@x> when it is created,
or to this list in the meantime.

--
John Cowan http://www.ccil.org/~cowan cowan@x
Schlingt dreifach einen Kreis vom dies!
Schliesst euer Aug vor heiliger Schau,
Denn er genoss vom Honig-Tau,
Und trank die Milch vom Paradies.

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports