• Jesse Phillips <jessekphillips+D gmail.com> Mar 16 2010
• Philippe Sigaud <philippe.sigaud gmail.com> Mar 17 2010
• Jesse Phillips <jessekphillips+D gmail.com> Mar 17 2010

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:

--0003255592bade5a61048204efee
Content-Type: text/plain; charset=ISO-8859-1

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



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

--0003255592bade5a61048204efee
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<br><br><div class=3D"gmail_quote">On Tue, Mar 16, 2010 at 17:35, Jesse Phi=
llips <span dir=3D"ltr">&lt;<a href=3D"mailto:jessekphillips%2BD gmail.com"=
jessekphillips+D gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"g=


 0pt 0pt 0.8ex; padding-left: 1ex;">
I&#39;m guessing that containers will help with this, but I&#39;m not sure =
how.<br>
<br>
Say I have an int[][] of unknown length and I want to get the setIntersecti=
on of all int[]s. The only way I can see to do that is to intersect the fir=
st two elements and iterate over them storing into an int[] which can be us=
ed in an intersection with the next element...<br>

<br>
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 impr=
ove this situation?<br>
<br></blockquote><div>I don&#39;t know if containers can help, but ranges o=
f ranges do exist, with no problem.<br><br>auto lists =3D [[0,1,2,3], [4,5,=
6], [7], [], [8]];<br><br>auto mapped =3D map!((int[] arr) { return map!&qu=
ot;a*a&quot;(arr))(lists); // The delegate literal takes an array and retur=
ns an array.<br>
<br>Here, the topology is preserved and you get back a range of ranges, wit=
h the same lengths and rank <br><br>[[0,1,4,9], [16,25,36], [49], [], [64]]=
<br><br>=A0</div><blockquote class=3D"gmail_quote" style=3D"border-left: 1p=
x solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<br>
.\setint.d(13): Error: cannot implicitly convert expression (setIntersectio=
n(res<br>
ult,range)) of type SetIntersection!(less,SetIntersection!(less,int[],int[]=
),int<br>
[]) to SetIntersection!(less,int[],int[])<br>
</blockquote></div><br><br>SetIntersection is lazy: it works for ranges of =
unknown length, even infinite ones, and calculates only the intersection el=
ements that you ask for. This means in D storing it in a struct, which has =
a type encoding the entire operation.<br>
So the type of result is indeed SetIntersection!(less, int[],int[]), wherea=
s a new application will wrap another layer around it. You have a matriochk=
a of types, which cannot be converted.<br><br>But you can &#39;collapse&#39=
; the result using array() to get back an array, if you&#39;re certain your=
 result is finite in length. Let&#39;s call that fuse:<br>
<br>T[] fuse(T)(T[] a1, T[] a2) {<br>=A0=A0=A0 return array(setIntersection=
(a1,a2));<br>}<br><br>What you&#39;re doing in your case is accumulating a =
result, so it&#39;s a fold/reduce operation:<br><br>auto intersect =3D redu=
ce ! fuse (lists);<br>
<br>Which works...<br><br>As setIntersection takes a variable number of ran=
ges, it&#39;d be interesting to have a way to &#39;crack open&#39; 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 templ=
ate transforming it into a TypeTuple!(int[],int[],int[]) that you can pass =
to setIntersection, opening it with .expand.<br>
<br>But that&#39;s not possible in general for a dynamic array of dynamic a=
rrays, as its number of elements is only known at runtime. Maybe that&#39;s=
 what you where asking?<br><br>I did a recursive map a few weeks ago, wich =
maps a function on the innermost elements of a range of ranges of ... of ra=
nges.<br>
I was looking for operations that preserve the topology (mapping on a tree =
and returning a tree of the same shape).<br><br><br>=A0 Philippe<br><br><br=
<br>


--0003255592bade5a61048204efee--

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.