Re: [Challenge] implementing the ambiguous operator in D
I agree with Andrei here, building hypercubes makes more sense, and feels like it has more structure. It also has the nice property that, once you've seen a (n+1)th element of any range then you have already explored the entire product of the first n elements of every range, kind of like how the colex ordering works. But which way would you add the successive shells? Like this?: (00) (01 10 11) (02 12 20 21 22)... i.e. lex order? btw, what are some real-world uses of the cartesian product of infinite ranges? I can't think of any off the top of my head.
Re: [Challenge] implementing the ambiguous operator in D
On 09/07/2010 02:43 AM, Peter Alexander wrote: I agree with Andrei here, building hypercubes makes more sense, and feels like it has more structure. It also has the nice property that, once you've seen a (n+1)th element of any range then you have already explored the entire product of the first n elements of every range, kind of like how the colex ordering works. But which way would you add the successive shells? Like this?: (00) (01 10 11) (02 12 20 21 22)... i.e. lex order? The algorithm builds one hyperplane at a time. At level k, there are n hyperplanes to build, each of which keeps exactly one range positioned on the kth element, and all others iterate from their first up to their kth element. Whenever you reached the corner of the hypercube (all ranges are at the kth position), you start building the next hyperplane. When all other hyperplanes are built, you popFront() the first range, reset all others, and start building the next shell. btw, what are some real-world uses of the cartesian product of infinite ranges? I can't think of any off the top of my head. It's great for various solution-searching algorithms, like the example given (lazily generate solutions to the equation x * y = 8). Even for finite ranges of moderate size, exploring two iota()s in the naive order (keep one fixed and exhaust all others) most often takes a long time to find anything interesting. That's why I think finding a solid method to iterate the cartesian product is important even for finite ranges. Andrei
Re: [Challenge] implementing the ambiguous operator in D
== Quote from Andrei Alexandrescu Yah, per your follow-up post, it's a different problem. It's also a much more difficult one. I convinced myself crossProduct is impossible to implement if one input range and one infinite forward range are simultaneously present. It works with any number of infinite forward ranges, and also with other combinations. I couldn't formalize the exact requirements yet. I must be missing something, because I don't understand how you could possibly take the cross product of any number of infinite ranges (other than to just return the range of (a[0], b[i]) for all (infinitely many) i in b). Note that I'm assuming you mean cartesian product, rather than cross product; I've never heard cross product used in the context of sets.
Re: [Challenge] implementing the ambiguous operator in D
Peter Alexander peter.alexander...@gmail.com wrote: I must be missing something, because I don't understand how you could possibly take the cross product of any number of infinite ranges (other than to just return the range of (a[0], b[i]) for all (infinitely many) i in b). Note that I'm assuming you mean cartesian product, rather than cross product; I've never heard cross product used in the context of sets. Quite simple - the result is also an infinte range (infinitely infinite, if you will :p ), that is lazily calculated. And yes, Cartesian product is exactly what we're talking about. -- Simen
Re: [Challenge] implementing the ambiguous operator in D
Andrei Alexandrescu seewebsiteforem...@erdani.org wrote:
I convinced myself crossProduct is impossible to implement if one input
range and one infinite forward range are simultaneously present. It
works with any number of infinite forward ranges, and also with other
combinations. I couldn't formalize the exact requirements yet.
This is indeed correct. Now, I have found a working algorithm (it works
on paper, I swear!), but I can't seem to get it to work in code.
Special cases come for input ranges - I will not consider those. All
forward ranges can be treated the same, regardless of infiniteness.
We need to keep track of the active ranges, and the initial versions of
those (i.e. those passed to the constructor). In addition, we need to
keep the position of each range, probably as a ulong (2 ranges should
give 2^128 combinations, which will not cover the whole solution space
for infinite ranges, but will still be enough for practical purposes).
Also, we must maintain a stack of locked ranges.
The solution is recursive to the number of ranges, and is given in
pseudocode below. Critique is very, VERY welcome!
bool movedEnough( lastUnlocked, lockedStack.peek ) {
if ( lastUnlocked.empty ) {
// If range is empty, don't pop stuff off of it.
return true;
} else if ( lastUnlocked lockedStack.peek ) {
// If the last unlocked range has a higher index than
// the next one the locked stack, check if popping
// would bring us past its position.
return pos[lastUnlocked] = pos[lockedStack.peek];
} else {
// If the last unlocked range has a lower index than
// the next one the locked stack, check if popping
// would bring us to its position.
return pos[lastUnlocked] = pos[lockedStack.peek] -1;
}
}
void popFront( ) {
if ( !unlockedRanges.empty ) {
// If there are unlocked ranges, use the first of them
currentRange = unlockedRanges[0];
} else {
// No unlocked ranges, so unlock one.
currentRange = lastUnlocked = lockedStack.pop;
unlock( lastUnlocked );
while ( movedEnough( lastUnlocked, lockedStack.peek ) ) {
// We have moved far enough along this range, move the next
one up.
currentRange = lastUnlocked = lockedStack.pop;
unlock( lastUnlocked );
if ( // If there are more unlocked ranges below this one
( lastUnlocked != unlockedRanges[$] ) ||
// Or there are no more locked ranges
( lockedStack.empty ) ) {
// Move to the next range. Note that firstAfter would need
to return 0 on being passed $.
currentRange = unlockedRanges.firstAfter( lastUnlocked );
// We have found the next range from which to pop.
break;
}
}
}
// Pop off the found range, the lock it, and reset all unlocked ranges
to their saved states.
currentRange.popFront();
lock(currentRange);
foreach ( unlockedRanges ) {
reset();
}
}
Given cartesian( [1,2], ab ), the result should be as follows:
tuple( 1, 'a' );
tuple( 2, 'a' );
tuple( 2, 'b' );
tuple( 1, 'b' );
And for cartesian( [1,2,3], abc ):
tuple( 1, 'a' );
tuple( 2, 'a' );
tuple( 2, 'b' );
tuple( 1, 'b' );
tuple( 3, 'a' );
tuple( 3, 'b' );
tuple( 3, 'c' );
tuple( 1, 'c' );
tuple( 2, 'c' );
--
Simen
Re: [Challenge] implementing the ambiguous operator in D
Simen kjaeraas simen.kja...@gmail.com wrote: Special cases come for input ranges - I will not consider those. All forward ranges can be treated the same, regardless of infiniteness. Actually, input ranges make everything a lot easier - the best solution is the brute-force stupid solution. -- Simen
Re: [Challenge] implementing the ambiguous operator in D
On 09/06/2010 06:51 AM, Peter Alexander wrote: == Quote from Andrei Alexandrescu Yah, per your follow-up post, it's a different problem. It's also a much more difficult one. I convinced myself crossProduct is impossible to implement if one input range and one infinite forward range are simultaneously present. It works with any number of infinite forward ranges, and also with other combinations. I couldn't formalize the exact requirements yet. I must be missing something, because I don't understand how you could possibly take the cross product of any number of infinite ranges (other than to just return the range of (a[0], b[i]) for all (infinitely many) i in b). Note that I'm assuming you mean cartesian product, rather than cross product; I've never heard cross product used in the context of sets. Yah, thanks for the correction. But probably ranges could be easier seen as vectors than as sets. We've discussed this before. Crosscartesian product of multiple infinite ranges can be easily done by applying Cantor's trick for proving that rational numbers are just as numerous than natural numbers. Google for Cantor with site:digitalmars.com. Andrei
Re: [Challenge] implementing the ambiguous operator in D
Attached latest version. It bugs out with an infinite loop, and I'm too tired to look more at it now. -- Simen autoRefTuple.d Description: Binary data combine.d Description: Binary data
Re: [Challenge] implementing the ambiguous operator in D
== Quote from Andrei Alexandrescu (seewebsiteforem...@erdani.org)'s article We've discussed this before. Crosscartesian product of multiple infinite ranges can be easily done by applying Cantor's trick for proving that rational numbers are just as numerous than natural numbers. Google for Cantor with site:digitalmars.com. Andrei Thanks. For some reason I had just assumed that we would have wanted to provide the product in lexicographic order, but Cantor's trick does seem like a solution to this problem.
Re: [Challenge] implementing the ambiguous operator in D
On 09/06/2010 04:34 PM, Philippe Sigaud wrote: Which gives us: (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3), .. See the indices: sum of 0, then sum of 1, then sum of 2, ... You never get stuck in an infinite line since these diagonal slices are finite. I don't think iteration for constant index sums works with forward ranges - you need bidirectional ranges to go back in one while going forth in another. You need to only move forward in all ranges, or reset them to zero. It helps me a lot to think how I'd lay bricks to fill the first quadrant of an n-dimensional infinite space. If you tried the tensorial product, you'd lay a nice column of bricks, but you'd be busy at it forever because the column would have infinite height. If you try your solution that has constant sums, then you are filling hypersimplexes of increasing size. That's certainly encouraging because it fills the space quite nicely, but again it requires bidirectional ranges. My solution is to fill hypercubes of increasing size from origin. One hypercube of size k is built by adding a layer of bricks on a hypercube of size k - 1. That can be done with forward iterators, and in fact is not all that difficult. Andrei: We've discussed this before. Crosscartesian product of multiple infinite ranges can be easily done by applying Cantor's trick for proving that rational numbers are just as numerous than natural numbers. Google for Cantor with site:digitalmars.com. Ok, I think I solved this particular problem, if only for infinite ranges. It's in three parts: 1- A memorize(range) struct that slowly looks ahead in a range, store the result in an internal array and so slowly transforms an input range into a random-access range. I tried this a few months ago, but got stuck in trying to propagate properties (bidirectional, etc). Now it's just an input range. Much easier. It's related to Zippers (in functional PL). 2- Generate the indices of sum = 0, then sum = 1, then sum = 2; etc. 3- Just take the corresponding indices in the input ranges. I don't think this is a good solution. Andrei
Re: [Challenge] implementing the ambiguous operator in D
Philippe Sigaud philippe.sig...@gmail.com wrote:
I guess the D syntax would be
auto x = amb([1,2,3]);
auto y =amb([4,5,6]);
x*y == 8; // forces desambiguation = the ambs explore the possibilities.
assert(x == amb([2]));
assert(y == amb([4]));
There is only one value left, no more ambiguity.
But what happens in the case where there is more than one value left?
That's one of the reasons I feel that doing the combination, then
filtering it, is more correct. There is also the fact that the above
syntax does not let you call arbitrary functions in the requirements,
something filter does.
Maybe in this case an
'alias possibilities[0] this' could do the trick:
assert(x == 2);
assert(y == 4);
Can we do alias someArray[0] this; ?
Well, we can do this:
struct foo( R ) {
R range;
ref ElementType!R getFront( ) {
return range.front;
}
alias getFront this;
}
--
Simen
Re: [Challenge] implementing the ambiguous operator in D
On Sun, Sep 5, 2010 at 12:00, Simen kjaeraas simen.kja...@gmail.com wrote:
Philippe Sigaud philippe.sig...@gmail.com wrote:
I guess the D syntax would be
auto x = amb([1,2,3]);
auto y =amb([4,5,6]);
x*y == 8; // forces desambiguation = the ambs explore the possibilities.
assert(x == amb([2]));
assert(y == amb([4]));
There is only one value left, no more ambiguity.
But what happens in the case where there is more than one value left?
If I understand correctly the linked Ruby and Haskell versions, the search
stops as soon as you find a possibility. But then, I'm no pro on this.
That's one of the reasons I feel that doing the combination, then
filtering it, is more correct. There is also the fact that the above
syntax does not let you call arbitrary functions in the requirements,
something filter does.
The combining and filtering is interesting (in this case, it'd be like doing
a list comprehension).
But the real challenge in the SO question is the 'going back in time' part,
which I have trouble to understand : how can you modify x and y through a
multiplication and a comparison?
I did a range comprehension maybe one year ago, which would be partially
equivalent to the problem:
auto solution = comp!([a,b], a*b == 8)([1,2,3], [4,5,6]);
solution is a range, in this case a one element range, containing only
[2,4].
Philippe
Maybe in this case an
'alias possibilities[0] this' could do the trick:
assert(x == 2);
assert(y == 4);
Can we do alias someArray[0] this; ?
Well, we can do this:
struct foo( R ) {
R range;
ref ElementType!R getFront( ) {
return range.front;
}
alias getFront this;
}
--
Simen
Re: [Challenge] implementing the ambiguous operator in D
On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud philippe.sig...@gmail.com wrote: But the real challenge in the SO question is the 'going back in time' part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison? It can be done using setjmp/longjmp, see C implementation for an example: http://homepage.mac.com/sigfpe/Computing/continuations.html
Re: [Challenge] implementing the ambiguous operator in D
On 09/05/2010 07:59 AM, Philippe Sigaud wrote: On Sun, Sep 5, 2010 at 12:00, Simen kjaeraas simen.kja...@gmail.com mailto:simen.kja...@gmail.com wrote: Philippe Sigaud philippe.sig...@gmail.com mailto:philippe.sig...@gmail.com wrote: I guess the D syntax would be auto x = amb([1,2,3]); auto y =amb([4,5,6]); x*y == 8; // forces desambiguation = the ambs explore the possibilities. assert(x == amb([2])); assert(y == amb([4])); There is only one value left, no more ambiguity. But what happens in the case where there is more than one value left? If I understand correctly the linked Ruby and Haskell versions, the search stops as soon as you find a possibility. But then, I'm no pro on this. That's one of the reasons I feel that doing the combination, then filtering it, is more correct. There is also the fact that the above syntax does not let you call arbitrary functions in the requirements, something filter does. The combining and filtering is interesting (in this case, it'd be like doing a list comprehension). But the real challenge in the SO question is the 'going back in time' part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison? I did a range comprehension maybe one year ago, which would be partially equivalent to the problem: auto solution = comp!([a,b], a*b == 8)([1,2,3], [4,5,6]); solution is a range, in this case a one element range, containing only [2,4]. Here we need to have a crossProduct range, as we discussed in the thread Combining infinite ranges. Then it's easy to combine it with filter: auto solutions = filter!a*b == 8(crossProduct([1,2,3], [4,5,6])); Andrei
Re: [Challenge] implementing the ambiguous operator in D
2010/9/5 Denis Koroskin 2kor...@gmail.com On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud philippe.sig...@gmail.com wrote: But the real challenge in the SO question is the 'going back in time' part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison? It can be done using setjmp/longjmp, see C implementation for an example: http://homepage.mac.com/sigfpe/Computing/continuations.html How can we access setjmp/longjmp in D? Anyway, I'm a bit nervous with using such a raw statement. An oh-so-slightly wrapped equivalent for D would be better. Philippe
Re: [Challenge] implementing the ambiguous operator in D
On Sun, Sep 5, 2010 at 15:56, Andrei Alexandrescu seewebsiteforem...@erdani.org wrote: equivalent to the problem: auto solution = comp!([a,b], a*b == 8)([1,2,3], [4,5,6]); solution is a range, in this case a one element range, containing only [2,4]. I did a range comprehension maybe one year ago, which would be partially Here we need to have a crossProduct range, as we discussed in the thread Combining infinite ranges. Then it's easy to combine it with filter: auto solutions = filter!a*b == 8(crossProduct([1,2,3], [4,5,6])); Not exactly: crossProduct is a range, and the only element type that makes sense is Tuple!(A,B). Unless of course you're interested in adding binary predicates to filter, which would be understood as automatically opening tuples (and of course, would statically check the length of the tuple and the arity of the passed function). I can add this to Phobos. What you call crossProduct can be seen as zipWith!tuple(range, range2), which If there is interest in this, I also suggest having a n-range version of map that takes a n-ary function and maps them in parallel. auto m = map!a b ? a : c(range1, range2, range3); OK, I definitely need to take some time to assemble all this and propose it for a formal Phobos review. I'll bump it up higher in my TODO list. Philippe Philippe
Re: [Challenge] implementing the ambiguous operator in D
On Sun, Sep 5, 2010 at 16:30, Philippe Sigaud philippe.sig...@gmail.comwrote: What you call crossProduct can be seen as zipWith!tuple(range, range2), which Scratch that. zipWith *is* mapping on n ranges in parallel.
Re: [Challenge] implementing the ambiguous operator in D
On Sun, 05 Sep 2010 18:24:43 +0400, Philippe Sigaud
philippe.sig...@gmail.com wrote:
2010/9/5 Denis Koroskin 2kor...@gmail.com
On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud
philippe.sig...@gmail.com wrote:
But the real challenge in the SO question is the 'going back in time'
part,
which I have trouble to understand : how can you modify x and y
through a
multiplication and a comparison?
It can be done using setjmp/longjmp, see C implementation for an
example:
http://homepage.mac.com/sigfpe/Computing/continuations.html
How can we access setjmp/longjmp in D?
Anyway, I'm a bit nervous with using such a raw statement. An
oh-so-slightly
wrapped equivalent for D would be better.
Philippe
It is available after the following import:
import core.sys.posix.setjmp;
It is not defined on Windows, but I believe you can use the following
declaration with dmd (works for ddmd):
version (Windows) {
alias int[16] jmp_buf;
extern (C) extern
{
int setjmp(ref jmp_buf env);
void longjmp(ref jmp_buf env, int value);
}
}
Some documentation:
http://en.wikipedia.org/wiki/Setjmp.h
Use the following struct (or make it a class) if you prefer OOP style:
struct State
{
int save() {
return setjmp(buf);
}
void restore(int status) {
assert(status != 0);
longjmp(buf, status);
}
private jmp_buf buf;
}
import std.stdio;
void main()
{
State state;
int result = state.save();
if (result == 0) {
// first time here
writeln(state saved);
state.restore(1);
} else {
assert(result == 1);
writeln(state restored);
}
}
The code above should print:
state saved
state restored
(not tested)
Re: [Challenge] implementing the ambiguous operator in D
Denis Koroskin:
The code above should print:
state saved
state restored
(not tested)
On Windows, dmd 2.048, this code:
import std.c.stdio: puts;
version (Windows) {
alias int[16] jmp_buf;
extern (C) extern {
int setjmp(ref jmp_buf env);
void longjmp(ref jmp_buf env, int value);
}
}
struct State {
int save() {
return setjmp(buf);
}
void restore(int status) {
assert(status != 0);
longjmp(buf, status);
}
private jmp_buf buf;
}
void main() {
State state;
int result = state.save();
if (result == 0) {
// first time here
puts(state saved);
state.restore(1);
} else {
assert(result == 1);
puts(state restored);
}
}
Gives an Access Violation after printing state saved.
Bye,
bearophile
Re: [Challenge] implementing the ambiguous operator in D
On Sun, 05 Sep 2010 19:17:55 +0400, bearophile bearophileh...@lycos.com
wrote:
Denis Koroskin:
The code above should print:
state saved
state restored
(not tested)
On Windows, dmd 2.048, this code:
import std.c.stdio: puts;
version (Windows) {
alias int[16] jmp_buf;
extern (C) extern {
int setjmp(ref jmp_buf env);
void longjmp(ref jmp_buf env, int value);
}
}
struct State {
int save() {
return setjmp(buf);
}
void restore(int status) {
assert(status != 0);
longjmp(buf, status);
}
private jmp_buf buf;
}
void main() {
State state;
int result = state.save();
if (result == 0) {
// first time here
puts(state saved);
state.restore(1);
} else {
assert(result == 1);
puts(state restored);
}
}
Gives an Access Violation after printing state saved.
Bye,
bearophile
Turn main into an extern(C) int main() and it works.
Surround the code with try/catch block and it fails again.
Looks like longjmp fails if you run the function inside a try/catch block
for some reason.
Re: [Challenge] implementing the ambiguous operator in D
Denis Koroskin:
Turn main into an extern(C) int main() and it works.
This version:
import std.c.stdio: puts;
version (Windows) {
alias int[16] jmp_buf;
extern (C) extern {
int setjmp(ref jmp_buf env);
void longjmp(ref jmp_buf env, int value);
}
}
struct State {
int save() {
return setjmp(buf);
}
void restore(int status) {
assert(status != 0);
longjmp(buf, status);
}
private jmp_buf buf;
}
extern(C) int main() {
State state;
int result = state.save();
if (result == 0) {
// first time here
puts(state saved);
state.restore(1);
} else {
assert(result == 1);
puts(state restored);
}
return 0;
}
Gives link errors:
test.obj(test)
Error 42: Symbol Undefined __d_assertm
test.obj(test)
Error 42: Symbol Undefined __d_assert_msg
Bye,
bearophile
Re: [Challenge] implementing the ambiguous operator in D
On Sun, 05 Sep 2010 20:18:13 +0400, bearophile bearophileh...@lycos.com
wrote:
Denis Koroskin:
Turn main into an extern(C) int main() and it works.
This version:
import std.c.stdio: puts;
version (Windows) {
alias int[16] jmp_buf;
extern (C) extern {
int setjmp(ref jmp_buf env);
void longjmp(ref jmp_buf env, int value);
}
}
struct State {
int save() {
return setjmp(buf);
}
void restore(int status) {
assert(status != 0);
longjmp(buf, status);
}
private jmp_buf buf;
}
extern(C) int main() {
State state;
int result = state.save();
if (result == 0) {
// first time here
puts(state saved);
state.restore(1);
} else {
assert(result == 1);
puts(state restored);
}
return 0;
}
Gives link errors:
test.obj(test)
Error 42: Symbol Undefined __d_assertm
test.obj(test)
Error 42: Symbol Undefined __d_assert_msg
Bye,
bearophile
Try linking with phobos explicitly:
# dmd test.d phobos.lib
Re: [Challenge] implementing the ambiguous operator in D
On 09/05/2010 09:30 AM, Philippe Sigaud wrote: On Sun, Sep 5, 2010 at 15:56, Andrei Alexandrescu seewebsiteforem...@erdani.org mailto:seewebsiteforem...@erdani.org wrote: equivalent to the problem: auto solution = comp!([a,b], a*b == 8)([1,2,3], [4,5,6]); solution is a range, in this case a one element range, containing only [2,4]. I did a range comprehension maybe one year ago, which would be partially Here we need to have a crossProduct range, as we discussed in the thread Combining infinite ranges. Then it's easy to combine it with filter: auto solutions = filter!a*b == 8(crossProduct([1,2,3], [4,5,6])); Not exactly: crossProduct is a range, and the only element type that makes sense is Tuple!(A,B). Unless of course you're interested in adding binary predicates to filter, which would be understood as automatically opening tuples (and of course, would statically check the length of the tuple and the arity of the passed function). I can add this to Phobos. Oh indeed. I think it's not onerous to require the client to write: auto solutions = filter!a._0*a._0 == 8(crossProduct([1,2,3], [4,5,6])); What you call crossProduct can be seen as zipWith!tuple(range, range2), which Yah, per your follow-up post, it's a different problem. It's also a much more difficult one. I convinced myself crossProduct is impossible to implement if one input range and one infinite forward range are simultaneously present. It works with any number of infinite forward ranges, and also with other combinations. I couldn't formalize the exact requirements yet. If there is interest in this, I also suggest having a n-range version of map that takes a n-ary function and maps them in parallel. auto m = map!a b ? a : c(range1, range2, range3); OK, I definitely need to take some time to assemble all this and propose it for a formal Phobos review. I'll bump it up higher in my TODO list. Philippe Yah, definitely. Note that I have a functioning Zip in my upcoming commit to std.range. Andrei
Re: [Challenge] implementing the ambiguous operator in D
Philippe Sigaud philippe.sig...@gmail.com wrote: But the real challenge in the SO question is the 'going back in time' part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison? I believe this to be possible, though horrible and unpleasant. Basically, binary operations on Amb ranges create a new, temporary type. This type keeps track of which ranges have been involved in the operation thus far, and which operations, and at the end gives each Amb a bool delegate( ElementType!Amb ) that has a heap copy of each other range and evaluates the operations on each. However, this solution may lead to inconsistent state in the combination of ranges. Another solution is for each Amb to keep track of a 'controller', which keeps track of the constraints given. This controller would be a combinatorial product of references to the ranges involved. Any call to popFront on the Amb ranges would delegate to the controller's popFront, which would update the involved ranges. Due to the unknowability of the number and type of ranges involved, this controller would need to be a class. I believe, but cannot prove, that only one constraint (i.e. one set of operations) would be feasible to keep track of in such a system, and thus the following would not work: auto a = amb( [1,2,3] ); auto b = amb( [1,3,6] ); auto c = amb( [3,6,9] ); a * b = 6; a * c = 9; assert( a == 1 ); assert( b == 6 ); assert( c == 9 ); A system based around the combinatorial range as a stand-alone, and using filter(s) could easily do the equivalent, but would be limited in that it would only yield one range unless given reference semantics. In the latter case, it would function much like above, except the controller would be a known type that the programmer him- or herself would need to manage. Another problem of the first system is that it has no support for conditionals. -- Simen
Re: [Challenge] implementing the ambiguous operator in D
On Sat, Sep 4, 2010 at 01:40, Simen kjaeraas simen.kja...@gmail.com wrote:
Simen kjaeraas simen.kja...@gmail.com wrote:
I believe this will only work with arrays as input. Either that, or I need
a way to make this work:
struct Foo( R ) if ( isForwardRange!R ) {
bool delegate( ElementType!R ) bar;
Filter!( bar, R ) range;
}
Or, well, something like it. I need a static type for a Filter that
delegates to a struct member, in this case bar.
Maybe with a dynamic filter?
struct DynamicFilter(R) if (isInputRange!R)
{
R range;
bool delegate(ElementType!R) predicate;
bool set;
this(R _range) { range = _range; }
this(R _range, bool delegate(ElementType!R) _predicate) { range =
_range; predicate = _predicate; set = true; popFront(); }
void setPredicate(bool delegate(ElementType!R) _predicate) { predicate =
_predicate; set = true; popFront();}
ElementType!R front() { if (set) { return range.front();} else { throw
new Exception(Calling DynamicFilter with an unset predicate.);};}
bool empty() { if (set) {return range.empty;} else { throw new
Exception(Calling DynamicFilter with an unset predicate.);};}
void popFront()
{
if (set)
{
while( !range.empty !predicate(range.front))
{
range.popFront();
}
}
else
{
throw new Exception(Calling DynamicFilter with an unset
predicate.);
}
}
}
//DynamicFilter!(R) dynamicFilter(R)(R range)
//{
//return DynamicFilter!R(range);
//}
DynamicFilter!(R) dynamicFilter(R,E)(R range, bool delegate(E) pred = null)
if ((isInputRange!R) is(ElementType!R == E))
{
if (pred is null)
return DynamicFilter!(R)(range);
else
return DynamicFilter!R(range, pred);
}
void main()
{
auto f = dynamicFilter([0,1,2,3], (int i) { return i%2 == 0;});
writeln(f.front); // 0
f.setPredicate((int i) { return i%2 == 1;});
writeln(f.front); // 1
}
Note that in this version, the filtered range always advances. When you
change filter, it continues to consume elements from the current point. For
backtracking, maybe you need a forward range input, a saved version of this
input, and have setPredicate rewind the inner range to the saved version.
Philippe
Re: [Challenge] implementing the ambiguous operator in D
== Quote from Nick Sabalausky (a...@a.a)'s article Interesting thing, but devil's advocate: What would be the uses/benefits of that versus just having for each element versions of the operators? Well the obvious benefit is that you don't have to create all those extra version -- you get them all for free. Also, ambiguous seems like a rather odd name for what it does. I don't see how ambiguity has anything to do with it. That disconnect made it difficult at first for me to understand what it was. It's more like an elementwise or something. I agree, it's a pretty bad name. I'd call it all or something.
Re: [Challenge] implementing the ambiguous operator in D
Philippe Sigaud philippe.sig...@gmail.com wrote: Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d The amb operator does this: amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10]) amb([hello, world]) ~ amb([qwerty]) == amb([helloqwerty, worldqwerty]) amb([hello, world]) ~ qwerty == amb([helloqwerty, worldqwerty]) amb([hello, very long string]).length = amb([5, 16]) (I find the guy examples much more comprehensible that the articles he links to) Are people interested in trying this? Yes, very much so. However, Peter Alexander has misunderstood the ambiguous operator. The idea of amb is to return the combinatorial product of N ranges. if this sounds familiar, it is because it has been discussed at length here earlier, with me and Andrei being the prime contributors (see Combining infinite ranges and Huffman coding comparison). The solution has eluded me for a while, and I have shelved my efforts while doing other things. Perhaps now is the time to revisit it. Peter Alexander seems to have conflated the two concepts of the ambiguous operator and its require()-function. Basically, Amb should be a range of tuples, and you then filter it to retrieve the interesting parts. -- Simen
Re: [Challenge] implementing the ambiguous operator in D
On 02/09/10 05:38, Philippe Sigaud wrote: Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d It's great to see someone doing the first D discussion topic with the [challenge] annotation. Bearophile, if you are reading this perhaps you might like to repost some of you previous challenges which have not received much attention with the [challenge] annotation in the subject line. I hope this idea of annotating ng discussion topics with their genre, say [challenge] or [trick], or perhaps [typesystem] or whatever takes on as much as [OT] threads seem to :-) Cheers Justin Johansson
Re: [Challenge] implementing the ambiguous operator in D
== Quote from Simen kjaeraas (simen.kja...@gmail.com)'s article Yes, very much so. However, Peter Alexander has misunderstood the ambiguous operator. Hey, I was just going by what the guy posted :) He mentioned nothing of tuples, and his examples certainly didn't show any tuples.
Re: [Challenge] implementing the ambiguous operator in D
On Fri, Sep 3, 2010 at 19:51, Peter Alexander peter.alexander...@gmail.comwrote: == Quote from Simen kjaeraas (simen.kja...@gmail.com)'s article Yes, very much so. However, Peter Alexander has misunderstood the ambiguous operator. Hey, I was just going by what the guy posted :) He mentioned nothing of tuples, and his examples certainly didn't show any tuples. Yes, I agree with Peter there. As I said, I personally prefer the examples in the SO OP than the Haskell/Ruby code, if only because the example are easily understood and I find this range combinator useful in some circumstances. What we have here in D is a bit like the List monad in Haskell: a way to represent a bunch of possible values for a computation. If a can 2 or 4 or 6, and b can be 0 or 1 or 2, it makes sense for a*b to among 0,2,4,6,8,12. So thanks, Peter. But does the code compile for you? As I said, here with 2.048, it doesn't. Now, the 'real'/intriguing/mind-bending amb operator (from the 60's) does like the Haskell implementation linked in SO does: backtracking on the results to avoid some condition. If someone is up to the challenge of implementing it in D, great! Maybe with closures? I never really thought about it. I guess the D syntax would be auto x = amb([1,2,3]); auto y =amb([4,5,6]); x*y == 8; // forces desambiguation = the ambs explore the possibilities. assert(x == amb([2])); assert(y == amb([4])); There is only one value left, no more ambiguity. Maybe in this case an 'alias possibilities[0] this' could do the trick: assert(x == 2); assert(y == 4); Can we do alias someArray[0] this; ? Philippe Philippe
Re: [Challenge] implementing the ambiguous operator in D
On Fri, Sep 3, 2010 at 16:30, Justin Johansson n...@spam.com wrote: On 02/09/10 05:38, Philippe Sigaud wrote: Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d It's great to see someone doing the first D discussion topic with the [challenge] annotation. This was just for fun, because combining ranges is always fun, and in this case, it's a good example of operator overloading. I have a more interesting / less academic challenge in mind: make idmd, an interactive,REPL-like, D interpreter. Philippe
Re: [Challenge] implementing the ambiguous operator in D
Peter Alexander peter.alexander...@gmail.com wrote: == Quote from Simen kjaeraas (simen.kja...@gmail.com)'s article Yes, very much so. However, Peter Alexander has misunderstood the ambiguous operator. Hey, I was just going by what the guy posted :) He mentioned nothing of tuples, and his examples certainly didn't show any tuples. Sorry, yes. Copied the wrong name off of the OP on SO. Should have said chrisdew, not Peter Alexander. -- Simen
Re: [Challenge] implementing the ambiguous operator in D
Philippe Sigaud philippe.sig...@gmail.com wrote:
Now, the 'real'/intriguing/mind-bending amb operator (from the 60's) does
like the Haskell implementation linked in SO does: backtracking on the
results to avoid some condition. If someone is up to the challenge of
implementing it in D, great! Maybe with closures? I never really thought
about it.
I guess the D syntax would be
auto x = amb([1,2,3]);
auto y =amb([4,5,6]);
x*y == 8; // forces desambiguation = the ambs explore the possibilities.
I believe this will only work with arrays as input. Either that, or I need
a way to make this work:
struct Foo( R ) if ( isForwardRange!R ) {
bool delegate( ElementType!R ) bar;
Filter!( bar, R ) range;
}
Or, well, something like it. I need a static type for a Filter that
delegates to a struct member, in this case bar.
assert(x == amb([2]));
assert(y == amb([4]));
There is only one value left, no more ambiguity. Maybe in this case an
'alias possibilities[0] this' could do the trick:
assert(x == 2);
assert(y == 4);
Can we do alias someArray[0] this; ?
For a simple assert like that, overloading opEquals ought to do the
trick, no?
--
Simen
Re: [Challenge] implementing the ambiguous operator in D
Simen kjaeraas simen.kja...@gmail.com wrote:
I believe this will only work with arrays as input. Either that, or I
need
a way to make this work:
struct Foo( R ) if ( isForwardRange!R ) {
bool delegate( ElementType!R ) bar;
Filter!( bar, R ) range;
}
Or, well, something like it. I need a static type for a Filter that
delegates to a struct member, in this case bar.
I would have thought this'd work, but apparently I'm wrong:
module foo;
import std.stdio;
import std.algorithm;
import std.range;
struct Foo( R ) if ( isForwardRange!R ) {
R range;
void delegate( ) _popFront;
bool delegate( ) _empty;
ElementType!R delegate( ) _front;
this( R rng ) {
range = rng;
_popFront = { range.popFront( ); };
_empty = { return range.empty; };
_front = { return range.front; };
}
void attempt( bool delegate( ElementType!R ) dg ) {
auto rng = filter!dg( range );
_popFront = { rng.popFront( ); };
_empty = { return rng.empty; };
_front = { return rng.front; };
}
void popFront( ) {
_popFront( );
}
@property
bool empty( ) {
return _empty( );
}
@property
ElementType!R front( ) {
return _front( );
}
}
Foo!R bar( R )( R rng ) if ( isForwardRange!R ) {
return Foo!R( rng );
}
void main() {
auto b = bar( [1,2,3] );
foreach ( e; b ) {
writeln( e );
}
}
Output:
1
object.Error: Access Violation
--
Simen
Re: [Challenge] implementing the ambiguous operator in D
On 09/01/2010 11:49 PM, Peter Alexander wrote:
On 1/09/10 9:08 PM, Philippe Sigaud wrote:
Peter, can we discuss your solution here?
Sure, I'd be interested to hear any improvements. Like I said in my
answer, I'm still learning D so I'm sure there's many issues. For
example, I made no attempt for const-correctness or anything like that
(mostly for simplicity).
In particular, I'd be interested in knowing if there's a better way to
write opDispatch i.e. a way that doesn't use that ugly mixin.
It needs opEquals :-)
something like this
auto opEquals(E e) {
auto cmp = (E a) { return a == e; };
return map!cmp(r);
}
...
writeln(5 == amb([1,2,3,4,5]));
[false, false, false, false, true]
Re: [Challenge] implementing the ambiguous operator in D
On 2/09/10 7:34 AM, Pelle wrote: It needs opEquals :-) Yeah, it needs a lot of things :) You could easily add unary operators as well (e.g. so that -amb([1, 2]) == [-1, -2]. I didn't bother adding more than I did because it would make the post too large, and wouldn't really add anything (I thought that the binary ops + dispatch covered most of the interesting cases). Also, I think it would supposed to return amb(map!...) instead of just returning map!... (otherwise you couldn't chain them), but that's a simple fix.
Re: [Challenge] implementing the ambiguous operator in D
On Thu, Sep 2, 2010 at 09:06, Peter Alexander
peter.alexander...@gmail.comwrote:
On 2/09/10 7:34 AM, Pelle wrote:
It needs opEquals :-)
Yeah, it needs a lot of things :)
You could easily add unary operators as well (e.g. so that -amb([1, 2]) ==
[-1, -2]. I didn't bother adding more than I did because it would make the
post too large, and wouldn't really add anything (I thought that the binary
ops + dispatch covered most of the interesting cases).
Also, I think it would supposed to return amb(map!...) instead of just
returning map!... (otherwise you couldn't chain them), but that's a simple
fix.
Yes, like Haskell monads: get into, transform, return a wrapped result.
Does your code compile for you? I tried it when you posted it on SO and the
.length, .replace(a,u) didn't work.
I had to change opDispatch from
auto opDispatch(string f)()
{
mixin(return map!((E e) { return e.~f~; })(r););
}
to:
auto opDispatch(string f)()
{
return map!(unaryFun!(a.~f))(r);
}
I tried to do the same for the dispatch with arguments, but got very strange
errors. DMD told me it couldn't get the args at CT.
Oh, but you changed your code on SO. It can know do the first example too.
That's good, and was in fact my main subject of interest. Amb seems to be
like the product of two ranges (with an operator), which is then flattened.
What I don't get is the link with the ruby article and its use of if.
Philippe
Re: [Challenge] implementing the ambiguous operator in D
Philippe Sigaud philippe.sig...@gmail.com wrote in message
news:mailman.42.1283371696.858.digitalmar...@puremagic.com...
Hey, this question on SO makes for a good challenge:
http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d
The amb operator does this:
amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10])
amb([hello, world]) ~ amb([qwerty]) == amb([helloqwerty,
worldqwerty])
amb([hello, world]) ~ qwerty == amb([helloqwerty, worldqwerty])
amb([hello, very long string]).length = amb([5, 16])
Interesting thing, but devil's advocate: What would be the uses/benefits of
that versus just having for each element versions of the operators?
Also, ambiguous seems like a rather odd name for what it does. I don't see
how ambiguity has anything to do with it. That disconnect made it difficult
at first for me to understand what it was. It's more like an elementwise
or something.
Certainly useful, I had reason to make a similar function once:
/// ctfe_subMapJoin(Hi WHO. , WHO, [Joey, Q, Sue])
/// -- Hi Joey. Hi Q. Hi Sue.
T ctfe_subMapJoin(T)(T str, T match, T[] replacements) if(isSomeString!T)
{
T value = ;
foreach(T replace; replacements)
value ~= ctfe_substitute(str, match, replace);
return value;
}
Though I'll grant that's a questionable name for it. I wasn't sure what else
to call it though.
Re: [Challenge] implementing the ambiguous operator in D
Nick Sabalausky a...@a.a wrote in message news:i5p68t$2pt...@digitalmars.com... Philippe Sigaud philippe.sig...@gmail.com wrote in message news:mailman.42.1283371696.858.digitalmar...@puremagic.com... Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d The amb operator does this: amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10]) amb([hello, world]) ~ amb([qwerty]) == amb([helloqwerty, worldqwerty]) amb([hello, world]) ~ qwerty == amb([helloqwerty, worldqwerty]) amb([hello, very long string]).length = amb([5, 16]) Interesting thing, but devil's advocate: What would be the uses/benefits of that versus just having for each element versions of the operators? Also, ambiguous seems like a rather odd name for what it does. I don't see how ambiguity has anything to do with it. That disconnect made it difficult at first for me to understand what it was. It's more like an elementwise or something. I've been starting at the Ruby page, and I think I'm starting to understand it a little more: Suppose you have two mostly unknown values: x and y. Neither you, nor the computer at runtime, know what either of their values actually are. But, you *do* know a finite set of values that they *might* be: auto x = amb([1, 2]); // x is either 1 or 2, but I don't know which auto y = amb([3, 4, 5]); // y is either 3, 4 or 5, but I don't know which assert(x != 2); // Not guaranteed to be == 2 at this point assert(y != 4); // x*y must be one of these values, but I don't know which, it could be any of them: assert(x*y == amb([3, 4, 5, 6, 8, 10]); // Here's the *real* magic (psuedo-syntax): // For some bizarre reason, this means // that x*y must be == 8 (despite the !=) amb(if x*y != 8); // Since x*y has been determined to be 8, // the real values of x and y are now known and // completely unambiguous: assert(x == 2); assert(y == 4);
[Challenge] implementing the ambiguous operator in D
Hey, this question on SO makes for a good challenge: http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d The amb operator does this: amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10]) amb([hello, world]) ~ amb([qwerty]) == amb([helloqwerty, worldqwerty]) amb([hello, world]) ~ qwerty == amb([helloqwerty, worldqwerty]) amb([hello, very long string]).length = amb([5, 16]) (I find the guy examples much more comprehensible that the articles he links to) Are people interested in trying this? Peter, can we discuss your solution here? Philippe
Re: [Challenge] implementing the ambiguous operator in D
On 1/09/10 9:08 PM, Philippe Sigaud wrote: Peter, can we discuss your solution here? Sure, I'd be interested to hear any improvements. Like I said in my answer, I'm still learning D so I'm sure there's many issues. For example, I made no attempt for const-correctness or anything like that (mostly for simplicity). In particular, I'd be interested in knowing if there's a better way to write opDispatch i.e. a way that doesn't use that ugly mixin.
