From cdf79f2907cab5aa410ad47934f0374254386220 Mon Sep 17 00:00:00 2001
From: Kaz Kylheku <kaz@kylheku.com>
Date: Wed, 13 May 2020 18:43:02 -0700
Subject: lib: sort becomes non-destructive; nsort introduced.

I'm fixing a historic mistake copied from ANSI Lisp,
which trips up language newcomers and sometimes even
experienced users.

The function innocently named sort will now return newly
allocated structure. The function previously called sort will
be available as nsort (non-consing/allocating sort).

The shuffle function also becomes pure, and is accompanied by
nshuffle.

* eval (me_op): Continue to use destructive sort in this
legacy code that is only triggered in very old compat mode.
(eval_init): Registered nsort and nshuffle.

* lib.c (nsort, nshuffle): New functions introduced, closely
based on sort and shuffle.
(sort, shuffle): Rewritten to avoid destructive behavior: work
by copying the input and calling destructive counterparts.
(sort_group): Continue to use destructive sort, which is safe;
the structure is locally allocated. The sort_group function
has pure semantics.
(grade): Likewise.

* lib.h (nsort, nshuffle): Declared.

* share/txr/stdlib/getopts.tl (opthelp): Replace an instance
of the (sort (copy-list ...)) pattern with just (sort ...).

* tags.tl (toplevel): Continue to use destructive sort to sort
tags before writing the tag file; the lifetime of the tags
list ends when the file is written.

* tests/010/seq.txr: Switch some sort calls to nsort to keep
test case working.

* txr.1: Documented.
---
 txr.1 | 47 +++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 39 insertions(+), 8 deletions(-)

(limited to 'txr.1')

diff --git a/txr.1 b/txr.1
index e83cdfb6..f33024ad 100644
--- a/txr.1
+++ b/txr.1
@@ -32550,13 +32550,14 @@ is a transformed list of rows which is reconstituted into a list of columns.
   ;; (op remove-if (ap eql @3 20))
 .brev
 
-.coNP Function @ sort
+.coNP Functions @ sort and @ nsort
 .synb
 .mets (sort < sequence >> [ lessfun <> [ keyfun ]])
+.mets (nsort < sequence >> [ lessfun <> [ keyfun ]])
 .syne
 .desc
 The
-.code sort
+.code nsort
 function destructively sorts
 .metn sequence ,
 producing a sequence
@@ -32596,7 +32597,21 @@ function.
 
 The
 .code sort
-function is stable for sequences which are lists. This means that the
+function has the same argument requirements as
+.code nsort
+but is non-destructive: it returns a new object, leaving the input
+.meta sequence
+unmodified, as if a copy of the input object were made using the
+function
+.code copy
+and then that copy were sorted in-place using
+.codn nsort .
+
+The
+.code sort
+and
+.code nsort
+functions are stable for sequences which are lists. This means that the
 original order of items which are considered identical is preserved.
 For strings and vectors,
 .code sort
@@ -32604,7 +32619,9 @@ is not stable.
 
 The
 .code sort
-function can be applied to hashes. It produces meaningful behavior
+and
+.code nsort
+functions can be applied to hashes. It produces meaningful behavior
 for a hash table which contains
 .I N
 keys which are the integers from 0 to
@@ -32660,13 +32677,14 @@ in the APL language.
   [grade "Hello" >] -> (4 2 3 1 0)
 .brev
 
-.coNP Function @ shuffle
+.coNP Functions @ shuffle and @ nshuffle
 .synb
 .mets (shuffle << sequence )
+.mets (nshuffle << sequence )
 .syne
 .desc
 The
-.code shuffle
+.code nshuffle
 function pseudo-randomly rearranges the elements of
 .metn sequence .
 This is performed in place:
@@ -32682,12 +32700,25 @@ The rearrangement depends on pseudo-random numbers obtained from the
 function.
 
 The
-.code shuffle
+.code nshuffle
 function supports hash tables in a manner analogous to the way
-.code sort
+.code nsort
 supports hash tables; the same remarks apply as in the description
 of that function.
 
+The
+.code shuffle
+function has the same argument requirements and
+semantics, but differs from
+.code nshuffle
+in that it avoids in-place modification of
+.metn sequence :
+a new, shuffled sequence is returned, as if a copy of
+.meta sequence
+were made using
+.code copy
+and then that copy were shuffled in-place and returned.
+
 .coNP Function @ sort-group
 .synb
 .mets (sort-group < sequence >> [ keyfun <> [ lessfun ]])
-- 
cgit v1.2.3