www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Better idea for double list comprehension?

reply "CJS" <Prometheus85 hotmail.com> writes:
I'm trying to write a D function that does the same as this 
Python function:

def cross(A, B):
     "Cross product of elements in A and elements in B."
     return [a+b for a in A for b in B]

where A and B are strings. (So cross("ab","12") is ["a1", "b1", 
"a2", "b2"]).

It's easy to get something that works the same in D, but I'd like 
to make it as simple and short as possible. The best I could come 
up with is


string[] cross(string A, string B){
     string[] grid;
     foreach(t; cartesianProduct(A,B)){
         grid ~= (to!string(p[0]) ~ to!string(p[1]));
Jan 17 2014
next sibling parent reply "CJS" <Prometheus85 hotmail.com> writes:
Hit the wrong key and posted too early. I finished the code 
sample below. My main question was for something prettier and 
more concise. I feel like the code below is long and not as 
pretty in comparison to the Python. Sometimes that's an 
unavoidable consequence of static typing, but I'm not sure that's 
the case here.

On Saturday, 18 January 2014 at 05:40:56 UTC, CJS wrote:

 I'm trying to write a D function that does the same as this 
 Python function:

 def cross(A, B):
     "Cross product of elements in A and elements in B."
     return [a+b for a in A for b in B]

 where A and B are strings. (So cross("ab","12") is ["a1", "b1", 
 "a2", "b2"]).

 It's easy to get something that works the same in D, but I'd 
 like to make it as simple and short as possible. The best I 
 could come up with is


 string[] cross(string A, string B){
     string[] grid;
     foreach(t; cartesianProduct(A,B)){
         grid ~= (to!string(p[0]) ~ to!string(p[1]));


       }
       return grid;
}
Jan 17 2014
parent reply "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
I'd say

import std.algorithm;

auto cross(R1,R2)(R1 a, R2 b) {
	return cartesianProduct(a,b).map!"[a[0]]~[a[1]]"();
}

You can always:

import std.array;

auto strings = array(cross("ab","12"));


Although that won't give you a string[], but in a dchar[][].
Jan 17 2014
parent "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
On Saturday, 18 January 2014 at 07:56:15 UTC, Stanislav Blinov 
wrote:


 Although that won't give you a string[], but in a dchar[][].


...but that is solvable:

auto strings = array(cross("ab","12").map!"to!string(a)"());

Or maybe even by providing additional overload:

auto cross(alias fun,R1,R2)(R1 a, R2 b) {
   return cross(a,b).map!fun();
}

auto strings = array(cross!"to!string(a)"("ab","12"));
Jan 18 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
CJS:


 I'm trying to write a D function that does the same as this 
 Python function:

 def cross(A, B):
     "Cross product of elements in A and elements in B."
     return [a+b for a in A for b in B]

 where A and B are strings. (So cross("ab","12") is ["a1", "b1", 
 "a2", "b2"]).


One solution:


import std.stdio, std.conv, std.algorithm, std.array;

string[] cross(in string A, in string B) {
     return cartesianProduct(A, B).map!(ab => ab[].text).array;
}

void main() {
     cross("ab", "12").writeln;
}


But note that currently cartesianProduct doesn't return the pairs 
in a natural order.

cross() should be pure.

Bye,
bearophile
Jan 18 2014
parent reply "CJS" <Prometheus85 hotmail.com> writes:
 import std.stdio, std.conv, std.algorithm, std.array;

 string[] cross(in string A, in string B) {
     return cartesianProduct(A, B).map!(ab => ab[].text).array;
 }

 void main() {
     cross("ab", "12").writeln;
 }


 But note that currently cartesianProduct doesn't return the 
 pairs in a natural order.

 cross() should be pure.


Great. Here's a similar follow-up question. I'm trying to 
reproduce Peter Novig's Python code for solving Sudoku in D 
(http://norvig.com/sudoku.html). As a way to understand both his 
code and D/Phobos better. The entire code chunk I'm working on 
now is

def cross(A, B):
     "Cross product of elements in A and elements in B."
     return [a+b for a in A for b in B]

digits   = '123456789'
rows     = 'ABCDEFGHI'
cols     = digits
squares  = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
             [cross(r, cols) for r in rows] +
             [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs 
in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u])
              for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
              for s in squares)

Unfortunately my current best attemp doesn't compile:

import std.stdio : writeln;
import std.range : chunks, chain;
import std.algorithm;
import std.array;
import std.conv;

auto cross(R1, R2)(in R1 A, in R2 B){
     return cartesianProduct(A,B).map!(ab => ab[].text).array;
}


void main(){
     string letters = "ABCDEFGHI";
     string digits = "123456789";

     auto cols = digits;
     auto rows = letters;

     auto squares = cross(rows, cols);
     string[][] unitlist;
     foreach(c; cols){
         unitlist ~= cross(rows, to!string(c));
     }
     foreach(r; rows){
         unitlist ~= cross(to!string(r), cols);
     }
     foreach(r; chunks(rows, 3)){
         foreach(c; chunks(cols, 3)){
             unitlist ~= cross(to!string(r),to!string(c));
         }
     }

     string[][][string] units;
     string[][string] peers;

     foreach(s; squares){
         units[s] = filter!(x=>any!(y=>(s==y)))(unitlist);
     }

     foreach(s; squares){
         peers[s] = remove(chain(units[s]), s);
     }

}

Up until units and peers are defined it works, but I find the 
to!string conversions ugly. Because of cross being templated I 
don't think they should be necessary. Taking the cartesian 
product of a string with a character seems like a reasonable 
request. Simialrly, so does taking the cartesian product of a 
string with a range of characters.

For the associative arrays I'm unsure I have the correct calls, 
but they looked reasonable. Any suggestions?
Jan 18 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
CJS:


 Unfortunately my current best attemp doesn't compile:


What errors are you seeing?



 auto cross(R1, R2)(in R1 A, in R2 B){


Better to add a space before the open brace.
Also you may want to remove "in" if you want to use cross() on 
lazy ranges.



     return cartesianProduct(A,B).map!(ab => ab[].text).array;


And a space after the comma.



     string letters = "ABCDEFGHI";
     string digits = "123456789";


And a enum/const/immutable for variables that don't need to 
change.



         unitlist ~= cross(rows, to!string(c));


to!string(c)   ===>   c.text



         units[s] = filter!(x=>any!(y=>(s==y)))(unitlist);


Better to use UFCS here, don't forget spaces around operators:

units[s] = unitlist.filter!(x => any!(y => (s == y)));

And filter returns a lazy range, so perhaps that doesn't work.



 For the associative arrays I'm unsure I have the correct calls, 
 but they looked reasonable. Any suggestions?


Phobos needs a very handy set().

Bye,
bearophile
Jan 18 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 units[s] = unitlist.filter!(x => any!(y => (s == y)));


And you don't need a pair of ( ):

units[s] = unitlist.filter!(x => any!(y => s == y));

And now you need to feed any with some range.

Bye,
bearophile
Jan 18 2014
prev sibling parent reply "CJS" <Prometheus85 hotmail.com> writes:
 to!string(c)   ===>   c.text


That's more concise but I also think it's more confusing. I 
assume that to!string is doing the exact same thing, but I was 
hoping for something to do the appropriate implicit 
conversations. Especially to a range of length 1, though I can 
understand that kind of auto-magical conversion would be annoying 
in a number of important instances.

I changed the code to this:



import std.stdio : writeln;
import std.range : chunks, chain;
import std.algorithm;
import std.array;
import std.conv;

auto cross(R1, R2)(R1 A, R2 B) {
     return cartesianProduct(A, B).map!(ab => ab[].text).array;
}


void main(){
     const string letters = "ABCDEFGHI";
     const string digits = "123456789";

     auto cols = digits;
     auto rows = letters;

     auto squares = cross(rows, cols);
     string[][] unitlist;
     foreach(c; cols){
         unitlist ~= cross(rows, to!string(c));
     }
     foreach(r; rows){
         unitlist ~= cross(to!string(r), cols);
     }
     foreach(r; chunks(rows, 3)){
         foreach(c; chunks(cols, 3)){
             unitlist ~= cross(to!string(r),to!string(c));
         }
     }

     string[][][string] units;
     string[][string] peers;

     foreach(s; squares){
         units[s] = unitlist.filter!(x => any!(y => s==y)); \\line 
37
     }

     foreach(s; squares){
         peers[s] = remove(chain(units[s]), s); \\line 41
     }

}


On dmd 2.064.2 (downloaded and installed today) on 64-bit linux I 
get the following errors:

sudoku.d(37): Error: cannot resolve type for any!((y) => s == y)
/home/cjordan1/dmd2/linux/bin64/../../src/phobos/std/algorithm.d(1381): 
Error: template instance sudoku.main.__lambda1!(string[]) error 
instantiating
/home/cjordan1/dmd2/linux/bin64/../../src/phobos/std/algorithm.d(1369): 
        instantiated from here: FilterResult!(__lambda1, 
string[][])
sudoku.d(37):        instantiated from here: filter!(string[][])
/home/cjordan1/dmd2/linux/bin64/../../src/phobos/std/algorithm.d(1369): 
Error: template instance sudoku.main.FilterResult!(__lambda1, 
string[][]) error instantiating
sudoku.d(37):        instantiated from here: filter!(string[][])
sudoku.d(37): Error: template instance sudoku.main.filter!((x) => 
any!((y) => s == y)).filter!(string[][]) error instantiating
sudoku.d(41): Error: cannot implicitly convert expression 
(remove(chain(units[s]), s)) of type string[][] to string[]

  Lines 37 and 41 are noted in the above code.
Jan 18 2014
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
CJS:


         units[s] = unitlist.filter!(x => any!(y => s==y));


One of your problems is that any that needs some range to work on.

Bye,
bearophile
Jan 18 2014
prev sibling parent reply "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
On Sunday, 19 January 2014 at 02:10:01 UTC, CJS wrote:


 That's more concise but I also think it's more confusing. I 
 assume that to!string is doing the exact same thing, but I was 
 hoping for something to do the appropriate implicit 
 conversations. Especially to a range of length 1, though I can 
 understand that kind of auto-magical conversion would be 
 annoying in a number of important instances.


Does not compute. You mean implicit conversion of single 
character to a range?


 I changed the code to this:

 import std.stdio : writeln;
 import std.range : chunks, chain;
 import std.algorithm;
 import std.array;
 import std.conv;

 auto cross(R1, R2)(R1 A, R2 B) {
     return cartesianProduct(A, B).map!(ab => ab[].text).array;
 }


 void main(){
     const string letters = "ABCDEFGHI";
     const string digits = "123456789";

     auto cols = digits;
     auto rows = letters;

     auto squares = cross(rows, cols);
     string[][] unitlist;


You may want to use an appender here. It's more efficient than ~= 
, and lets you transform those foreach loops into one-liners :)

       auto app = appender(&unitlist);

       /+
       foreach(c; cols){
           unitlist ~= cross(rows, to!string(c));
       }
       foreach(r; rows){
           unitlist ~= cross(to!string(r), cols);
       }
       foreach(r; chunks(rows, 3)){
           foreach(c; chunks(cols, 3)){
               unitlist ~= cross(to!string(r),to!string(c));
           }
       }
       +/
       app.put(cols.map!(x => cross(rows, x.text)));
       app.put(rows.map!(x => cross(x.text, cols)));
       app.put(chunks(rows,3).map!(r => chunks(cols,3).map!(c => 
cross(r.text, c.text))));


     string[][][string] units;
     string[][string] peers;

     foreach(s; squares){
         units[s] = unitlist.filter!(x => any!(y => s==y)); 
 \\line 37
     }


This one seems like it should be unitlist.filter!(x => x.any!(y 
=> s==y)).array();


     foreach(s; squares){
         peers[s] = remove(chain(units[s]), s); \\line 41
     }


This one I don't understand. chain(units[s]) ? That's the same as 
units[s]. remove() returns a range, in this case string[][].
Jan 18 2014
parent reply "CJS" <Prometheus85 hotmail.com> writes:
Thanks!


       auto app = appender(&unitlist);


Ah, I'd been wondering if there was something like this. But why 
does it need unitlist's address? (Assume & has the same meaning 
as in C and C++.)


 This one seems like it should be unitlist.filter!(x => x.any!(y 
 => s==y)).array();


Oh. Duh. But what is the .array() at the end doing? Allocating a 
new array for the results of the filter, since it's basically 
just a lazily computed range rather than actual storage for the 
results?


    foreach(s; squares){
        peers[s] = remove(chain(units[s]), s); \\line 41
    }


 This one I don't understand. chain(units[s]) ? That's the same 
 as units[s]. remove() returns a range, in this case string[][].


I'm just trying to match what the python code was doing. In that 
case the line

peers = dict((s, set(sum(units[s],[]))-set([s]))
              for s in squares)

was using sum to concatenate a bunch of lists together and then 
remove the element. But I miscounted the parentheses and didn't 
notice the '-' was after the concatenated lists were tured into a 
set. The following code appears to do what I want, but the string 
temporary and appender are a bit ugly. Any suggestions on getting 
rid of them?

    foreach(s; squares){
         string[] tmp;
         auto app2 = appender(&tmp);
         foreach(t; units[s]) {app2.put(t);}
         peers[s] = tmp.sort().uniq().filter!(a => a!=s).array();
     }
Jan 18 2014
parent reply "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
On Sunday, 19 January 2014 at 06:57:37 UTC, CJS wrote:


 Ah, I'd been wondering if there was something like this. But 
 why does it need unitlist's address? (Assume & has the same 
 meaning as in C and C++.)


Look at the docs for Appender. It can either provide its own 
storage, or use an existing one. In the latter case you feed it a 
pointer to your array and it uses that.


 This one seems like it should be unitlist.filter!(x => 
 x.any!(y => s==y)).array();


 Oh. Duh. But what is the .array() at the end doing? Allocating 
 a new array for the results of the filter, since it's basically 
 just a lazily computed range rather than actual storage for the 
 results?


Yes. But in this case you'd have to allocate anyways, to fill the 
units[s] array.


 I'm just trying to match what the python code was doing. In 
 that case the line


Ah, I see.


 peers = dict((s, set(sum(units[s],[]))-set([s]))
              for s in squares)

 was using sum to concatenate a bunch of lists together and then 
 remove the element. But I miscounted the parentheses and didn't 
 notice the '-' was after the concatenated lists were tured into 
 a set. The following code appears to do what I want, but the 
 string temporary and appender are a bit ugly. Any suggestions 
 on getting rid of them?


	foreach(s; squares){
		peers[s] = units[s].join().sort().uniq().filter!(a => 
a!=s).array();
	}

That's std.array.join() there. However, I notice that the output 
(the order of elements) differs from the one on that page you 
linked earlier.
Jan 18 2014
parent "CJS" <Prometheus85 hotmail.com> writes:
 That's std.array.join() there. However, I notice that the 
 output (the order of elements) differs from the one on that 
 page you linked earlier.


The order shouldn't be a problem. Join is a great idea. I'd 
thought it was only for an array of strings. Thanks for all the 
help!
Jan 19 2014