## digitalmars.D.learn - Range of Ranges and std.algorithm

- 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

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[])

Mar 16 2010

--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"><<a href=3D"mailto:jessekphillips%2BD gmail.com"=jessekphillips+D gmail.com</a>></span> wrote:<br><blockquote class=3D"g=

0pt 0pt 0.8ex; padding-left: 1ex;"> I'm guessing that containers will help with this, but I'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'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"(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 '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:<br> <br>T[] fuse(T)(T[] a1, T[] a2) {<br>=A0=A0=A0 return array(setIntersection= (a1,a2));<br>}<br><br>What you're doing in your case is accumulating a = result, so it'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'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 templ= ate transforming it into a TypeTuple!(int[],int[],int[]) that you can pass = to setIntersection, opening it with .expand.<br> <br>But that'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'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--

Mar 17 2010

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

Mar 17 2010