www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - quickSort

reply hdsh <asmasm hotmail.com> writes:
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
Sep 13 2011
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Sep 13 2011
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Sep 13 2011
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.

Sep 13 2011
next sibling parent reply %u <asmasm hotmail.com> writes:
i have qustion why filter can't return int[]
and if lambda return  the last Expression without return keyword it would much
cleaner
Sep 13 2011
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
%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
Sep 14 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Sep 14 2011
parent bearophile <bearophileHUGS lycos.com> writes:
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
Sep 14 2011
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Sep 14 2011
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Sep 13 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Sep 14 2011
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Sep 14 2011