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: CLI library?
On Tue, 13 Sep 2011 10:59:27 +0300, Dainius (GreatEmerald) wrote: > Is there any library that would allow me to use the extended terminal > features (like coloured backgrounds and custom/multiple resolution > support) that works with D and is not platform-dependent? Something > similar to ncurses? I know that there was a dcurses project, but it > seems that it only works with D1 and the Linux implementation was never > finished to begin with. There isn't a working wrapper of ncurses, and my understanding is there hasn't been anything as fully featured that worked cross platform in any language.
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
Re: Is this a bug?
On Tuesday, September 13, 2011 15:34 Caligo wrote:
> On Tue, Sep 13, 2011 at 4:47 AM, Jonathan M Davis
wrote:
> > On Monday, September 12, 2011 23:15:19 Caligo wrote:
> > > On Mon, Sep 12, 2011 at 10:44 PM, Jonathan M Davis
> >
> > wrote:
> > > > On Monday, September 12, 2011 22:38:25 Caligo wrote:
> > > > > Great. So is it a known bug?
> > > >
> > > > I don't know. You'd have to search bugzilla: d.puremagic.com/issues
> > > >
> > > > - Jonathan M Davis
> > >
> > > Searching bugzilla (horrible technology) is never fun for me, thx.
> >
> > Most search technology sucks on some level. But regardless, if bugs
> > aren't reported, then they're not likely to be fixed. So, if you want to
> > ensure that
> > the bugs that you find get fixed, you need to report them, which for
> > better or
> > worse means using bugzilla.
> >
> > - Jonathan M Davis
>
> *sigh*
> I think you fail to understand my situation.
>
> I don't know anything about D's internals and I know nothing about
> compilers and how they work. If I did, I wouldn't ask on
> digitalmars.D.learn. But, I'll go ahead and bug report this.
>
> http://d.puremagic.com/issues/show_bug.cgi?id=6665
I don't know much about dmd's internals either. But given that you have an
error that you can search for ('/Internal error: ../ztc/cg87.c 202'), it
shouldn't be hard to at least see whether there's anything which is obviously
the same. And if there isn't then, you report it. Understanding how dmd works
isn't really necessary to reporting the bug, and worse case, you end up
reporting a bug which has already been reported, which is better than the bug
never getting reported.
Most bugs where the compiler gives an internal error or an assertion in the
compiler gets triggered get fixed fairly quickly, and even if they don't,
they're not the sort of bug that much of anyone outside of the dmd devs who is
going to have any clue what's going on with the bug. So, it's probably not all
that fruitful to inquire about that sort of bug on any of the newsgroups. For
the most part, the dmd devs don't seem to pay attention to D.Learn, so even if
they would recognize the issue, they wouldn't respond to it in D.Learn. The
odds of them seeing it in D newsgroup are higher, but when it comes to bugs
which are "internal errors" or assertions in the compiler, I'd suggest that
you just do a cursory search in bugzilla and then report them.
Bugs which relate to the language's behavior are much more likely to be
recognized by others in the newsgroups (including D.Learn), so asking about
them can be fruitful, but internal compiler errors and assertions isn't the
sort of thing that people outside of the dmd devs generally recognize.
- Jonathan M Davis
Re: Is this a bug?
On Tue, Sep 13, 2011 at 4:47 AM, Jonathan M Davis wrote: > On Monday, September 12, 2011 23:15:19 Caligo wrote: > > On Mon, Sep 12, 2011 at 10:44 PM, Jonathan M Davis > wrote: > > > On Monday, September 12, 2011 22:38:25 Caligo wrote: > > > > Great. So is it a known bug? > > > > > > I don't know. You'd have to search bugzilla: d.puremagic.com/issues > > > > > > - Jonathan M Davis > > > > Searching bugzilla (horrible technology) is never fun for me, thx. > > Most search technology sucks on some level. But regardless, if bugs aren't > reported, then they're not likely to be fixed. So, if you want to ensure > that > the bugs that you find get fixed, you need to report them, which for better > or > worse means using bugzilla. > > - Jonathan M Davis > *sigh* I think you fail to understand my situation. I don't know anything about D's internals and I know nothing about compilers and how they work. If I did, I wouldn't ask on digitalmars.D.learn. But, I'll go ahead and bug report this. http://d.puremagic.com/issues/show_bug.cgi?id=6665
Re: CLI library?
On 09/13/2011 02:59 AM, Dainius (GreatEmerald) wrote: Is there any library that would allow me to use the extended terminal features (like coloured backgrounds and custom/multiple resolution support) that works with D and is not platform-dependent? Something similar to ncurses? I know that there was a dcurses project, but it seems that it only works with D1 and the Linux implementation was never finished to begin with. I'd like to know as well. Is there no ncurses wrapper that works for dmd2?
Re: Converting Duration to TickDuration
On Tuesday, September 13, 2011 15:45:27 Vladimir Panteleev wrote: > On Tue, 13 Sep 2011 06:27:44 +0300, Jonathan M Davis > > wrote: > > Personally, I'd just Duration far those and not TickDuration. Duration > > is just > > as precise (if not more precise) than TickDuration as long as the system > > ticks > > aren't less than 1 hnsec apart. TickDuration is useful in that it gives > > you > > timing in clock ticks if you need it (e.g. if the system clocks ticks > > were > > faster than 1 ever 1 hnsecs), but in the general case, it doesn't buy > > you > > anything over Duration, and I don't see why it would in your case > > either. > > Maybe something in how you're doing events? > > Well, TickDuration.currSystemTick() returns a TickDuration, so I went with > that all across. I'll be needing to do some conversions at one point or > another, though optimally it'd happen when creating events, and not when > processing them, as that would have less total overhead. That makes some sense. The cast probably should be added to Duration anyway, even if the need is somewhat of an abnormality. And maybe such conversions will end up being more common than I would have thought anyway. - Jonathan M Davis
Re: A question about purity
On Tuesday, September 13, 2011 07:43:55 bearophile wrote:
> Jonathan M Davis:
> > However, Foo.y is not encapsulated
> > by a strongly pure function at all. Other functions can alter alter it.
> > So, it breaks purity.
>
> Thank you for your explanation :-)
>
> So, let's change the situation a bit. If the struct Foo is the only thing
> present in a module (to avoid someone to touch its private members), and
> the y field is "private static" only foo2 is able to touch it. In this case
> isn't foo2 weakly pure?
>
>
> struct Foo {
> private static int y;
> static pure void foo2() {
> Foo.y++;
> }
> }
> void main() {}
Pure functions cannot access mutable static variables. End of story. _That_ is
the definition of pure in D. The terms strong and weakly pure relate only to
whether a particular call to a pure function can be optimized out, and Don
(who created the terms) would like to see the terms die out.
Yes, in this particular situation, if you treat everything in the program as
an argument to the function (which is completely impractical), then you know
that calling foo2 won't break purity. But that's just way too complicated. The
compiler doesn't work that way and never will. And there would be no point in
making it work that way even if it were feasible, because this example is
completely contrived. It's just not going to happen in real life.
- Jonathan M Davis
Re: A question about purity
bearophile Wrote: > So, let's change the situation a bit. If the struct Foo is the only thing > present in a module (to avoid someone to touch its private members), and the > y field is "private static" only foo2 is able to touch it. In this case isn't > foo2 weakly pure? Weakly pure function causes side effect with a lifetime limited to enclosing pure function, changing static data causes side effect which escapes enclosing pure function.
Re: A question about purity
bearophile , dans le message (digitalmars.D.learn:29490), a écrit :
> Jonathan M Davis:
>
>> However, Foo.y is not encapsulated
>> by a strongly pure function at all. Other functions can alter alter it. So,
>> it
>> breaks purity.
>
> Thank you for your explanation :-)
>
> So, let's change the situation a bit. If the struct Foo is the only
> thing present in a module (to avoid someone to touch its private
> members), and the y field is "private static" only foo2 is able to
> touch it. In this case isn't foo2 weakly pure?
No, because you change a variable that is global, even if it is private.
In foo.foo1(), foo is changed, but it can be considered as an argument
and a part of the result of foo1(). You cannot say this for Foo.y.
Here is an example to illustrate what was meant with "encapsulating with
a pure function" :
struct Foo {
int x;
pure int foo1() {
return x++;
}
private static int y;
static pure int foo2() {
return Foo.y++; // not pure: a global variable changes
}
}
pure int test1(Foo foo)
{
auto a = foo.foo1(); // nothing changes outside test1: only the local
// copy of foo changes.
return a;
}
pure int test2()
{
auto b = Foo.foo2(); // error: Foo.y changes
return b;
}
void main()
{
Foo foo;
auto a = test1(foo); // only a copy of foo is changed.
auto b = test1(foo);
assert(a==b); // ok
auto c = test2(); // error: Foo.y changes
auto d = test2();
assert(c==d); // fails if test2 was indeed run twice.
}
Re: Converting Duration to TickDuration
On Tue, 13 Sep 2011 06:27:44 +0300, Jonathan M Davis wrote: Personally, I'd just Duration far those and not TickDuration. Duration is just as precise (if not more precise) than TickDuration as long as the system ticks aren't less than 1 hnsec apart. TickDuration is useful in that it gives you timing in clock ticks if you need it (e.g. if the system clocks ticks were faster than 1 ever 1 hnsecs), but in the general case, it doesn't buy you anything over Duration, and I don't see why it would in your case either. Maybe something in how you're doing events? Well, TickDuration.currSystemTick() returns a TickDuration, so I went with that all across. I'll be needing to do some conversions at one point or another, though optimally it'd happen when creating events, and not when processing them, as that would have less total overhead. -- Best regards, Vladimirmailto:vladi...@thecybershadow.net
Re: A question about purity
Jonathan M Davis:
> However, Foo.y is not encapsulated
> by a strongly pure function at all. Other functions can alter alter it. So,
> it
> breaks purity.
Thank you for your explanation :-)
So, let's change the situation a bit. If the struct Foo is the only thing
present in a module (to avoid someone to touch its private members), and the y
field is "private static" only foo2 is able to touch it. In this case isn't
foo2 weakly pure?
struct Foo {
private static int y;
static pure void foo2() {
Foo.y++;
}
}
void main() {}
Bye,
bearophile
Re: Is this a bug?
On Monday, September 12, 2011 23:15:19 Caligo wrote: > On Mon, Sep 12, 2011 at 10:44 PM, Jonathan M Davis wrote: > > On Monday, September 12, 2011 22:38:25 Caligo wrote: > > > Great. So is it a known bug? > > > > I don't know. You'd have to search bugzilla: d.puremagic.com/issues > > > > - Jonathan M Davis > > Searching bugzilla (horrible technology) is never fun for me, thx. Most search technology sucks on some level. But regardless, if bugs aren't reported, then they're not likely to be fixed. So, if you want to ensure that the bugs that you find get fixed, you need to report them, which for better or worse means using bugzilla. - Jonathan M Davis
CLI library?
Is there any library that would allow me to use the extended terminal features (like coloured backgrounds and custom/multiple resolution support) that works with D and is not platform-dependent? Something similar to ncurses? I know that there was a dcurses project, but it seems that it only works with D1 and the Linux implementation was never finished to begin with.
