[Nix-dev] Trying to implement quicksort in nix...

[Roger Qiu]

Maybe this should be added to the standard library?
On 15/04/2016 12:36 PM, "Eric Sagnes" <eric.sagnes at gmail.com> wrote:

> Sorry, I just noticed that my example is wrong because it is missing
> recursion.
> The `in low ++ [x] ++ high;` should be `in qs low ++ [x] ++ qs high;`.
>
> For fun, I added it to rosetta code [1] :)
>
> [1] http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Nix
>
> On Wed, Apr 13, 2016 at 04:01:59PM +0200, Matthias Beyer wrote:
> > Ah, okay... there was my fault. Thank you!
> >
> > On 13-04-2016 22:08:08, Eric Sagnes wrote:
> > > The following seems to work:
> > >
> > > ```
> > > let
> > >   qs = l:
> > >     if l == [] then []
> > >     else
> > >       with builtins;
> > >       let x  = head l;
> > >           xs = tail l;
> > >           low  = filter (a: a < x)  xs;
> > >           high = filter (a: a >= x) xs;
> > >       in low ++ [x] ++ high;
> > > in
> > >   qs [3 4 1 2]
> > > ```
> > >
> > > I think you get infinite recursion because `xs` in the else branch is
> > > refering to the whole list and not the tail.
> > >
> > > On Wed, Apr 13, 2016 at 02:39:22PM +0200, Matthias Beyer wrote:
> > > > Hi,
> > > >
> > > > I struggle implementing quicksort in the nix expression language...
> maybe one of
> > > > you gurus can help me? Here's what I have so far:
> > > >
> > > >     let
> > > >         len    = xs: builtins.length xs;
> > > >         fst    = xs: builtins.head xs;
> > > >         lower  = x: xs: builtins.filter (a: a < x) xs;
> > > >         higher = x: xs: builtins.filter (a: a >= x) xs;
> > > >
> > > >         qs = xs:
> > > >             if (0 == (len xs)) then []
> > > >             else (qs (lower (fst xs) xs)) ++ (fst xs) ++ (qs (higher
> (fst xs) xs));
> > > >     in
> > > >         qs [3 4 1 2]
> > > >
> > > > Any ideas why I'm getting a stackoverflow due to infinite recursion?
> > > >
> > > > --
> > > > Mit freundlichen Grüßen,
> > > > Kind regards,
> > > > Matthias Beyer
> > > >
> > > > Proudly sent with mutt.
> > > > Happily signed with gnupg.
> > >
> > >
> > >
> > > > _______________________________________________
> > > > nix-dev mailing list
> > > > nix-dev at lists.science.uu.nl
> > > > http://lists.science.uu.nl/mailman/listinfo/nix-dev
> > >
> > >
> > > --
> > > Eric Sagnes
> > > サニエ エリック
> >
> > --
> > Mit freundlichen Grüßen,
> > Kind regards,
> > Matthias Beyer
> >
> > Proudly sent with mutt.
> > Happily signed with gnupg.
>
>
>
> --
> Eric Sagnes
> サニエ エリック
> _______________________________________________
> nix-dev mailing list
> nix-dev at lists.science.uu.nl
> http://lists.science.uu.nl/mailman/listinfo/nix-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.science.uu.nl/pipermail/nix-dev/attachments/20160415/aac796fd/attachment.html