Range of Ranges and std.algorithm

[Philippe Sigaud]

On Tue, Mar 16, 2010 at 17:35, Jesse Phillips
<jessekphillips+D at gmail.com<jessekphillips%2BD at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d-learn/attachments/20100317/eede2a51/attachment.htm>