On 27/09/11 15:58, Stephen Allen wrote:
-----Original Message-----
From: Andy Seaborne [mailto:[email protected]]
Sent: Tuesday, September 27, 2011 4:56 AM
To: [email protected]
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
