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