Re: QuickSort on ranges
I posted some sum-up on my github. https://preview.tinyurl.com/y6sprdbq
Re: QuickSort on ranges
On 10/4/20 6:50 AM, jerome wrote: Thanks you very much Ali, I will try to wrap my head around your inputs, and get a better understanding of ranges in the process. I feel there is a lot of power in D ranges, and like the hammer of Thor, I am not worthy yet :) Just to elaborate a bit further: Templates work by pattern matching. When you say quickSort(T)(T[] r) You are saying, match the parameter T[] to what is passed, and if it's a match, set T to the part of the parameter that matches. Therefore: int[] => T = int ubyte[] => T = ubyte But if you leave off the array brackets: quickSort(T)(T r) Now T matches *any type* that you pass in, including ranges. Most range functions use templates because there is no supertype for ranges. They are checked by trying to compile the range primitives on them. How you do more advanced checks other than pattern matching, is to use a template constraint, as Ali suggests. In fact, since you are just using std.algorithm.pivotPartition, you can just look at the constraints it uses: if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasAssignableElements!Range) -Steve
Re: QuickSort on ranges
Thanks you very much Ali, I will try to wrap my head around your inputs, and get a better understanding of ranges in the process. I feel there is a lot of power in D ranges, and like the hammer of Thor, I am not worthy yet :)
Re: QuickSort on ranges
On 9/12/20 11:25 AM, jerome wrote:
>
> import std.stdio : writeln;
> import std.algorithm.sorting;
>
> pure void quickSort(T) (T[] r)
> {
>if (r.length > 1)
>{
> size_t p = pivotPartition(r, r.length-1); //r[$-1] is swapped
to r[p]
>
> quickSort( r[ 0..p ] );
> quickSort( r[ p+1..$ ] );
>}
> }
>
> void main()
> {
>int[] arr = [9,7, 4 , 8, 5, 3, 1];
>quickSort!(int)(arr);
// No need to specify int there because it's deduced from
// the parameter. Pretty cool: :)
quickSort(arr);
>writeln("arr : ", arr );
>
> }
>
>
> I spent some time understanding "ranges", but at the end I am surprised
> I didn't use them. At the beginning I wrote something like quickSort(
> Range r ) and tried randomaccessrange etc but I didn't manage to make it
> work.
Agreed. The most common range type is InputRange and most algorithms
don't require more than that. Combined with slices being the most common
RandomAccessRange, it's not obvious why one needs to write algorithms
that require RandomAccessRange.
So, your algorithm is very useful already but as you said, it can't work
with all RandomAccessRanges:
import std.range;
auto arr2 = iota(5).array;
quickSort(chain(arr, arr2));// <-- Compilation error
chain() is a very smart algorithm that return a range type that can be a
RandomAccessRange if all the ranges given to it are RandomAccessRanges.
(Pretty awesome and very practical that we can write ranges like chain()
in D!)
So, to make your algorithm with any RandomAccessRange, we need to change
it like this:
pure void quickSort(R) (R r)// <-- The only change
Now the quickSort(chain(arr, arr2)) expression can be compiled and the
result is awesome too:
// Wow! Your quickSort operated on the elements of two
// separate ranges! :)
writeln(arr);
writeln(arr2);
Optionally, you can put a template constraint on your algorithm to
communicate the fact that it can only work with RandomAccessRanges:
import std.range : isRandomAccessRange;
pure void quickSort(R) (R r)
if (isRandomAccessRange!R)// <-- Here
{
// ...
}
Doing that moves potential compilation errors from your algorithm to the
caller. For example, if they call your algorithm with int[string], they
will get a compilation error saying "you can't call this function with
int[string]".
Ali
QuickSort on ranges
Hi fellow coders, I spent a couple of hours to implement a
working, basic, quicksort. Practicing D. It finally boils down to
that (intent to use the std, not to rewrite swap, etc):
import std.stdio : writeln;
import std.algorithm.sorting;
pure void quickSort(T) (T[] r)
{
if (r.length > 1)
{
size_t p = pivotPartition(r, r.length-1); //r[$-1] is
swapped to r[p]
quickSort( r[ 0..p ] );
quickSort( r[ p+1..$ ] );
}
}
void main()
{
int[] arr = [9,7, 4 , 8, 5, 3, 1];
quickSort!(int)(arr);
writeln("arr : ", arr );
}
I spent some time understanding "ranges", but at the end I am
surprised I didn't use them. At the beginning I wrote something
like quickSort( Range r ) and tried randomaccessrange etc but I
didn't manage to make it work.
My question is, is there a way to write this with "ranges" as the
argument, or does this concept of slices with the [] notation
takes precedence somehow on the concept of ranges, in this
particular case?
2) how would YOU write it? Using std or not.
3) any comment/code correction welcome, I am learning :)
cheers
J
Re: Quicksort Variants
On Tuesday, 8 July 2014 at 20:50:01 UTC, Nordlöw wrote: Also related: http://forum.dlang.org/thread/eaxcfzlvsakeucwpx...@forum.dlang.org#post-mailman.2809.1355844427.5162.digitalmars-d:40puremagic.com
Re: Quicksort Variants
On Tuesday, 8 July 2014 at 20:50:01 UTC, Nordlöw wrote: I recall that Python's default sorting algorithm is related to this, right? https://en.wikipedia.org/wiki/Timsort
Quicksort Variants
After having read
http://togototo.wordpress.com/2014/06/20/the-magic-forest-problem-revisited-rehabilitating-java-with-the-aid-of-d/
I stared at
forest_t[] quickSort(forest_t[] fors) pure nothrow {
if (fors.length >= 2) {
auto parts = partition3!(forLessThan)(fors, fors[$ / 2]);
parts[0].quickSort;
parts[2].quickSort;
}
return fors;
}
for a while. Could somebody explain why this gave such a speed
boost? To my knowledge it is an optimization which gives extra
speedup when fors is already partially sorted right?
Are there any plans to merge this optimization into existing or
new sorting algorithms in Phobos?
I recall that Python's default sorting algorithm is related to
this, right?
Re: Implementing Haskell's Type-Level Quicksort in D
On Fri, Feb 14, 2014 at 3:24 PM, bearophile wrote: > Meta: > > >> While it is heavier than Haskell's syntax, I have been consistently and >> pleasantly surprised by how powerful D's template pattern matching is (bugs >> notwithstanding). I wonder how well-known this is outside this mailing >> list... Well, I have a tutorial, but I admit it being somewhat incomplete and now partially out of date (2012). > I keep reading blog posts that use Haskell and present supposed "marvels", > using very complex things, that can be routinely done in D, and with less > complexity for the brain of the programer, often leading to faster code and > equally safe :-) So while I like several parts of Haskell, it's sometimes > over-hyped (while D is nearly invisible). Same here, same here! But you have to admit some of their examples are pretty damn elegant :) I remember doing some Haskell -> D translation (a bit like what Meta is doing), making it work, doing the happy-happy dance, and then suddenly realizing I could do the same compile-time computation in one line of D ;)
Re: Implementing Haskell's Type-Level Quicksort in D
Meta: While it is heavier than Haskell's syntax, I have been consistently and pleasantly surprised by how powerful D's template pattern matching is (bugs notwithstanding). I wonder how well-known this is outside this mailing list... I keep reading blog posts that use Haskell and present supposed "marvels", using very complex things, that can be routinely done in D, and with less complexity for the brain of the programer, often leading to faster code and equally safe :-) So while I like several parts of Haskell, it's sometimes over-hyped (while D is nearly invisible). Bye, bearophile
Re: Implementing Haskell's Type-Level Quicksort in D
On Friday, 14 February 2014 at 06:05:08 UTC, Philippe Sigaud
wrote:
`alias` is just a bit of syntax sugar, it does not (at least for
2.064) have the same power than fully defining a template and
the `is(...)` expression.
Right. What I was saying, however, is it is strange to me that
this code will compile:
alias numPred(N: Succ!a, a) = a;
struct Number(a)
if (is(a == Zero) || is(a == Succ!x, x))
{}
enum numValue(N: Number!Zero) = 0;
enum numValue(N: Number!x, x) = numValue!(Number!(numPred!x)) + 1;
assert(numValue!(Number!Zero) == 0);
assert(numValue!(Number!Four) == 4);
While this code won't:
struct Nil{}
struct Cons(a, b) {}
alias list1 = Cons!(Three, Cons!(Two, Cons!(Four, Cons!(One,
Nil;
alias numlHead(L: Cons!(a, b), a, b) = a;
alias numlTail(L: Cons!(a, b), a, b) = b;
assert(is(numlHead!list1 == Three));
Since list1 is a roughly similar construction to
Number!(Succ!(Succ!(Succ!(Succ!Zero, it is surprising to me
that the template matching system can correctly destructure the
latter, while not the former. This is obviously a bug, I'm just
surprised that it exists.
So yes, D does not have Haskell nice syntax for pattern
matching. You can do some pattern matching using templates,
but it tends to be a bit heavier than ML/F#/Haskell.
While it is heavier than Haskell's syntax, I have been
consistently and pleasantly surprised by how powerful D's
template pattern matching is (bugs notwithstanding). I wonder how
well-known this is outside this mailing list...
(Some would say that at least D does not force you to encode
numbers as succ/zero list, since you can use numbers directly
as template args, but that's another story).
Sure, but I want to stay as close to the original Haskell as
possible (and Peano Numbers are pretty damn cool anyway).
Re: Implementing Haskell's Type-Level Quicksort in D
Philippe Sigaud: So yes, D does not have Haskell nice syntax for pattern matching. I'd like some of such syntax for templates (and a little different syntax added to match structs inside switch statements: https://d.puremagic.com/issues/show_bug.cgi?id=596 ). Bye, bearophile
Re: Implementing Haskell's Type-Level Quicksort in D
On Fri, Feb 14, 2014 at 3:54 AM, Meta wrote: > It seems strange that it would choke now, as Cons is a struct. Therefore, > Cons!(Three, ...) should create a new type, and `L: Cons!(a, b), a, b` > shouldn't be any trouble to destructure into two types, `Three` and > `Cons!(Two, ...)`. It had no problem handling the Succ and Number struct > templates I defined. `alias` is just a bit of syntax sugar, it does not (at least for 2.064) have the same power than fully defining a template and the `is(...)` expression. So yes, D does not have Haskell nice syntax for pattern matching. You can do some pattern matching using templates, but it tends to be a bit heavier than ML/F#/Haskell. (Some would say that at least D does not force you to encode numbers as succ/zero list, since you can use numbers directly as template args, but that's another story).
Re: Implementing Haskell's Type-Level Quicksort in D
On Friday, 14 February 2014 at 02:41:12 UTC, bearophile wrote:
Meta:
alias list1 = Cons!(Three, Cons!(Two, Cons!(Four, Cons!(One,
Nil;
alias numlHead(L: Cons!(a, b), a, b) = a;
alias numlTail(L: Cons!(a, b), a, b) = b;
But the compiler is complaining loudly about a mismatch:
/d43/f234.d(39): Error: template instance numlHead!(list1)
does not match template declaration numlHead(L : Cons!(a, b),
a, b)
See a recent thread of mine:
http://forum.dlang.org/thread/vlwgufdlpjgewpnnh...@forum.dlang.org
Currently I think you have to accept types and aliases with a
regular template syntax, and verify the types and kinds with
template constraints. Something like (untested):
template numlTail(C) if (TemplateOf!(C, Cons)) {
alias numlTail = TemplateArgsOf!(C)[1];
}
Bye,
bearophile
It seems strange that it would choke now, as Cons is a struct.
Therefore, Cons!(Three, ...) should create a new type, and `L:
Cons!(a, b), a, b` shouldn't be any trouble to destructure into
two types, `Three` and `Cons!(Two, ...)`. It had no problem
handling the Succ and Number struct templates I defined.
Re: Implementing Haskell's Type-Level Quicksort in D
Meta:
alias list1 = Cons!(Three, Cons!(Two, Cons!(Four, Cons!(One,
Nil;
alias numlHead(L: Cons!(a, b), a, b) = a;
alias numlTail(L: Cons!(a, b), a, b) = b;
But the compiler is complaining loudly about a mismatch:
/d43/f234.d(39): Error: template instance numlHead!(list1) does
not match template declaration numlHead(L : Cons!(a, b), a, b)
See a recent thread of mine:
http://forum.dlang.org/thread/vlwgufdlpjgewpnnh...@forum.dlang.org
Currently I think you have to accept types and aliases with a
regular template syntax, and verify the types and kinds with
template constraints. Something like (untested):
template numlTail(C) if (TemplateOf!(C, Cons)) {
alias numlTail = TemplateArgsOf!(C)[1];
}
Bye,
bearophile
Re: Implementing Haskell's Type-Level Quicksort in D
Coming back to this after a few days. I got a bit farther, but I'm running into trouble with the template args pattern matching. I'd like to turn this code: list1 :: Cons Three (Cons Two (Cons Four (Cons One Nil))) list1 = undefined numlHead :: Cons a b -> a numlHead = const undefined numlTail :: Cons a b -> b numlTail = const undefined' Into this D code: alias list1 = Cons!(Three, Cons!(Two, Cons!(Four, Cons!(One, Nil; alias numlHead(L: Cons!(a, b), a, b) = a; alias numlTail(L: Cons!(a, b), a, b) = b; But the compiler is complaining loudly about a mismatch: /d43/f234.d(39): Error: template instance numlHead!(list1) does not match template declaration numlHead(L : Cons!(a, b), a, b)
Re: Implementing Haskell's Type-Level Quicksort in D
alias One = Typedef!(Succ!Zero); alias Two = Typedef!(Succ!One); alias Three = Typedef!(Succ!Two); alias Four = Typedef!(Succ!Three); Note that you need a "cookie" for those Typedefs, otherwise they are not useful. They are different types, so my comment is wrong :-) I don't understand why you have used Typedef there. Bye, bearophile
Re: Implementing Haskell's Type-Level Quicksort in D
On Tuesday, 11 February 2014 at 19:13:01 UTC, Philippe Sigaud wrote: On Mon, Feb 10, 2014 at 6:12 PM, Meta wrote: I'm trying to write a D implementation of Haskell's "type level quicksort"[0], but I'm already running into problems with std.typecons.Typedef. I have tried to translate this Haskell code: alias One = Typedef!(Succ!Zero); alias Two = Typedef!(Succ!One); alias Three = Typedef!(Succ!Two); alias Four = Typedef!(Succ!Three); Did you try just using: alias One = Succ!Zero; alias Two = Succ!One; alias Three = Succ!Two; alias Four = Succ!Three; ? I remember having fun implementing type-level addition and multiplication using D and this Peano construct, so Quicksort is probably possible. I have tried once before only semi-seriously, and using just a bare alias was my initial strategy. It didn't work for some reason, and I can't really remember why. Maybe I'll give it another try and just drop the Typedef.
Re: Implementing Haskell's Type-Level Quicksort in D
On Mon, Feb 10, 2014 at 6:12 PM, Meta wrote: > I'm trying to write a D implementation of Haskell's "type level > quicksort"[0], but I'm already running into problems with > std.typecons.Typedef. I have tried to translate this Haskell code: > alias One = Typedef!(Succ!Zero); > alias Two = Typedef!(Succ!One); > alias Three = Typedef!(Succ!Two); > alias Four = Typedef!(Succ!Three); Did you try just using: alias One = Succ!Zero; alias Two = Succ!One; alias Three = Succ!Two; alias Four = Succ!Three; ? I remember having fun implementing type-level addition and multiplication using D and this Peano construct, so Quicksort is probably possible.
Re: Implementing Haskell's Type-Level Quicksort in D
Note that you need a "cookie" for those Typedefs, otherwise they are not useful. Unless this gets implemented: http://d.puremagic.com/issues/show_bug.cgi?id=12100 See also: http://d.puremagic.com/issues/show_bug.cgi?id=11828 Bye, bearophile
Re: Implementing Haskell's Type-Level Quicksort in D
Meta: alias One = Typedef!(Succ!Zero); alias Two = Typedef!(Succ!One); alias Three = Typedef!(Succ!Two); alias Four = Typedef!(Succ!Three); Note that you need a "cookie" for those Typedefs, otherwise they are not useful. Unless this gets implemented: http://d.puremagic.com/issues/show_bug.cgi?id=12100 Bye, bearophile
Re: Implementing Haskell's Type-Level Quicksort in D
On Monday, 10 February 2014 at 17:12:11 UTC, Meta wrote: I tried defining a static opCall in the Zero struct that doesn't take any arguments, but that didn't make a difference. I'm guessing this is a bug with Typedef, but does anyone have an idea of where that bug might be? I would say it's not Typedef's fault, but std.typecons.Proxy's one. It has issues forwarding through opCall and opDispatch: https://d.puremagic.com/issues/show_bug.cgi?id=11947 I'm currently working on a fix: https://github.com/D-Programming-Language/phobos/pull/1914 Looks like a case for static opCall should also be covered.
Implementing Haskell's Type-Level Quicksort in D
I'm trying to write a D implementation of Haskell's "type level
quicksort"[0], but I'm already running into problems with
std.typecons.Typedef. I have tried to translate this Haskell code:
data Zero
data Succ a
-- booleans
data True
data False
-- lists
data Nil
data Cons a b
-- shortcuts
type One = Succ Zero
type Two = Succ One
type Three = Succ Two
type Four = Succ Three
To this code in D:
import std.typecons;
struct Zero {}
struct Succ(a) {}
struct True {}
struct False {}
struct Nil {}
struct Cons(a, b) {}
alias One = Typedef!(Succ!Zero);
alias Two = Typedef!(Succ!One);
alias Three = Typedef!(Succ!Two);
alias Four = Typedef!(Succ!Three);
void main()
{
auto test = Four();
}
But I'm getting a compiler error when actually trying to
construct a Four:
Error: template std.typecons.Typedef!(Succ!(Zero),
Succ()).Typedef.Proxy!(Typedef_payload).opCall does not match any
function template declaration.
Candidates are:
std.typecons.Typedef!(Succ!(Zero),
Succ()).Typedef.Proxy!(Typedef_payload).opCall(this X,
Args...)(auto ref Args args)
I tried defining a static opCall in the Zero struct that doesn't
take any arguments, but that didn't make a difference. I'm
guessing this is a bug with Typedef, but does anyone have an idea
of where that bug might be?
1.
http://www.haskell.org/haskellwiki/Type_arithmetic#An_Advanced_Example_:_Type-Level_Quicksort
Re: Phobos orthogonality [Was: Re: quickSort]
On Wednesday, September 14, 2011 14:36 bearophile wrote: > Jonathan M Davis: > > So, basically, you just want to shorten your code by wrapping array(func) > > in a afunc function, and you think that this happens enough with map and > > filter enough to merit putting these functions into Phobos. > > There is also the point 3) that you have not seen, plus the notes about > Haskell Prelude design. I did see it. I read your entire post, and I don't see anything that IMHO justifies adding amap or afilter. Yes, I can see why you would want to have and use amap and afilter. They aren't worthless. But they just don't add enough value to be worth adding to Phobos. And I'd be very surprised if Andrei disagreed with me based on what he's said about similar stuff. It was an uphill battle just to get him to allow drop to be added to std.range, and that actually allows code to be written in a different style, whereas amap and afilter pretty much just reduce the number of characters that a particular statement requires. Yes, the resulting code may look cleaner, but that's it. There's no real functional difference in the resulting code. It just doesn't add enough value to make it into Phobos. - Jonathan M Davis
Re: Phobos orthogonality [Was: Re: quickSort]
Jonathan M Davis: > So, basically, you just want to shorten your code by wrapping array(func) in > a > afunc function, and you think that this happens enough with map and filter > enough to merit putting these functions into Phobos. There is also the point 3) that you have not seen, plus the notes about Haskell Prelude design. Bye, bearophile
Re: Phobos orthogonality [Was: Re: quickSort]
On Wednesday, September 14, 2011 07:46:37 bearophile wrote: > Jonathan M Davis: > > What would that gain you over passing the result of map or filter to > > std.array.array? > > 1) The code gets shorter > 2) The code gets a bit less noisy, because () add noise. > 3) You use a single function instead of two, so you reduce the number of > chunks your brain has to manage. A human brain is able to manage a very > limited number of chunks at the same time (about 7). An expert programmer > is able to merge array(map()) into a single chunk, but this requires a bit > of training and time. 4) Maybe you are able to reduce the abstraction > penalty for the compiler, reducing the amount of code compiled. (But this > probably will not happen because amap will probably be just implemented > with an array(map()) to reduce library code and time to write to write it). > 5) The lazy result of map is quite useful. But in a large amount of > situations in D you can't use a lazy result, you need an array (this is not > true in Haskell). So in practice about half the time I need a map, I have > to apply array() on it. So amap is a very common pattern in D. 6) In > std.parallelism there is already an map/amap pair: > http://www.d-programming-language.org/phobos/std_parallelism.html#amap > So for the D programmer it's not a significant burden to have the same > functions in std.algorithm, with the same names and same purposes. > > Orthogonality is overrated in Phobos. If you take a look at functional > languages where the use of higher order functions is common, like Haskell, > you see standard functions that are the composition of common functions. > Haskell designers have a large experience on the usage of higher order > functions. This is the Haskell Prelude (similar to the D object module): > > http://www.haskell.org/onlinereport/standard-prelude.html > > As example it contains both map and concatMap (concatMap is absent in Phobos > still, but it will be useful to have). > > The definition of concatMap is just: > > concatMap :: (a -> [b]) -> [a] -> [b] > concatMap f = concat . map f > > In practice in Haskell you are allowed to write concatMap just like this: > > concatMap = concat.map > > This means concatMap is just using three functions, concat, map and dot > (that is the composition function). Do you know why such simple function is > included in the Prelude, despite it essentially saves just one character > (the dot)? Because using a concat on the result of map is a very common > pattern in Haskell code. So packing them in a single name allows the mind > of the programmer to think of it as a single entity, and allows a bit > higher thinking while you program. > > This is why I think amap/afilter are worth adding to Phobos. I did have them > in my dlibs1 and I have used them many times. So, basically, you just want to shorten your code by wrapping array(func) in a afunc function, and you think that this happens enough with map and filter enough to merit putting these functions into Phobos. Yeah, I don't see that happening. It's not impossible, but there are a number of functions in Phobos which return lazy ranges. It's not at all reasonable to have duplicate versions of them all just to shorten a bit of code. And if anything, Andrei has been looking at heightening the bar for how much a function has to add to make it into std.algorithm or std.range. He feels that there's arguably too much duplication already. And when all a function does is making so that you're doing afunc(r) instead of array(func(r)), there's no way that that's getting in. - Jonathan M Davis
Phobos orthogonality [Was: Re: quickSort]
Jonathan M Davis: > What would that gain you over passing the result of map or filter to > std.array.array? 1) The code gets shorter 2) The code gets a bit less noisy, because () add noise. 3) You use a single function instead of two, so you reduce the number of chunks your brain has to manage. A human brain is able to manage a very limited number of chunks at the same time (about 7). An expert programmer is able to merge array(map()) into a single chunk, but this requires a bit of training and time. 4) Maybe you are able to reduce the abstraction penalty for the compiler, reducing the amount of code compiled. (But this probably will not happen because amap will probably be just implemented with an array(map()) to reduce library code and time to write to write it). 5) The lazy result of map is quite useful. But in a large amount of situations in D you can't use a lazy result, you need an array (this is not true in Haskell). So in practice about half the time I need a map, I have to apply array() on it. So amap is a very common pattern in D. 6) In std.parallelism there is already an map/amap pair: http://www.d-programming-language.org/phobos/std_parallelism.html#amap So for the D programmer it's not a significant burden to have the same functions in std.algorithm, with the same names and same purposes. Orthogonality is overrated in Phobos. If you take a look at functional languages where the use of higher order functions is common, like Haskell, you see standard functions that are the composition of common functions. Haskell designers have a large experience on the usage of higher order functions. This is the Haskell Prelude (similar to the D object module): http://www.haskell.org/onlinereport/standard-prelude.html As example it contains both map and concatMap (concatMap is absent in Phobos still, but it will be useful to have). The definition of concatMap is just: concatMap :: (a -> [b]) -> [a] -> [b] concatMap f = concat . map f In practice in Haskell you are allowed to write concatMap just like this: concatMap = concat.map This means concatMap is just using three functions, concat, map and dot (that is the composition function). Do you know why such simple function is included in the Prelude, despite it essentially saves just one character (the dot)? Because using a concat on the result of map is a very common pattern in Haskell code. So packing them in a single name allows the mind of the programmer to think of it as a single entity, and allows a bit higher thinking while you program. This is why I think amap/afilter are worth adding to Phobos. I did have them in my dlibs1 and I have used them many times. Bye, bearophile
Re: quickSort
On Wednesday, September 14, 2011 06:09:52 bearophile wrote: > %u: > > i have qustion why filter can't return int[] > > Because a lazy filter is handy, you often don't need a real array result, a > lazy sequence is enough. A lazy sequence avoids the memory allocation of > the output array. In D programs often the slowest parts are the memory > allocations. On the other hand I have asked to add amap/afilter functions > that return arrays. Andrei has not answered about this yet. What would that gain you over passing the result of map or filter to std.array.array? - Jonathan M Davis
Re: quickSort
%u: > i have qustion why filter can't return int[] Because a lazy filter is handy, you often don't need a real array result, a lazy sequence is enough. A lazy sequence avoids the memory allocation of the output array. In D programs often the slowest parts are the memory allocations. On the other hand I have asked to add amap/afilter functions that return arrays. Andrei has not answered about this yet. Bye, bearophile
Re: quickSort
On Wednesday, September 14, 2011 05:43:37 %u wrote: > i have qustion why filter can't return int[] > and if lambda return the last Expression without return keyword it would > much cleaner filter can't return int[]. filter does not alter the original array. It returns a new range with only the elements which match the predicate. For it to return int[], it would have to allocate a new array, and that would be inefficient. Instead, it returns a new range which wraps the original array. If you want to actually allocate a new array, then just pass the result of filter to std.array.array. As for the lambda syntax, there has been some discussion of simplifying it, but there are potential issues with it, and so for the moment, it's staying as-is. - Jonathan M Davis
Re: quickSort
i have qustion why filter can't return int[] and if lambda return the last Expression without return keyword it would much cleaner
Re: quickSort
On 09/14/2011 04:12 AM, Timon Gehr wrote:
On 09/14/2011 03:34 AM, hdsh wrote:
this my try
int[] quickSort(int[] arr) {
int[] result = quickSort(filter!(arr< arr[0])(arr)) ~ arr[0] ~
quickSort(filter!(arr> arr[0])(arr));
}
but it fail to compile
Note that this approach is an inefficient way of implementing a sorting
routine.
This works:
int[] quickSort(int[] arr) {
if(!arr.length) return [];
return quickSort(array(filter!((a){return a < arr[0];})(arr))) ~ arr[0] ~
quickSort(array(filter!((a){return a > arr[0];})(arr)));
}
Sry, accidentally sent a first draft. This is how it should have looked.
int[] quickSort(int[] arr) {
if(!arr.length) return [];
return quickSort(array(filter!((a){return a < arr[0];})(arr))) ~
arr[0] ~
quickSort(array(filter!((a){return a >= arr[0];})(arr[1..$])));
}
I'll go quickly through how I fixed it:
int[] quickSort(int[] arr) {
if(!arr.length) return []; // base case for recursion
return // return statement for giving back a result
quickSort(array( // turn the lazy filter range into an array
filter!(
(a){return a < arr[0];} // delegate literal passed to filter
)(arr))) ~ arr[0] ~
quickSort(array(filter!(
(a){return a >= arr[0];} //allow multiple elements that are equal to the
pivot element
)(arr[1..$]))); // only include the pivot once
}
If you have particular questions about this solution, feel free to ask.
Re: quickSort
On 09/14/2011 03:34 AM, hdsh wrote:
this my try
int[] quickSort(int[] arr) {
int[] result = quickSort(filter!(arr< arr[0])(arr)) ~ arr[0] ~
quickSort(filter!(arr> arr[0])(arr));
}
but it fail to compile
Note that this approach is an inefficient way of implementing a sorting
routine.
This works:
int[] quickSort(int[] arr) {
if(!arr.length) return [];
return quickSort(array(filter!((a){return a < arr[0];})(arr))) ~
arr[0] ~
quickSort(array(filter!((a){return a > arr[0];})(arr)));
}
I'll go quickly through how I fixed it:
int[] quickSort(int[] arr) {
if(!arr.length) return []; // base case for recursion
return // return statement for giving back a result
quickSort(array( // turn the lazy filter range into an array
filter!(
(a){return a < arr[0];} // delegate literal passed to filter
)(arr))) ~ arr[0] ~
quickSort(array(filter!(
(a){return a >= arr[0];} //allow multiple elements that are
equal to the pivot element
)(arr[1..$]))); // only include the pivot once
}
If you have particular questions about this solution, feel free to ask.
Re: quickSort
On Wednesday, September 14, 2011 01:34:34 hdsh wrote:
> this my try
>
> int[] quickSort(int[] arr) {
> int[] result = quickSort(filter!(arr < arr[0])(arr)) ~ arr[0] ~
> quickSort(filter!(arr > arr[0])(arr));
> }
>
> but it fail to compile
filter does not return an array. It returns a new range which wraps the
original array. As you iterate over the range, it skips elements which don't
match the predicate. If you want to make an array out of it, you use
std.array.array, but that allocates a new array. But as filter doesn't return
int[], you can't pass its result to your quickSort function, nor can you
concatenate it (if you want to concatenate ranges, you use std.range.chain,
which chains them together without allocating anything - it just goes to each
successive range when iterating over it). Normally, range-based functions are
templated so that they can deal with a variety of range types.
If all you're looking for is a sort function, then you can use
std.algorithm.sort, but if you're just trying to implement quick sort in D,
because you want to implement it in D, then you're going to have to rework how
your algorithm works. Either, you're going to have to templatize it (and use
chain), use array (which would be less than efficient), or you're going to have
to use something other than filter.
Personally, I'd advise reworking it so that it doesn't use filter if you want
it to be efficient. Using std.array.array would work but would be inefficient,
whereas templatizing quickSort might run into trouble. I'm not sure whether
such a recursive templated function would work or not. It would depend on
whether each call to filter required a new template instantiation or not.
In any case, your core problem here is the fact that filter does not return
int[]. It returns a new range type.
- Jonathan M Davis
quickSort
this my try
int[] quickSort(int[] arr) {
int[] result = quickSort(filter!(arr < arr[0])(arr)) ~ arr[0] ~
quickSort(filter!(arr > arr[0])(arr));
}
but it fail to compile
