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