> > qsort [] = []
> > qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
> > where
> > smaller = [y | y <- xs, y < x],
> > larger = [y | y <- xs, y >= x]
> >
> > Very brief, to the point and easy to read (if you understand the list
> > generation syntax). However, let's examine it against the Lisp version.
> > The Lisp version is equally simple:
> >
> > (defun qsort (list)
> > (if (null list)
> > nil
> > (let* ((x (car list))
> > (xs (cdr list))
> > (smaller (loop for y in xs when (< y x) collect y))
> > (larger (loop for y in xs when (>= y x) collect y)))
> > (append (qsort smaller) (list x) (qsort larger)))))
>
> or with some syntactic sugar (list comprensions and
> the select-match macro from Stephen Adams (1990 ;-) )
> it looks like this (in Common Lisp!):
>
> (amanda qs (l)
> () => '()
> (pivot . x) => (append (qs [y (y <- x) (< y pivot)])
> (list pivot)
> (qs [y (y <- x) (>= y pivot)])))

Gauche Scheme or Racket:

(use srfi-1) ;; car+cdr for Gauche
or
(require srfi/1) ;; car+cdr for Racket
(require srfi/8) ;; receive for Racket
(require srfi/26) ;; cut for Racket

(define (qsort L)
(if (null? L)
'()
(receive (x xs) (car+cdr L)
(define-values (smaller larger) (partition (cut < <> x) xs))
(append (qsort smaller) (list x) (qsort larger)))))

(qsort
'(21 20 15 6 14 17 0 1 10 12 19 3 7 16 13 5 2 9 4 11 18 8))

===>
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21)

In Forth?

On Saturday, March 12, 2022 at 11:17:56 AM UTC+1, Robert L. wrote:
Do something useful with your time, my favorite incel. I got another challenge for you:

Sometimes, when testing whether the solution to a task (for example, here on Rosetta Code) is correct, the difference in floating point calculations between different language implementations becomes significant.

For example, a difference between 32 bit and 64 bit floating point calculations may appear by about the 8th significant digit in base 10 arithmetic.

Task

Create a function which returns true if two floating point numbers are approximately equal.

The function should allow for differences in the magnitude of numbers, so that, for example,
100000000000000.01 may be approximately equal to 100000000000000.011,
even though 100.01 is not approximately equal to 100.011.

If the language has such a feature in its standard library, this may be used instead of a custom function.

Show the function results with comparisons on the following pairs of values:

100000000000000.01, 100000000000000.011 (note: should return true)
100.01, 100.011 (note: should return false)
10000000000000.001 / 10000.0, 1000000000.0000001000
0.001, 0.0010000001
0.000000000000000000000101, 0.0
sqrt(2) * sqrt(2), 2.0
-sqrt(2) * sqrt(2), -2.0
3.14159265358979323846, 3.14159265358979324

Answers should be true for the first example and false in the second, so that just rounding the numbers to a fixed number of decimals should not be enough. Otherwise answers may vary and still be correct.

: test-f~ ( f1 f2 -- )
1e-18 \ epsilon
f~ \ AproximateEqual
if ." True" else ." False" then
;
In Scheme?

Hans Bezemer

On 3/12/22 9:23 AM, Hans Bezemer wrote:
> I got another challenge for you:
>
> Sometimes, when testing whether the solution to a task (for example,
> here on Rosetta Code) is correct, the difference in floating point
> calculations between different language implementations becomes
> significant. [snip]

You will never hear from him about your counter-challenge. But
mentioning Rosetta Code is useful if he were truly interesting in
comparing Forth solutions to Scheme or whatever. Of course there is
already a Forth QuickSort in Rosetta that he could have easily found.

I have found some very useful Forth code snippets here on clf.
For example, you once placed here a simple and efficient string sort
that I have since used many times. Thanks for that. :-)

Another example is Albert van der Horst's efficient linked list sort.
There are other examples too numerous to mention.

-Doug

Doug Hoffman schrieb am Mittwoch, 16. März 2022 um 09:02:20 UTC+1:
> On 3/12/22 9:23 AM, Hans Bezemer wrote:
> > I got another challenge for you:
> >
> > Sometimes, when testing whether the solution to a task (for example,
> > here on Rosetta Code) is correct, the difference in floating point
> > calculations between different language implementations becomes
> > significant. [snip]
>
> You will never hear from him about your counter-challenge. But
> mentioning Rosetta Code is useful if he were truly interesting in
> comparing Forth solutions to Scheme or whatever. Of course there is
> already a Forth QuickSort in Rosetta that he could have easily found.

Indeed Robert L's sportive invitations are mostly as brainless as
"hey, I got a hammer, you got a screwdriver, can you nail as well as me?"

Nevertheless sometimes they can produce a smile, or put a finger on
Forth's strengths and weaknesses. Some guys are tempted to respond
but often have to resort to a non-standard Forth dialect.

On 3/16/22 4:37 AM, minf...@arcor.de wrote:

> Indeed [his] sportive invitations are mostly as brainless as
> "hey, I got a hammer, you got a screwdriver, can you nail as well as me?"

Yes. I would say "hey I got a do-it-all programmer's-swiss-army-knife,
you have just a box of basic tools (hammer, screwdriver, etc)".

> Nevertheless sometimes they can produce a smile, or put a finger on
> Forth's strengths and weaknesses. Some guys are tempted to respond

Agreed. I have been guilty of responding. I try not to do that anymore. :-)

> but often have to resort to a non-standard Forth dialect.

Those that are Forth-related like 8th or Oforth (or non-ANS) I usually
find interesting.

-Doug

keskiviikko 16. maaliskuuta 2022 klo 10.02.20 UTC+2 Doug Hoffman kirjoitti:
> Another example is Albert van der Horst's efficient linked list sort.
> There are other examples too numerous to mention.
>

Can linked list be sorted efficiently? I think only good way with linked list is insertion sort. I personally like circular list with common head/tail that acts as sentinel. That way you don't have to separately test head and tail nodes.

On 3/16/22 5:57 AM, Jali Heinonen wrote:
> keskiviikko 16. maaliskuuta 2022 klo 10.02.20 UTC+2 Doug Hoffman kirjoitti:
>> Another example is Albert van der Horst's efficient linked list sort.

> Can linked list be sorted efficiently?

I guess that depends on one's definition of efficient. You can judge
this one for yourself:

https://groups.google.com/g/comp.lang.forth/c/9CThNEkqLrw/m/e9cQVQfEBgAJ

-Doug

> I think only good way with linked list is insertion sort. I
> personally like circular list with common head/tail that acts as
> sentinel. That > way you don't have to separately test head and tail
> nodes.

On Wednesday, March 16, 2022 at 9:02:20 AM UTC+1, Doug Hoffman wrote:
> You will never hear from him about your counter-challenge.
That's a shame - really. Because I set 'em up in a way it could benefit others.

> But mentioning Rosetta Code is useful if he were truly interesting in
> comparing Forth solutions to Scheme or whatever.
Rosetta code is awesome - I just wish there were more useful tasks there.
"12 days of Xmas" and "99 bottles of beer" hardly make library candidates.
But there IS useful stuff there to rip as well..

> Of course there is
> already a Forth QuickSort in Rosetta that he could have easily found.
4tH supports a large list of sorts - in two categories. I recently added an in place radix sort
(unfortunately - not as efficient as I had hoped) and a binary quicksort. Some taking
additional pragmas to influence their behavior.

So I don't feel have a lacks of sorting routines ;-)

Algorithm Library
Slow sort slowsort.4th
Stooge sort stoosort.4th
Cycle sort cyclsort.4th
Pancake sort pancsort.4th
Radix sort LSB radxsort.4th
Bubble sort bublsort.4th
Cocktail sort cocksort.4th
Cocktail sort
(improved) coc2sort.4th
Simple sort simpsort.4th
Simple sort
(improved) ismpsort.4th
Selection sort selcsort.4th
Insertion sort instsort.4th
Insertion sort
(improved) ins2sort.4th
Binary Insertion sort binssort.4th
Oyelami sort (MDIS) oyelsort.4th
Circle sort circsort.4th
Circle sort (improved) cir2sort.4th
Bitonic sort bitosort.4th
Merge sort mergsort.4th
Odd-even merge sort odevsort.4th
Tim sort (simple) timsort.4th
Shell sort shelsort.4th
Shell sort (A033622) shelsort.4th
Shell sort (A108870) shelsort.4th
Comb sort com2sort.4th
Heap sort hea2sort.4th
Binary Quick sort binquick.4th
Intro sort intrsort.4th
Quick sort qsort.4th
Quick sort
(unsafe) qsort.4th

> I have found some very useful Forth code snippets here on clf.
> For example, you once placed here a simple and efficient string sort
> that I have since used many times. Thanks for that. :-)
Must have been CircleSort - I developed that one. Yes, it carries quite a bang for the buck.
> Another example is Albert van der Horst's efficient linked list sort.
> There are other examples too numerous to mention.
Point is - I rarely encounter problems that involve lists. Neither professionally nor personally.
I know there are people swearing lists are THE best thing since sliced bread, but I rarely find
a problem that says: "Yeah, lists!". I once developed a lib for handling lists, but then I
found out the problem I had invented it for would be better served by an ordinary array.

Later, when I developed the "INI file manager", yeah - that one worked fine with lists -
and it was applied there. Next problem, I haven't found any use for the "INI file manager" yet.
I got an "INI file interpreter" as well and that one has been used several times.

It happens quite often I develop stuff - either because a user requests it or because I
think it will be useful and then sits on the shelf for years without use. Like a string stack. First,
I developed one which allowed you to build several ones and you could swap values. Then I
built one that just allows you to build several of 'em. Finally, I built one that allows only
one, but is quite fast, easy to handle and quite compact. Guess which one has been used most? ;-)

The same with associative arrays, regex engines, printf, etc. It gets build, it seldom gets used (by me),
while others are found in almost every program. Like BREAK?
https://sourceforge.net/p/forth-4th/wiki/I%20need%20a%20BREAK%3F/

You'd almost think I'm a Forth programmer.. ;-)

Hans Bezemer

the.bee...@gmail.com schrieb am Mittwoch, 16. März 2022 um 12:38:29 UTC+1:
> Point is - I rarely encounter problems that involve lists. Neither professionally nor personally.
> I know there are people swearing lists are THE best thing since sliced bread, but I rarely find
> a problem that says: "Yeah, lists!".

FWIW Forth high level code can be stored in lists whose 1st element is a (sub)list with header
information. In this way a Forth program (or library) becomes a searchable list database
very similar to a Prolog database. Through pattern matching it is rather easy to implement
peephole optimization, superinstructions, and compilation to machie code including
dead code elimination (I know it works because I did all this 40 ys ago using Turbo Prolog on DOS).

But as you said, when you don't need lists, don't use them. ;-)

Jali Heinonen <jali.heinonen@gmail.com> writes:
>Can linked list be sorted efficiently?

Mergesort has O(n ln n) performance. Quicksort has the usual
quadratic worst case, and it's more expensive to avoid this case in a
pre-sorted list than in a pre-sorted array, but it also does ok (with
O(n ln n) achievable in the pre-sorted case, too.

But I would not use lists if I want to sort them. And I would not
sort them. What's the obsession with sorting? I have not needed a
sort in Forth in the 38 years since I started using it. And IIRC not
in C, either.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2021: https://euro.theforth.net/2021

On 16/03/2022 18:06, Anton Ertl wrote:
> Jali Heinonen <jali.heinonen@gmail.com> writes:
>> Can linked list be sorted efficiently?
>
> Mergesort has O(n ln n) performance. Quicksort has the usual
> quadratic worst case, and it's more expensive to avoid this case in a
> pre-sorted list than in a pre-sorted array, but it also does ok (with
> O(n ln n) achievable in the pre-sorted case, too.
>
> But I would not use lists if I want to sort them. And I would not
> sort them. What's the obsession with sorting? I have not needed a
> sort in Forth in the 38 years since I started using it. And IIRC not
> in C, either.

Really? I've needed sorting for a variety of applications (in 8th, or
C/C++, or any other language -- the language is besides the point).

I did add a 'heap' datastructure in 8th to accomplish sort-on-reception
of data, which is nice, but not always useful.

On Wednesday, March 16, 2022 at 1:19:33 PM UTC+1, minf...@arcor.de wrote:
[..]
> FWIW Forth high level code can be stored in lists whose 1st element is a (sub)list with header
> information. In this way a Forth program (or library) becomes a searchable list database
> very similar to a Prolog database. Through pattern matching it is rather easy to implement
> peephole optimization, superinstructions, and compilation to machie code including
> dead code elimination (I know it works because I did all this 40 ys ago using Turbo Prolog on DOS).
>
> But as you said, when you don't need lists, don't use them. ;-)

In my iSPICE, each device is a CREATE DOES> type Forth word that performs run-time
code generation. The devices are organized in lists, linked by their NT. Apart from
code-generation, these lists are also used to insert the device stamps in the MNA matrix
and to print results, show device info, generate netlist information etc.. This is done
through a number of 'methods'. All the list members execute at least once per simulation
step.

I would hesitate to call this object-oriented code, but it sure is the most efficient and
flexible method I could come up with.

-marcel

Hans Bezemer <the.beez.speaks@gmail.com> writes:
> Point is - I rarely encounter problems that involve lists. Neither
> professionally nor personally. I know there are people swearing lists
> are THE best thing since sliced bread, but I rarely find a problem
> that says: "Yeah, lists!".

Lists are natural and intuitive to use in some languages, such as (heh)
Lisp. So they are used a lot there. I've also used them plenty of
times in C. I think in Forth, they're less easy to use, and
applications that want them don't come up as often, so they're not seen
as much.

On 17/03/2022 1:31, Paul Rubin wrote:
> Hans Bezemer <the.beez.speaks@gmail.com> writes:
>> Point is - I rarely encounter problems that involve lists. Neither
>> professionally nor personally. I know there are people swearing lists
>> are THE best thing since sliced bread, but I rarely find a problem
>> that says: "Yeah, lists!".
>
> Lists are natural and intuitive to use in some languages, such as (heh)
> Lisp. So they are used a lot there. I've also used them plenty of
> times in C. I think in Forth, they're less easy to use, and
> applications that want them don't come up as often, so they're not seen
> as much.

They're natural for the languages which are based around them, but how
many real-world problems revolve around lists (and which can't be
handled as naturally with arrays)?

I agree with The Beez on this. I had considered adding lists (to 8th),
but couldn't see any argument for them over arrays. And of course, you
can create all the Lispy-list-words using an array as the 'list'.

Not a problem I've had a reason to solve, TBH.

Ron AARON <clf@8th-dev.com> writes:
> They're natural for the languages which are based around them, but how
> many real-world problems revolve around lists (and which can't be
> handled as naturally with arrays)?

Traditionally the Forth word list is implemented as a list. You can
cons new items onto a list in constant time til you run out of memory,
without having to know the final size in advance. Resizeable arrays are
nice, but resizing usually means having to copy the data around.
Somehow (some) Forthers who won't tolerate occasional GC pauses are ok
with array resizing.

> I agree with The Beez on this. I had considered adding lists (to 8th)...

I think resizeable arrays are more usable now than they were in the old
days on memory starved systems. Resizing usually means allocating a
large chunk of new memory (e.g. doubling the old size of the array), so
you have lots of memory that is allocated but unused.

Lists are also natural if you program in functional style, since you
don't have to mutate existing objects (consing is just new allocations:
the old stuff stays the same). The immutable equivalent of arrays is
balanced trees, which are way more complicated to implement.

On 17/03/2022 7:30, Paul Rubin wrote:
> Ron AARON <clf@8th-dev.com> writes:
>> They're natural for the languages which are based around them, but how
>> many real-world problems revolve around lists (and which can't be
>> handled as naturally with arrays)?
>
> Traditionally the Forth word list is implemented as a list. You can
> cons new items onto a list in constant time til you run out of memory,

Right. Reva Forth's dictionary was implemented as a list, while 8th's is
a map (associative-array, hash-table).

With a list, adding is constant time, but lookup is O(n). With the map,
lookup is constant time while adding is between constant and O(n) most
of the time (depending on the load factor).

> without having to know the final size in advance. Resizeable arrays are
> nice, but resizing usually means having to copy the data around.
> Somehow (some) Forthers who won't tolerate occasional GC pauses are ok
> with array resizing.

I haven't found array-resizing to be anywhere near significant in terms
of performance. Maybe that's just an artifact of usage-pattern, I don't
know.

What I do know is that dynamic arrays are incredibly useful.

>
>> I agree with The Beez on this. I had considered adding lists (to 8th)...
>
> I think resizeable arrays are more usable now than they were in the old
> days on memory starved systems. Resizing usually means allocating a
> large chunk of new memory (e.g. doubling the old size of the array), so
> you have lots of memory that is allocated but unused.

That depends on your memory utilization pattern. Quite often (in
practice) the memory is simply resized in-place, nothing gets moved. Of
course, "modern" machines are extremely fast (compared to embedded
controllers and the like).

>
> Lists are also natural if you program in functional style, since you
> don't have to mutate existing objects (consing is just new allocations:
> the old stuff stays the same). The immutable equivalent of arrays is
> balanced trees, which are way more complicated to implement.

I don't understand this. Arrays are just as immutable as balanced trees.
Or, rather, just as mutable. Either can be modified.

Yes, balanced trees are a bit complex to implement; 8th has three
varieties built-in, for different use-cases. Debugging them was a lot of
fun...

Ron AARON <clf@8th-dev.com> writes:
> I haven't found array-resizing to be anywhere near significant in
> terms of performance.

For 8th, it probably doesn't matter, just that it introduces small
pauses, as gc usually does as well. 8th is gc'd iirc. In fact plenty
of soft realtime systems use gc, but some Forthers go berserk when gc is
mentioned.

> Quite often (in practice) the memory is simply resized in-place,
> nothing gets moved.

In that case there was unused memory past the existing array boundary.

> Of course, "modern" machines are extremely fast (compared to embedded
> controllers and the like).

There's a speed-memory tradeoff, so even on a slower machine you can
limit the resize overhead, by reserving enough extra space on each
resize. A huge amount of Knuth vol 1 going back to the 1960s is about
this ;).

> I don't understand this. Arrays are just as immutable as balanced
> trees. Or, rather, just as mutable. Either can be modified.

If you want a fast lookup structure that can be updated without
mutation, balanced trees can do that, arrays really can't. You might
like Chris Okasaki's book "Purely Functional Data Structures".

Ron AARON <clf@8th-dev.com> writes:
>On 17/03/2022 7:30, Paul Rubin wrote:
>> Lists are also natural if you program in functional style, since you
>> don't have to mutate existing objects (consing is just new allocations:
>> the old stuff stays the same). The immutable equivalent of arrays is
>> balanced trees, which are way more complicated to implement.
>
>I don't understand this. Arrays are just as immutable as balanced trees.
>Or, rather, just as mutable. Either can be modified.

His point is: If you have a language that does not support changing
existing data structures, you program by creating a new item that
represents the new state. In case of an array this means copying all
the data that is not changed. In the case of a tree this means
copying only the unchanged data in changed nodes and their ancestor
nodes. For large data structures, this is much more efficient.
Therefore, functional programs use trees instead of arrays.

>Yes, balanced trees are a bit complex to implement; 8th has three
>varieties built-in, for different use-cases.

What are the use cases? I have not found a serious use for search
trees in my programming, much less balanced search trees.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2021: https://euro.theforth.net/2021

Paul Rubin <no.email@nospam.invalid> writes:
>I think resizeable arrays are more usable now than they were in the old
>days on memory starved systems.

The typical approach on memory-starved systems was static arrays at
best configurable on startup (but more typically in the source code;
in Forth that is actually the same). The data either fits or it does
not. If it does not, you can get a little wiggle room by configuring
some data structure larger (but configuring a different one smaller to
make all fit), but other than that you are out of luck. Resizable
arrays don't give you more capability, only more convenience.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2021: https://euro.theforth.net/2021

On 17/03/2022 18:25, Paul Rubin wrote:
> Ron AARON <clf@8th-dev.com> writes:
>> I haven't found array-resizing to be anywhere near significant in
>> terms of performance.
>
> For 8th, it probably doesn't matter, just that it introduces small
> pauses, as gc usually does as well. 8th is gc'd iirc. In fact plenty
> of soft realtime systems use gc, but some Forthers go berserk when gc is
> mentioned.

We still remember it from Microsoft BASIC days. In fact anything 'dynamic'
prompts us to ask 'do I really need that?' - including ALLOCATE, circular
buffers and other bandwagons as may be passing through.

Ron AARON <clf@8th-dev.com> writes:
>
>
>On 16/03/2022 18:06, Anton Ertl wrote:
>> What's the obsession with sorting? I have not needed a
>> sort in Forth in the 38 years since I started using it. And IIRC not
>> in C, either.
>
>Really? I've needed sorting for a variety of applications (in 8th, or
>C/C++, or any other language -- the language is besides the point).

The language is important. In most languages sorting is not needed,
but the shell has tools such as join and uniq that require sorted
inputs (or, in the case of many uses of uniq, are useless without
sorting first); with hash-table-based equivalents of these tools most
of my uses of sort in shell scripts could be eliminated, and thus most
of my uses of sorting. Of course, in my shell usage there is still
the following usage:

Sorting is useful for human consumption, so I sometimes do it as last
step on the output of a Forth or C program (and I have a nice shell
tool called sort for that). But sorting is normally not useful for
internal operations of programs; hashing is almost always better
there.

There is an exception: You need to associate a value with the
next-larger (or next-smaller) key in a lookup table without being able
to compute that key (e.g., because it is the next power-of-two). But,
as mentioned, I have not come across that situation.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2021: https://euro.theforth.net/2021

Anton Ertl schrieb am Donnerstag, 17. März 2022 um 09:12:13 UTC+1:
> Ron AARON <c...@8th-dev.com> writes:
> >
> >
> >On 16/03/2022 18:06, Anton Ertl wrote:
> >> What's the obsession with sorting? I have not needed a
> >> sort in Forth in the 38 years since I started using it. And IIRC not
> >> in C, either.
> >
> >Really? I've needed sorting for a variety of applications (in 8th, or
> >C/C++, or any other language -- the language is besides the point).
> The language is important. In most languages sorting is not needed,
> but the shell has tools such as join and uniq that require sorted
> inputs (or, in the case of many uses of uniq, are useless without
> sorting first); with hash-table-based equivalents of these tools most
> of my uses of sort in shell scripts could be eliminated, and thus most
> of my uses of sorting. Of course, in my shell usage there is still
> the following usage:
>
> Sorting is useful for human consumption, so I sometimes do it as last
> step on the output of a Forth or C program (and I have a nice shell
> tool called sort for that). But sorting is normally not useful for
> internal operations of programs; hashing is almost always better
> there.
>
> There is an exception: You need to associate a value with the
> next-larger (or next-smaller) key in a lookup table without being able
> to compute that key (e.g., because it is the next power-of-two). But,
> as mentioned, I have not come across that situation.

A practical application example:
Alarm logs in realtime control systems are one area where sorting is
required for output on display, reports, data extraction and analysis.
When this could touch time-critical functions, sorting is often supported by
background indexing while new alarms are added to the alarm tables.
IOW fancy sorting algorithms or data movement are not necessary here.

On 17/03/2022 9:25, Paul Rubin wrote:
> Ron AARON <clf@8th-dev.com> writes:
>> I haven't found array-resizing to be anywhere near significant in
>> terms of performance.
>
> For 8th, it probably doesn't matter, just that it introduces small
> pauses, as gc usually does as well. 8th is gc'd iirc. In fact plenty
> of soft realtime systems use gc, but some Forthers go berserk when gc is
> mentioned.

8th is GC'd, but on a continual basis (reference-counting), so the cost
of GCing is relatively constant rather than stop-the-world kind of thing.

>
>> Quite often (in practice) the memory is simply resized in-place,
>> nothing gets moved.
>
> In that case there was unused memory past the existing array boundary.

Exactly. It is very much dependent on the memory allocator in use.

>
>> Of course, "modern" machines are extremely fast (compared to embedded
>> controllers and the like).
>
> There's a speed-memory tradeoff, so even on a slower machine you can
> limit the resize overhead, by reserving enough extra space on each
> resize. A huge amount of Knuth vol 1 going back to the 1960s is about
> this ;).

I've got his books :)

>
>> I don't understand this. Arrays are just as immutable as balanced
>> trees. Or, rather, just as mutable. Either can be modified.
>
> If you want a fast lookup structure that can be updated without
> mutation, balanced trees can do that, arrays really can't. You might
> like Chris Okasaki's book "Purely Functional Data Structures".

I'm unsure what you mean, then, by 'mutation'...

On 17/03/2022 9:28, Anton Ertl wrote:
> Ron AARON <clf@8th-dev.com> writes:
>> On 17/03/2022 7:30, Paul Rubin wrote:
>>> Lists are also natural if you program in functional style, since you
>>> don't have to mutate existing objects (consing is just new allocations:
>>> the old stuff stays the same). The immutable equivalent of arrays is
>>> balanced trees, which are way more complicated to implement.
>>
>> I don't understand this. Arrays are just as immutable as balanced trees.
>> Or, rather, just as mutable. Either can be modified.
>
> His point is: If you have a language that does not support changing
> existing data structures, you program by creating a new item that
> represents the new state. In case of an array this means copying all
> the data that is not changed. In the case of a tree this means
> copying only the unchanged data in changed nodes and their ancestor
> nodes. For large data structures, this is much more efficient.
> Therefore, functional programs use trees instead of arrays.

OK.

>
>> Yes, balanced trees are a bit complex to implement; 8th has three
>> varieties built-in, for different use-cases.
>
> What are the use cases? I have not found a serious use for search
> trees in my programming, much less balanced search trees.

The tree varieties supported are plain binary-tree, b-tree, and BK-tree.
This last is a particularly useful tree if you have a metric function
(for example, Levenshtein distance), very useful for word-similarity
look-up.

As for the other two, they're not particularly dissimilar in use, just a
matter of some efficiency (in memory usage).

In terms of use-cases? Well, my users asked for them -- so I presume
they had particular uses in mind.

On 17/03/2022 9:57, Anton Ertl wrote:
> Ron AARON <clf@8th-dev.com> writes:
>>
>>
>> On 16/03/2022 18:06, Anton Ertl wrote:
>>> What's the obsession with sorting? I have not needed a
>>> sort in Forth in the 38 years since I started using it. And IIRC not
>>> in C, either.
>>
>> Really? I've needed sorting for a variety of applications (in 8th, or
>> C/C++, or any other language -- the language is besides the point).
>
> The language is important. In most languages sorting is not needed,
> but the shell has tools such as join and uniq ...

> Sorting is useful for human consumption...

Well, and there you are. Sorting is obviously useful in user-facing
applications (of course, not always and not everywhere).

Presenting a list of names or places is most often done as a sorted
list, because it's easier for a (normal) user to scan a sorted list.

The language used for the application isn't important, because the need
for sorting user-facing data (among other examples) is present
regardless of the language. Some languages make it easier than others,
but there's a reason even C has qsort() in the library.