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

[Eric Sagnes]

> Maybe this should be added to the standard library?

There is a sort function in the builtins [1], and one in Nix in the list
functions [2].

[1] http://nixos.org/nix/manual/#ssec-builtins
[2] https://github.com/NixOS/nixpkgs/blob/master/lib/lists.nix#L298

On Fri, Apr 15, 2016 at 02:53:49PM +1000, Roger Qiu wrote:
> Maybe this should be added to the standard library?
> On 15/04/2016 12:36 PM, "Eric Sagnes"  wrote:
> 
> > 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
> >

-- 
Eric Sagnes
サニエ エリック
___
nix-dev mailing list
nix-dev@lists.science.uu.nl
http://lists.science.uu.nl/mailman/listinfo/nix-dev

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

[Roger Qiu]

Maybe this should be added to the standard library?
On 15/04/2016 12:36 PM, "Eric Sagnes"  wrote:

> 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
>
___
nix-dev mailing list
nix-dev@lists.science.uu.nl
http://lists.science.uu.nl/mailman/listinfo/nix-dev

Re: [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@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

Re: [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@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.


signature.asc
Description: PGP signature
___
nix-dev mailing list
nix-dev@lists.science.uu.nl
http://lists.science.uu.nl/mailman/listinfo/nix-dev

Re: [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@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

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

[Matthias Beyer]

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.


signature.asc
Description: PGP signature
___
nix-dev mailing list
nix-dev@lists.science.uu.nl
http://lists.science.uu.nl/mailman/listinfo/nix-dev