You can also make list-based quicksort stable by calling list_reverse (twice).
However, list-based quicksort is not very practical; it is mostly used for illustration purpose (that is, teaching). On the other hand, list-based mergesort is useful in practice. Unlike array-based mergesort, list-based version does not need extra memory for merging. Anyway, this not particularly related to ATS. On Tue, Jun 3, 2025 at 7:55 PM jin <[email protected]> wrote: > so, the reverse is apllied to make sure the result is what user expected? > does it can be removed from function like quick sort, which seems like will > not effect the result > > 在2025年6月4日星期三 UTC+8 07:43:08<gmhwxi> 写道： > >> >> Stable sorting means the ordering of equals should not be changed after >> sorting is done. >> For instance, if we sort the following list according to parity (0 < 1): >> >> [3,2,5,4,1,6] >> >> we should get: [2,4,6,3,5,1] >> >> In the mergesort implementation you referred to, list_reverse needs to be >> called to ensure sorting >> done is actually stable sorting. Without list_reverse, the ordering among >> some equals is reversed. >> >> On Tuesday, June 3, 2025 at 7:31:48 PM UTC-4 jin wrote: >> >>> thanks a lot, in my understand, the function under a function can use >>> its father's type and without convert to templates, and can you explain >>> more about why there is a make sort stable commet at the second picture >>> which is the code in the book i download from ats lang web >>> >>> 在2025年6月4日星期三 UTC+8 06:53:07<gmhwxi> 写道： >>> >>>> For instance, I see the following kind of recursive templates very >>>> often: >>>> >>>> fun{a:t@ype} >>>> list0_length(xs: list0(a)): int = >>>> case+ xs of >>>> | list0_nil() => 0 >>>> | list0_cons(x1, xs) => 1 + list0_length<a>(xs) >>>> >>>> This kind of code may be working, but should be avoided. Instead, >>>> one can replace it with the following code: >>>> >>>> fun{a:t@ype} >>>> list0_length(xs: list0(a)): int = >>>> length(xs) where >>>> { >>>> fun length(xs: list0(a)): int = >>>> case+ xs of >>>> | list0_nil() => 0 >>>> | list0_cons(_, xs) => 1 + length(xs) >>>> } >>>> >>>> BTW, recursive templates, by default, are not supported in ATS3. >>>> >>>> On Tuesday, June 3, 2025 at 6:45:35 PM UTC-4 gmhwxi wrote: >>>> >>>>> >>>>> I see that you wrote some ATS2 code. >>>>> >>>>> Unfortunately, there is not much written documentation on ATS2 (or ATS >>>>> in general). >>>>> It is often difficult for one to immediately figure out how various >>>>> features in ATS2 should >>>>> be used. >>>>> >>>>> In your code, you have some recursive templates (e.g., your template >>>>> list0RevHelper is >>>>> recursive). >>>>> >>>>> In general, templates should *not* be recursive. In this case, >>>>> list0RevHelper does not need >>>>> to be a template in the first place. Just turn it into an ordinary >>>>> (recursive) function. Then I believe >>>>> your problem will go away. >>>>> >>>>> --Hongwei >>>>> >>>>> >>>>> >>>>> On Monday, June 2, 2025 at 8:23:32 PM UTC-4 jin wrote: >>>>> >>>>>> when i t[image: 2025-06-03 07.57.11.png]ry to use list0_rev >>>>>> (list0_tail (listo_rev lista)) as initlist function, there notice segment >>>>>> default at runtime, so i change function to the picture below, error >>>>>> disappear, i want to know what cause the error, is there any relation >>>>>> between the error and the "make stable" of the second picture, which >>>>>> seems >>>>>> like not nessesary, that's really confuse[image: 2025-06-03 >>>>>> 07.57.11.png] >>>>>> [image: 2025-06-03 08.02.32.png][image: 2025-06-03 07.57.11.png] >>>>> >>>>> -- > You received this message because you are subscribed to the Google Groups > "ats-lang-users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion visit > https://groups.google.com/d/msgid/ats-lang-users/1de3e545-af9b-4bcd-b636-1c29823a0447n%40googlegroups.com > <https://groups.google.com/d/msgid/ats-lang-users/1de3e545-af9b-4bcd-b636-1c29823a0447n%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "ats-lang-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion visit https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLraVJUpOOGzR6fcmxLkB51h098w-g6T5HURNo89Ho_T7w%40mail.gmail.com.
