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

[Eric Sagnes]

> Maybe this should be added to the standard library?

There is a sort function in the builtins [1], and one in Nix in the list
functions [2].

[1] http://nixos.org/nix/manual/#ssec-builtins
[2] https://github.com/NixOS/nixpkgs/blob/master/lib/lists.nix#L298

On Fri, Apr 15, 2016 at 02:53:49PM +1000, Roger Qiu wrote:
> 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
> >

-- 
Eric Sagnes
サニエ エリック