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

[Eric Sagnes]

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
サニエ エリック