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

[Eric Sagnes]

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 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.



-- 
Eric Sagnes
サニエ エリック