• Jesse Phillips (19/19) Mar 16 2010 I'm guessing that containers will help with this, but I'm not sure how.
• Philippe Sigaud (39/54) Mar 17 2010 problem.
• Jesse Phillips (2/2) Mar 17 2010 Thank you, your fuse is a much cleaner way than how I did it and works

Jesse Phillips <jessekphillips+D gmail.com> writes:

I'm guessing that containers will help with this, but I'm not sure how.

Say I have an int[][] of unknown length and I want to get the setIntersection
of all int[]s. The only way I can see to do that is to intersect the first two
elements and iterate over them storing into an int[] which can be used in an
intersection with the next element...

I realize that a Range is meant to be view of a container, but it seems to me
that containing a Range can be just as useful. How might containers improve
this situation?


-----------------------------------
import std.algorithm;

void main() {
   auto lists = [[1,2,3,4,5],
                 [2,4,6,8,10],
                 [1,1,2,3,5]];

   //assert(setIntersection(lists) == [2]);
   
   auto result = setIntersection(lists[0], lists[1]);

   foreach(range; lists)
      result = setIntersection(result, range);
}

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

.\setint.d(13): Error: cannot implicitly convert expression (setIntersection(res
ult,range)) of type SetIntersection!(less,SetIntersection!(less,int[],int[]),int
[]) to SetIntersection!(less,int[],int[])

Philippe Sigaud <philippe.sigaud gmail.com> writes:

On Tue, Mar 16, 2010 at 17:35, Jesse Phillips
<jessekphillips+D gmail.com<jessekphillips%2BD gmail.com>
 wrote:

 I'm guessing that containers will help with this, but I'm not sure how.

 Say I have an int[][] of unknown length and I want to get the
 setIntersection of all int[]s. The only way I can see to do that is to
 intersect the first two elements and iterate over them storing into an int[]
 which can be used in an intersection with the next element...

 I realize that a Range is meant to be view of a container, but it seems to
 me that containing a Range can be just as useful. How might containers
 improve this situation?

 I don't know if containers can help, but ranges of ranges do exist, with no

problem.

auto lists = [[0,1,2,3], [4,5,6], [7], [], [8]];

auto mapped = map!((int[] arr) { return map!"a*a"(arr))(lists); // The
delegate literal takes an array and returns an array.

Here, the topology is preserved and you get back a range of ranges, with the
same lengths and rank

[[0,1,4,9], [16,25,36], [49], [], [64]]



 .\setint.d(13): Error: cannot implicitly convert expression
 (setIntersection(res
 ult,range)) of type
 SetIntersection!(less,SetIntersection!(less,int[],int[]),int
 []) to SetIntersection!(less,int[],int[])


SetIntersection is lazy: it works for ranges of unknown length, even
infinite ones, and calculates only the intersection elements that you ask
for. This means in D storing it in a struct, which has a type encoding the
entire operation.
So the type of result is indeed SetIntersection!(less, int[],int[]), whereas
a new application will wrap another layer around it. You have a matriochka
of types, which cannot be converted.

But you can 'collapse' the result using array() to get back an array, if
you're certain your result is finite in length. Let's call that fuse:

T[] fuse(T)(T[] a1, T[] a2) {
    return array(setIntersection(a1,a2));
}

What you're doing in your case is accumulating a result, so it's a
fold/reduce operation:

auto intersect = reduce ! fuse (lists);

Which works...

As setIntersection takes a variable number of ranges, it'd be interesting to
have a way to 'crack open' a range of ranges and transform it into a tuple
of ranges. The problem is, a tuple has a compile-time length. If lists was
an int[][3], you could make a template transforming it into a
TypeTuple!(int[],int[],int[]) that you can pass to setIntersection, opening
it with .expand.

But that's not possible in general for a dynamic array of dynamic arrays, as
its number of elements is only known at runtime. Maybe that's what you where
asking?

I did a recursive map a few weeks ago, wich maps a function on the innermost
elements of a range of ranges of ... of ranges.
I was looking for operations that preserve the topology (mapping on a tree
and returning a tree of the same shape).


  Philippe

Jesse Phillips <jessekphillips+D gmail.com> writes:

Thank you, your fuse is a much cleaner way than how I did it and works
with reduce.