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

[Matthias Beyer]

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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
Url : http://lists.science.uu.nl/pipermail/nix-dev/attachments/20160413/16d999f1/attachment.bin