You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@jena.apache.org by Andy Seaborne <an...@apache.org> on 2011/09/27 10:56:07 UTC
Iter.mapMany
Stephen,
I took the liberty of rewriting the implementation of Iter.mapMany - it
didn't cope with the case where one of the sub-iterators returned was
zerolength because it created the iterator and immediately called .next().
The situation occurred in the SPARQL WG test suite for Update, where a
binding didn't generate any legal quads.(TemplateLib.calcQuads).
Where did the name "mapMany" come from? It's called "flatMap in scala.
The implement of flatmap is shorter :-) ... and recursive (the while
loop in mapMany is removing that tail recursion).
Andy
scala.collection.Iterator[A]
def flatMap[B](f: A => GenTraversableOnce[B]): Iterator[B]
= new Iterator[B] {
private var cur: Iterator[B] = empty
def hasNext: Boolean =
cur.hasNext || self.hasNext &&
{ cur = f(self.next).toIterator; hasNext }
def next(): B = (if (hasNext) cur else empty).next()
}
Re: Iter.mapMany
Posted by Andy Seaborne <an...@apache.org>.
On 27/09/11 15:58, Stephen Allen wrote:
>> -----Original Message-----
>> From: Andy Seaborne [mailto:andy@apache.org]
>> Sent: Tuesday, September 27, 2011 4:56 AM
>> To: jena-dev@incubator.apache.org
>> Subject: Iter.mapMany
>>
>> Stephen,
>>
>> I took the liberty of rewriting the implementation of Iter.mapMany - it
>> didn't cope with the case where one of the sub-iterators returned was
>> zerolength because it created the iterator and immediately called
>> .next().
>>
>> The situation occurred in the SPARQL WG test suite for Update, where a
>> binding didn't generate any legal quads.(TemplateLib.calcQuads).
>>
>
> Sounds good. Not enough tests I guess!
>
>>
>> Where did the name "mapMany" come from? It's called "flatMap in scala.
>>
>
> I called it "mapMany", because I was used to the equivalent C# LINQ operator called "SelectMany" [1]. LINQ's version of "Select" is called "map" in ARQ, so I went with "mapMany".
>
>
>> The implement of flatmap is shorter :-) ... and recursive (the while
>> loop in mapMany is removing that tail recursion).
>>
>> Andy
>>
>> scala.collection.Iterator[A]
>>
>> def flatMap[B](f: A => GenTraversableOnce[B]): Iterator[B]
>> = new Iterator[B] {
>> private var cur: Iterator[B] = empty
>> def hasNext: Boolean =
>> cur.hasNext || self.hasNext&&
>> { cur = f(self.next).toIterator; hasNext }
>> def next(): B = (if (hasNext) cur else empty).next()
>> }
>
> Oh, to have optimized tail recursion in Java! We can hope it arrives soon.
+1
As far as I can see, this tail recursion does not have problems that are
stopping it else where (tail jumps and trampolining).
> Incidentally, I find C#'s implementation even more elegant (argument checking elided):
>
> public static IEnumerable<TResult> SelectMany<TSource, TResult>(
> this IEnumerable<TSource> source,
> Func<TSource, IEnumerable<TResult>> selector)
> {
> foreach (TSource item in source)
> {
> foreach (TResult result in selector(item))
> {
> yield return result;
> }
> }
> }
>
> This relies on C#'s yield generator [2], which makes creating iterators so much simpler!
yes - it comes from CLU. Some of the web descriptions call it
coroutines but you can do that style yield-iterator on the same call stack.
You have to have compiler/VM support though - there are stackframes in
front of the active stack front when yield-iterators are active. A call
inside the body of the iterator must put it's frame ahead of the
iterators ... or else.
In scala, it can be one line:
iter.map(a => func(a) ).flatten
or even
iter.map(func(_)).flatten
which I get it down to:
def flatMap2[A,B](iter:Iterator[A],func: A => Iterator[B])
: Iterator[B] = iter.map(func(_)).flatten
I expect the Iterator.flatMap was written with a very careful eye to
efficiency. If you look at Iterator.flatten, is has the same pattern as
the scala library Iterator.flatMap.
I think the one liner it's going to evaluate all the input iterator
first in the .map.
Andy
>
> -Steve
>
> [1] http://msdn.microsoft.com/en-us/library/bb534336.aspx
> [2] http://msdn.microsoft.com/en-us/library/9k7k7cf0(v=VS.100).aspx
>
>
>
>
RE: Iter.mapMany
Posted by Stephen Allen <sa...@bbn.com>.
> -----Original Message-----
> From: Andy Seaborne [mailto:andy@apache.org]
> Sent: Tuesday, September 27, 2011 4:56 AM
> To: jena-dev@incubator.apache.org
> Subject: Iter.mapMany
>
> Stephen,
>
> I took the liberty of rewriting the implementation of Iter.mapMany - it
> didn't cope with the case where one of the sub-iterators returned was
> zerolength because it created the iterator and immediately called
> .next().
>
> The situation occurred in the SPARQL WG test suite for Update, where a
> binding didn't generate any legal quads.(TemplateLib.calcQuads).
>
Sounds good. Not enough tests I guess!
>
> Where did the name "mapMany" come from? It's called "flatMap in scala.
>
I called it "mapMany", because I was used to the equivalent C# LINQ operator called "SelectMany" [1]. LINQ's version of "Select" is called "map" in ARQ, so I went with "mapMany".
> The implement of flatmap is shorter :-) ... and recursive (the while
> loop in mapMany is removing that tail recursion).
>
> Andy
>
> scala.collection.Iterator[A]
>
> def flatMap[B](f: A => GenTraversableOnce[B]): Iterator[B]
> = new Iterator[B] {
> private var cur: Iterator[B] = empty
> def hasNext: Boolean =
> cur.hasNext || self.hasNext &&
> { cur = f(self.next).toIterator; hasNext }
> def next(): B = (if (hasNext) cur else empty).next()
> }
Oh, to have optimized tail recursion in Java! We can hope it arrives soon. Incidentally, I find C#'s implementation even more elegant (argument checking elided):
public static IEnumerable<TResult> SelectMany<TSource, TResult>(
this IEnumerable<TSource> source,
Func<TSource, IEnumerable<TResult>> selector)
{
foreach (TSource item in source)
{
foreach (TResult result in selector(item))
{
yield return result;
}
}
}
This relies on C#'s yield generator [2], which makes creating iterators so much simpler!
-Steve
[1] http://msdn.microsoft.com/en-us/library/bb534336.aspx
[2] http://msdn.microsoft.com/en-us/library/9k7k7cf0(v=VS.100).aspx