> 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.sag...@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@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@lists.science.uu.nl > > http://lists.science.uu.nl/mailman/listinfo/nix-dev > > -- Eric Sagnes サニエ エリック _______________________________________________ nix-dev mailing list nix-dev@lists.science.uu.nl http://lists.science.uu.nl/mailman/listinfo/nix-dev