• bearophile <bearophileHUGS lycos.com> Aug 16 2007
• Oskar Linde <oskar.lindeREM OVEgmail.com> Aug 16 2007
• BCS <ao pathlink.com> Aug 16 2007

bearophile <bearophileHUGS lycos.com> writes:

Sorry for my answering delay.

BCS:

I'll put a copy at the end that has some edits, mostly for code space and
editablility.<


Thank you. I'm learning D, so I can comment your code; this is the first line:
Xpermutations!(TyItem) xpermutations(TyItem)(TyItem[] items, bool copy=true) 

I think it has a problem, this templated class (that't the resulting object of
the helper function) doesn't receive the boolean value:
Xpermutations!(TyItem)

And this line:
if (int result = dg2(items2)) return result;
May raise an error like this:
modulename.d(linenumber): Error: '=' does not give a boolean result


Maybe I under-spoke, the opApply is much more transparent. the system is doing,
and hiding, a lot less complexity. IMO a system hiding to much complexity is
not a good thing.<


I understand now. Because of their nature and usage, in dynamic languages like
Python/Ruby it's normal to hide part of the complexity from the user, but you
are right asserting that in lower level languages like C++/D it's probably
better to show most complexities to the programmer, to avoid problems, reduce
"mysteries", to improve the capability to optimize the code, etc.
(Maybe a language like D can be designed to have some hi-level constructs to be
used in the spots where you don't care of speed; beside other lower lever ones
to be used where you need more speed and you need to exactly know what's
happening under the cover. Other people may argue you can't fit both things in
the same language).

Thank you for your code version and your answers.

----------------------

In the meantime I have found some problems translating lazy recursive
generators from Py=>D, like this one, that yields the combinations of the given
items, taking k distinct elements (this kind of code may look slow). You may
help me:

def xcombinations(items, k):
  if k:
    for i in xrange(len(items) - k + 1):
      for cc in xcombinations(items[i+1:], k-1):
        yield [items[i]] + cc
  else:
    yield []

Usage example:
xcombinations("abcd", 1) ==> "a" "b" "c" "d"
xcombinations("abcd", 2) ==> "ab" "ac" "ad" "bc" "bd" "cd"
xcombinations("abcd", 3) ==> "abc" "abd" "acd" "bcd"

Note that:

xrange(n) just yields int numbers from 0 to n-1.

+ among arrays equals to ~.

array[a:] equals to:
(a >= cast(long)array.length) ? new typeof(array)[0] : array[max(a,0) .. $].

Bear hugs,
bearophile

Oskar Linde <oskar.lindeREM OVEgmail.com> writes:

bearophile wrote:

 In the meantime I have found some problems translating lazy recursive
generators from Py=>D, like this one, that yields the combinations of the given
items, taking k distinct elements (this kind of code may look slow). You may
help me:
 
 def xcombinations(items, k):
   if k:
     for i in xrange(len(items) - k + 1):
       for cc in xcombinations(items[i+1:], k-1):
         yield [items[i]] + cc
   else:
     yield []
 
 Usage example:
 xcombinations("abcd", 1) ==> "a" "b" "c" "d"
 xcombinations("abcd", 2) ==> "ab" "ac" "ad" "bc" "bd" "cd"
 xcombinations("abcd", 3) ==> "abc" "abd" "acd" "bcd"



As far as I can tell, the following should work. Maybe I am missing 
something fundamental, as this is just a straight forward implementation 
of the above. Note that yield(x) is:

{ auto tmp = x; if (auto r = dg(tmp)) return r; }

(Might be a nice macro in the future.)

Code:

struct XRange {
   int n;

   int opApply(int delegate(inout int v) dg) {
     for (int i = 0; i < n; i++)
       if (auto r = dg(i)) return r;
     return 0;
   }
}

XRange xrange(int n) { XRange r; r.n = n; return r; }

struct XCombinations(T) {
   T[] items;
   int k;
	
   int opApply(int delegate(inout T[] arr) dg) {
     if (k > 0)
       foreach (i; xrange(items.length - k + 1))
         foreach(cc; xcombinations(items[i+1..$], k-1)) {
           auto tmp = items[i] ~ cc; // must be an lvalue
           if (auto r = dg(tmp)) return r;
	}
     else {
       T[] tmp = null; // need an lvalue
       return dg(tmp);
     }
     return 0;
   }	
}

XCombinations!(T) xcombinations(T)(T[] items, int k) {
   XCombinations!(T) ret;
   ret.items = items;
   ret.k = k;
   return ret;
}



-- 
Oskar

BCS <ao pathlink.com> writes:

Reply to bearophile,

 Sorry for my answering delay.
 
 BCS:
 
 I'll put a copy at the end that has some edits, mostly for code space
 and editablility.<
 


 first line: Xpermutations!(TyItem) xpermutations(TyItem)(TyItem[]
 items, bool copy=true)
 
 I think it has a problem, this templated class (that't the resulting
 object of the helper function) doesn't receive the boolean value:
 
 Xpermutations!(TyItem)


that is because it can't, not directly at least. This is because the argument 
is a runtime value and template parameter must be compile time values. However 
because bools can only have two values it is trivial to generate both versions 
and have the run time code select between them.

OTOH your correct about the return type. this could be solved by using an 
abstract base class that uses the (TyItem) and a derived class that uses 
both args.
Another solution would be to return a delegate to the opApply function:

|int delegate(int delegate(ref TyItem[])) xpermutations(TyItem)(TyItem[] 
items, bool copy=true)
|{
| if(copy)
| return &(new Xpermutations!(TyItem, true)(items)).opApply;
| else
| return &(new Xpermutations!(TyItem, false)(items)).opApply;
|}
 
 And this line:
 if (int result = dg2(items2)) return result;
 May raise an error like this:
 modulename.d(linenumber): Error: '=' does not give a boolean result


it doesn't. assignment expressions cause that error, variable delectations 
don't

 
 (Maybe a language like D can be designed to have some hi-level
 constructs to be used in the spots where you don't care of speed;
 beside other lower lever ones to be used where you need more speed and
 you need to exactly know what's happening under the cover. Other
 people may argue you can't fit both things in the same language).
 


I tend to think low level. C# annoys the heck out of me because it's "to 
high level". ff