Foreach[+A]

I like the simplicity of the Foreach interface in terms of unifying the difference between iterators and collections.   The biggest concern I have with collections in general is the fact that developers (especially the java ones) will know have to select the approrpiate level of abstraction for methods that use collections.  One thing I've noticed with Java is most people just use java.util.List (with a small subset using java.util.Collection) for all collection-related methods.   This is perhaps further propogated with frameworks like Hibernate. However, as of 2.8 the necessity of choice is back (along with some real power/flexibility).   Giving people sensible names along with great descriptions of what each provides, and then propogating this to the community will be important.   I think the last piece will be most difficult early on. 

Enough rambling, on to the point: Right now... I see Foreach and Traversable having conflicting goals.   The main differentiator (as far as I understand it) is that Foreach unifies Iterators and Collections (of which Traversable is one).  The traversable interface as it exists today assumes you can traverse multiple times, while an Iterator can only traverse once before it is exhausted.   This new Foreach interface provides a bridge between those two concepts.... Exhausting Foreach vs. Repeatable foreach (Traversable).

Does Repeatable foreach make sense in a mutable collection?  I can do the following today:

scala> import collection.mutable.ListBuffer
import collection.mutable.ListBuffer

scala> val x = new ListBuffer[Int]
x: scala.collection.mutable.ListBuffer[Int] = ListBuffer()

scala> x foreach {  item => x.remove(x.indexOf(item)) }

scala> x
res0: scala.collection.mutable.ListBuffer[Int] = ListBuffer()


If this is possible today... What's wrong with making Iterable *be* a Traversable... You can, in fact, traverse the iterator via foreach, and as seen above a foreach on a mutable object could exhaust the collection....




Also as a side note, I was starting to test out defining collections in terms of an early-exit foldable rather then foreach.  I think this might work better with asynchronous access collections....but wanted to try it out.   Of course, this is all based on the following: http://okmij.org/ftp/Streams.html. I'm not a huge fan of iterators anymore, and I hope this foldable/iteratee thign will pan out, but I'm nowhere near a place where I have any kind of evidence that this will provide a better option with simple interface.  If anyone thinks this has merit, let me know.  I have too many things on my plate as always, but this work is one of the expirements relating to I/O.



- Josh

On Fri, Mar 26, 2010 at 10:21 AM, Paul Phillips <paulp@improving.org> wrote:

Leading with a quote from the man himself[1]:

"Two aspects of software systems tend to accelerate bit rot: lack of
explicit design and code duplication."

Since truer words were never spoken, last night I decided to follow my
inclinations and find out if there was some obvious reason we couldn't
do what I wanted to the collections.  And one mostly red diff later I
never found the reason.  We create this interface:

trait Foreach[+A] {
 def foreach[U](f: A => U): Unit
 // there are a few more convenient methods here but only foreach is mandatory
}

Both Iterator and Traversable implement it.  Now we can perform this
transformation many times:

-  override def ++[B >: A, That](that: Traversable[B])(implicit bf: CanBuildFrom[Traversable[A], B, That]): That
-  override def ++[B >: A, That](that: Iterator[B])(implicit bf: CanBuildFrom[Traversable[A], B, That]): That
+  override def ++[B >: A, That](xs: Foreach[B])(implicit bf: CanBuildFrom[Traversable[A], B, That]): That

And that's not all! (NOW how much would you pay?) Here is the signature
of scala.util.Randomm.shuffle:

 def shuffle[T, CC[X] <: Traversable[X]](coll: CC[T])(implicit bf: CanBuildFrom[CC[T], T, CC[T]]): CC[T]

I can now change this to:

 def shuffle[T, CC[X] <: Foreach[X]](coll: CC[T])(implicit bf: CanBuildFrom[CC[T], T, CC[T]]): CC[T]

Don't even have to touch the implementation of the method[2], and now
this works:

scala> scala.util.Random.shuffle(1 to 5 iterator)
res0: Iterator[Int] = non-empty iterator

scala> res0 foreach println
4
5
1
2
3

So to me this seems like such a slam dunk that I'm already going into a
crouch to fend off the blow I don't see coming.  Why shouldn't we do
this? The whole branch can be seen here:

 http://github.com/paulp/scala/tree/foreach

There are probably more spots I can apply this, I was just going enough
for proof of concept.  The diff is here:

 http://github.com/paulp/scala/commit/072934073c0675d02111cb3f1f61e5be2368ceee

All tests pass, this thing is ready to fire.

[1] http://lampwww.epfl.ch/~odersky/papers/fsttcs2009.pdf
[2] ...but I did have to give Iterator a CanBuildFrom.

--
Paul Phillips      | A Sunday school is a prison in which children do
Vivid              | penance for the evil conscience of their parents.
Empiricist         |     -- H. L. Mencken
pull his pi pal!   |----------* http://www.improving.org/paulp/ *----------

On Fri, Mar 26, 2010 at 7:21 AM, Paul Phillips wrote:
> Leading with a quote from the man himself[1]:
>
> "Two aspects of software systems tend to accelerate bit rot: lack of
> explicit design and code duplication."
>
> Since truer words were never spoken, last night I decided to follow my
> inclinations and find out if there was some obvious reason we couldn't
> do what I wanted to the collections.  And one mostly red diff later I
> never found the reason.  We create this interface:
>
> trait Foreach[+A] {
>  def foreach[U](f: A => U): Unit
>  // there are a few more convenient methods here but only foreach is mandatory
> }
>
> Both Iterator and Traversable implement it.  Now we can perform this
> transformation many times:

I think I'm having deja vu:

http://www.scala-lang.org/node/2903

(I'm actually in the pro-Foreach camp, but I figured it was worth
bringing this up.)

On Fri, Mar 26, 2010 at 01:24:15PM -0700, David Hall wrote:
> I think I'm having deja vu:
>
> http://www.scala-lang.org/node/2903

Yeah, obviously it'd be hard for me to forget having already been shot
down in this quadrant. Yet the flaw was not the idea but the delivery.
I should have gone straight for the interface rather than halfheartedly
swimming around with conversions.

In any case, martin left the rest of you out of his reply, but we are
all systems go and I'm almost done. It's called TraversableOnce.

On Fri, Mar 26, 2010 at 04:13:57PM -0400, Josh Suereth wrote:
> If this is possible today... What's wrong with making Iterable *be* a
> Traversable...

On the presumption that is a typo and you mean "making Iterator be a
Traversable", this is undesirable for a number of reasons. We blur a
useful distinction and we add a lot of complexity weight to Iterator
when its one decent reason for existing is its simplicity. I'll have
this thing done quite soon and I think you'll find this hail mary hit
for the cycle of goodness on its way to being a slam dunk. But let me
know if that's inaccurate in any way.

Relatedly:
I've been messing around with the Map traits to make a wrapper for Nathan Bronson's SnapTree (Code: http://github.com/nbronson/snaptree, PDF: http://ppl.stanford.edu/papers/ppopp207-bronson.pdf). There's no mutable.SortedMap trait, so I was trying to define my own.
Unfortunately, MapLike and friends have methods like:  def ++[B1 >: B] (iter: Iterator[(A, B1)]): Map[A, B1] = which hard-code the return type to be collection.Map. This means mutable.MapLike needs to override it to narrow the return type to mutable.Map, as does immutable.MapLike, as does collection.SortedMapLike, as does... ad nauseam. 
The Seq hierarchy has gotten rid of this kind of repetition. Any chance this will get addressed in the Map hiererchy?
--j
On Fri, Mar 26, 2010 at 1:55 PM, Paul Phillips <paulp@improving.org> wrote:

On Fri, Mar 26, 2010 at 04:13:57PM -0400, Josh Suereth wrote:
> If this is possible today... What's wrong with making Iterable *be* a
> Traversable...

On the presumption that is a typo and you mean "making Iterator be a
Traversable", this is undesirable for a number of reasons.  We blur a
useful distinction and we add a lot of complexity weight to Iterator
when its one decent reason for existing is its simplicity.  I'll have
this thing done quite soon and I think you'll find this hail mary hit
for the cycle of goodness on its way to being a slam dunk.  But let me
know if that's inaccurate in any way.

--
Paul Phillips      | All men are frauds.  The only difference between
Protagonist        | them is that some admit it.  I myself deny it.
Empiricist         |     -- H. L. Mencken
up hill, pi pals!  |----------* http://www.improving.org/paulp/ *----------

I think OnceTraversable is a great option here, as it helps delineate the difference between itself and Traversable.  I guess my argument is that mutability blurs the line of what constitutes something that can be traversed more then once.  It's a very fragile guarantee.

In any case, I look forward to your upcoming commit.  It should help when defining interfaces in libraries.

- Josh

On Fri, Mar 26, 2010 at 4:55 PM, Paul Phillips <paulp@improving.org> wrote:

On Fri, Mar 26, 2010 at 04:13:57PM -0400, Josh Suereth wrote:
> If this is possible today... What's wrong with making Iterable *be* a
> Traversable...

On the presumption that is a typo and you mean "making Iterator be a
Traversable", this is undesirable for a number of reasons.  We blur a
useful distinction and we add a lot of complexity weight to Iterator
when its one decent reason for existing is its simplicity.  I'll have
this thing done quite soon and I think you'll find this hail mary hit
for the cycle of goodness on its way to being a slam dunk.  But let me
know if that's inaccurate in any way.

--
Paul Phillips      | All men are frauds.  The only difference between
Protagonist        | them is that some admit it.  I myself deny it.
Empiricist         |     -- H. L. Mencken
up hill, pi pals!  |----------* http://www.improving.org/paulp/ *----------

On Fri, Mar 26, 2010 at 10:34 PM, Jorge Ortiz <jorge.ortiz@gmail.com> wrote:

Relatedly:
I've been messing around with the Map traits to make a wrapper for Nathan Bronson's SnapTree (Code: http://github.com/nbronson/snaptree, PDF: http://ppl.stanford.edu/papers/ppopp207-bronson.pdf). There's no mutable.SortedMap trait, so I was trying to define my own.
Unfortunately, MapLike and friends have methods like:  def ++[B1 >: B] (iter: Iterator[(A, B1)]): Map[A, B1] = which hard-code the return type to be collection.Map. This means mutable.MapLike needs to override it to narrow the return type to mutable.Map, as does immutable.MapLike, as does collection.SortedMapLike, as does... ad nauseam. 
The Seq hierarchy has gotten rid of this kind of repetition. Any chance this will get addressed in the Map hiererchy?
--j

I tried but it seemed to be really hard, harder than in the seq case, even though I cannot remember anymore why. Anyway if someone makes a fresh attempt at solving this and succeeds, great!

Cheers

 -- Martin

Paul Phillips wrote:
> On Fri, Mar 26, 2010 at 04:13:57PM -0400, Josh Suereth wrote:
>
>> If this is possible today... What's wrong with making Iterable *be* a
>> Traversable...
>>
>
> On the presumption that is a typo and you mean "making Iterator be a
> Traversable", this is undesirable for a number of reasons. We blur a
> useful distinction and we add a lot of complexity weight to Iterator
> when its one decent reason for existing is its simplicity. I'll have
> this thing done quite soon and I think you'll find this hail mary hit
> for the cycle of goodness on its way to being a slam dunk. But let me
> know if that's inaccurate in any way.
>
>
I believe this question is directly addressed in the paper: The Essence
of the Iterator Pattern.

It is possible to get an Iterator/Iterable/OnceOnlyIterate from
Traversable but not the other way around.
Traversable => Iterator
Iterator =/=> Traversable

However, this uses a slightly different definition of Traversable than
the Scala library.

----

Scalaz has Each and Traverse. The usefulness of Traverse is greatly
increased in 2.8 with type constructor inference (thanks!).

trait Each[E[_]] {
def each[A](f: E[A] => Unit): Unit
}

trait Traverse[T[_]] extends Functor[T] {
def traverse[F[_]: Applicative, A, B](f: A => F[B], t: T[A]): F[T[B]]
}

Traverse is very much related to specialised functions that I see
occasionally such as:
* List[Option[A]] => Option[List[A]]
* Array[SomeTrait[A]] => SomeTrait[Array[A]]