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