Why Iterators ever?

If you want to be able to traverse a tree in pre, in and post order without creating new trees?

On Wed, Dec 7, 2011 at 12:18 PM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Dear all,

Having finished Chapter 24 of PinS, I apparently fail to see any
reason why anyone would ever prefer Iterators over containers and the
algorithms they support. Would anyone here please provide a good
motivating example -- perhaps one that they use in real-world Scala
frequently? Why would anyone basically want to restrict themselves to
single traversals at all?

TIA,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

iterator.continuously(...) or what it's called is one thing no collection can do. you can use iterators to dynamically calculate elements that don't need to be/can't be in a collection

-------- Original-Nachricht --------
> Datum: Wed, 7 Dec 2011 12:18:32 +0100
> Von: "Seyed H. HAERI (Hossein)"
> An: scala-user
> Betreff: [scala-user] Why Iterators ever?

> Dear all,
>
> Having finished Chapter 24 of PinS, I apparently fail to see any
> reason why anyone would ever prefer Iterators over containers and the
> algorithms they support. Would anyone here please provide a good
> motivating example -- perhaps one that they use in real-world Scala
> frequently? Why would anyone basically want to restrict themselves to
> single traversals at all?
>
> TIA,
> --Hossein
>
> --------------------------------------------------------------------------------------------------------------
>
> Seyed H. HAERI (Hossein)
>
> Research Assistant
> Institute for Software Systems (STS)
> Technical University of Hamburg (TUHH)
> Hamburg, Germany
>
> ACCU - Professionalism in programming - http://www.accu.org/
> --------------------------------------------------------------------------------------------------------------

Hi Viktor,

> If you want to be able to traverse a tree in pre, in and post order without creating new trees?

The only tree-like data structures I know so far of in Scala are Tree
Sets/Maps, Vectors, Hash Tries. AFAIK, none of these accepts a
traversal order. Neither does Iterator. So, I'm confused. Or, did you
not mean the Scala API's data structures? Anyway, maybe an example
could help here.

TIA,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

for example, i have a custom tree structure that supports range queries ("give me all values that close to a particular point (spatially)") -- that's a perfect case for an iterator. i have another one which keeps elements sorted with O(1) order comparison. it needs occasional relabelings, and the using instance of that structure gets an iterator of the elements which are going to be relabelled (without exhibiting the internals of the datastructure).

iterators are useful when you have a particular strategy of traversing an existing data structure, but you want to avoid building a separate structure just to represent that traversal. they can also hide implementation details, e.g. perform an internal mapping of the values over which it iterates.

best, -sciss-

On 7 Dec 2011, at 12:41, Seyed H. HAERI (Hossein) wrote:

> Hi Viktor,
>
>> If you want to be able to traverse a tree in pre, in and post order without creating new trees?
>
> The only tree-like data structures I know so far of in Scala are Tree
> Sets/Maps, Vectors, Hash Tries. AFAIK, none of these accepts a
> traversal order. Neither does Iterator. So, I'm confused. Or, did you
> not mean the Scala API's data structures? Anyway, maybe an example
> could help here.
>
> TIA,
> --Hossein
>
> --------------------------------------------------------------------------------------------------------------
>
> Seyed H. HAERI (Hossein)
>
> Research Assistant
> Institute for Software Systems (STS)
> Technical University of Hamburg (TUHH)
> Hamburg, Germany
>
> ACCU - Professionalism in programming - http://www.accu.org/
> --------------------------------------------------------------------------------------------------------------

Just today i had a use-case: I want to traverse a data structure driven by a “list” of items. Passing around iterators obviates the need for creating new (smaller) collections at each step; since the code in question is kind of a hot path, I would rather not have that many allocations happening on it, so one Iterator seems like a decent compromise between performance and readability (the alternative being to pass around an IndexedSeq and an index).

Regards,

Roland

Am Mittwoch, 7. Dezember 2011 12:18:32 UTC+1 schrieb Hossein:

Dear all,

Having finished Chapter 24 of PinS, I apparently fail to see any
reason why anyone would ever prefer Iterators over containers and the
algorithms they support. Would anyone here please provide a good
motivating example -- perhaps one that they use in real-world Scala
frequently? Why would anyone basically want to restrict themselves to
single traversals at all?

TIA,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

in particular if the using instance is only interested in part of the iterator! e.g. a hierarchical data structure which can return an iterator of the elements in some order -- you may just want to get the 'lowest ten elements'. simple: sortedSet.iterator.take(10).toList -- no need to build the whole list and throw away 99999990 elements unused.

best, -sciss-

On 7 Dec 2011, at 12:46, Sciss wrote:

> but you want to avoid building a separate structure just to represent that traversal.

Hi Dennis,

> iterator.continuously(...) or what it's called is one thing no collection can do.

Having just double-checked Table 24.12 in PinS (Operations in trait
Iterator), found nothing which looks similar. Would you mind
double-checking?

> you can use iterators to dynamically calculate elements that don't need to be/can't be in a collection

Like?

TIA,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

On Wed, Dec 7, 2011 at 09:18, Seyed H. HAERI (Hossein)
wrote:
> Dear all,
>
> Having finished Chapter 24 of PinS, I apparently fail to see any
> reason why anyone would ever prefer Iterators over containers and the
> algorithms they support. Would anyone here please provide a good
> motivating example -- perhaps one that they use in real-world Scala
> frequently? Why would anyone basically want to restrict themselves to
> single traversals at all?

Because the single traversal case happens often enough. For instance,
most methods in all of the collections are actually implemented
through an iterator. See
https://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src//library/scal...
and other methods in that trait. Take a look also at methods defined
at a more basic level, such as map:
https://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src//library/scal....
See how it is implemented in terms of foreach, which is implemented in
terms of iterator?

But let's ignore that as an internal mechanism of collections.
Iterators give you two big advantages:

1. You do not keep all the data in memory. That's why io.Source is an
Iterator, for example -- you do not need to keep all of the file in
memory. In fact, you don't even need to read all of the files. If
Source was a collection, that wouldn't be the case. The method
permutation is another one that benefits from the same principle.

2. You can accumulate any number of operations without creating
intermediate results in memory. When you accumulate operations on an
Iterator, these operations are stacked, so that they all get applied
element-by-element when you actually use the Iterator. This can be a
huge performance benefit.

Both benefits can be had with Stream, but Stream is much heavier, and
it is difficult to use in a manner that guarantees you won't be
keeping all of it in memory.

>
> TIA,
> --Hossein
>
> --------------------------------------------------------------------------------------------------------------
>
> Seyed H. HAERI (Hossein)
>
> Research Assistant
> Institute for Software Systems (STS)
> Technical University of Hamburg (TUHH)
> Hamburg, Germany
>
> ACCU - Professionalism in programming - http://www.accu.org/
> --------------------------------------------------------------------------------------------------------------

A good example would be a stream of random numbers for use in cryptography, possibly from a quantum-level/hardware source.
Other possibility would be an audio stream getting compressed, with both the input and output being iterators.
In fact, most places where you'd normally think "stream", what you really want is an iterator.



On 7 December 2011 12:46, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Hi Dennis,

> iterator.continuously(...) or what it's called is one thing no collection can do.

Having just double-checked Table 24.12 in PinS (Operations in trait
Iterator), found nothing which looks similar. Would you mind
double-checking?

> you can use iterators to dynamically calculate elements that don't need to be/can't be in a collection

Like?

TIA,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

it's not in the trait, it's in the companion object

-------- Original-Nachricht --------
> Datum: Wed, 7 Dec 2011 12:56:21 +0000
> Von: Kevin Wright
> An: "Seyed H. HAERI (Hossein)"
> CC: scala-user
> Betreff: Re: [scala-user] Why Iterators ever?

> A good example would be a stream of random numbers for use in
> cryptography,
> possibly from a quantum-level/hardware source.
>
> Other possibility would be an audio stream getting compressed, with both
> the input and output being iterators.
>
> In fact, most places where you'd normally think "stream", what you really
> want is an iterator.
>
>
>
> On 7 December 2011 12:46, Seyed H. HAERI (Hossein)
> wrote:
>
> > Hi Dennis,
> >
> > > iterator.continuously(...) or what it's called is one thing no
> > collection can do.
> >
> > Having just double-checked Table 24.12 in PinS (Operations in trait
> > Iterator), found nothing which looks similar. Would you mind
> > double-checking?
> >
> > > you can use iterators to dynamically calculate elements that don't
> need
> > to be/can't be in a collection
> >
> > Like?
> >
> > TIA,
> > --Hossein
> >
> >
> >
> --------------------------------------------------------------------------------------------------------------
> >
> > Seyed H. HAERI (Hossein)
> >
> > Research Assistant
> > Institute for Software Systems (STS)
> > Technical University of Hamburg (TUHH)
> > Hamburg, Germany
> >
> > ACCU - Professionalism in programming - http://www.accu.org/
> >
> >
> --------------------------------------------------------------------------------------------------------------
> >

Hi Daniel,

> But let's ignore that as an internal mechanism of collections.

OK, here seems to be my big gotwa! In C++ too, we have all the
efficiency concerns people mentioned in favour of iterators. Yet, the
marvellous decoupling of algorithms and containers -- which becomes
possible through the magic of iterators -- enables us to implement
each algorithm only once and for every container it applies to. This
is an unparalleled flavour of Generic Programming that is ubiquitous
in today's C++ via STL and much more.

Whilst reading PinS and throughout all the responses chaps gave over
this thread, I was wondering why is it that in presence of the same
concerns in C++, our Scala brothers have failed to choose a similar
single-implementation magic for their iterator classes? Why do they
implement every method for every container repeatedly and then have
iterator on top of all that? Apparently, the answer is right here: All
the container methods are defined in terms of iterator ones under the
hood. On the other hand, given that unlike C++, everything in Scala
lives in an OOP world, the stand-alone C++ algorithms were obliged to
become members of Iterator.

Having all that said, I am surprised to how restricted Scala iterators
are in comparison to the C++ ones. See here for an old -- but still
correct -- classification of the 1998 C++ iterators:

http://www.sgi.com/tech/stl/Iterators.html

This is in pre-concepts days of C++ -- although Concepts are still not
formally in the game either. I would be very enthusiastic to know
whether in Scala there is any Type Class business around iterators?
(Concepts in C++ == Type Classes in Haskell =?= Type Classes in
Scala.)

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

In C++ All the abstractions assume some form of iterator traversal.   In Scala we have Traversable and TraversableOnce which are *Good Things(TM)* IMHO.   A Traversable exposes the "foreach" method that can traverse a collection, but does not care how this is done.   For trees, you can expose three Traversables (inorder, postorder, preorder) that know how to traverse the original tree and don't have much overhead.
Combined with views, this gives us a lot of flexibility to right efficient collection methods using the declarative style that Scala favors.  You get *more* benefits than C++, in general.
However, there are still times when you really just want an iterator for some reason.  These are safer against immutable collections, but still have a lot of flaws (like the underlying collection wanting to disappear or change behind the iterator).   
So, while there are some valid use cases for Iterator, I think your intuition is right.  Don't reach for iterator out of habit if another method can do what you want in a simpler way.
- Josh

On Wed, Dec 7, 2011 at 8:30 AM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Hi Daniel,

> But let's ignore that as an internal mechanism of collections.

OK, here seems to be my big gotwa! In C++ too, we have all the
efficiency concerns people mentioned in favour of iterators. Yet, the
marvellous decoupling of algorithms and containers -- which becomes
possible through the magic of iterators -- enables us to implement
each algorithm only once and for every container it applies to. This
is an unparalleled flavour of Generic Programming that is ubiquitous
in today's C++ via STL and much more.

Whilst reading PinS and throughout all the responses chaps gave over
this thread, I was wondering why is it that in presence of the same
concerns in C++, our Scala brothers have failed to choose a similar
single-implementation magic for their iterator classes? Why do they
implement every method for every container repeatedly and then have
iterator on top of all that? Apparently, the answer is right here: All
the container methods are defined in terms of iterator ones under the
hood. On the other hand, given that unlike C++, everything in Scala
lives in an OOP world, the stand-alone C++ algorithms were obliged to
become members of Iterator.

Having all that said, I am surprised to how restricted Scala iterators
are in comparison to the C++ ones. See here for an old -- but still
correct -- classification of the 1998 C++ iterators:

http://www.sgi.com/tech/stl/Iterators.html

This is in pre-concepts days of C++ -- although Concepts are still not
formally in the game either. I would be very enthusiastic to know
whether in Scala there is any Type Class business around iterators?
(Concepts in C++ == Type Classes in Haskell =?= Type Classes in
Scala.)

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Hi Josh,

[MY WORDS BELOW ARE NOT TO PROVE SUPERIORITY OF C++ OVER SCALA. ONLY
FOR MYSELF TO UNDERSTAND THE COMPARISON BETTER. PLEASE DON'T TAKE ME
WRONG; THIS IS NOT A LANGUAGE WAR.]

> A Traversable exposes the "foreach" method that can traverse a collection, but does not care how this is done.

All STL algorithms in C++ traverse the iterator range they are given
and they don't care how this traversal business is done.

> For trees, you can expose three Traversables (inorder, postorder, preorder) that know how to traverse the original tree and don't have much overhead.

And, you can have three iterators types in_iterator, post_iterator,
and pre_iterator, each of which to traverse your tree in their
designated way, and, all of which equally applicable to all the
relevant STL (or any generic) algorithms.

> Combined with views, this gives us a lot of flexibility to right efficient collection methods using the declarative style that Scala favors. You get *more* benefits than C++, in general.

Can I have some examples?

TIA,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

I looked through "Scala for the Impatient", and found iterators in the
following situations:

1) Source.fromFile(filename).getLines returns an Iterator[String]

You might want to process the file a line at a time, without a need to
store all lines.

If you want to store all lines, just call toArray on the iterator.

2) Regex.findAllIn returns an iterator through all matches.

Again, you might not care about all matches, so it won't compute them
until you need them.

3) Several methods in Iterable and Seq yield iterators through complex
results: grouped, sliding, permutations, combinations.

It would be expensive to store the results in a collection.

So, I agree with you that most of the time, you just want to work with
collections. The iterators are there for the less common case in which
a result is expensive to collect.

In Scala, it's pleasant that many of the collection algorithms work on
iterators as well. Of course, you need to realize that they exhaust
the iterator since you can't reset it. If you need to make more than
one pass, just call toArray, toMap, etc.

Cheers,

Cay

On Wed, Dec 7, 2011 at 3:18 AM, Seyed H. HAERI (Hossein)
wrote:
> Dear all,
>
> Having finished Chapter 24 of PinS, I apparently fail to see any
> reason why anyone would ever prefer Iterators over containers and the
> algorithms they support. Would anyone here please provide a good
> motivating example -- perhaps one that they use in real-world Scala
> frequently? Why would anyone basically want to restrict themselves to
> single traversals at all?
>
> TIA,
> --Hossein
>
> --------------------------------------------------------------------------------------------------------------
>
> Seyed H. HAERI (Hossein)
>
> Research Assistant
> Institute for Software Systems (STS)
> Technical University of Hamburg (TUHH)
> Hamburg, Germany
>
> ACCU - Professionalism in programming - http://www.accu.org/
> --------------------------------------------------------------------------------------------------------------

Hi Cay,

> I looked through "Scala for the Impatient", and found iterators in the following situations:

Yes, that was a nice list. Thanks. :)

> Of course, you need to realize that they exhaust the iterator since you can't reset it. If you need to make more than one pass, just call toArray, toMap, etc.

This is one of the places where C++ iterators categorically outshine
their Scala counterparts. From a user's point of view the
single-traversal restriction causes a lot of difficulty. My guess is
though that this facilitates program correctness in the same way that
pure Function code tends to generally do. I'm not sure whether this
also has some benefits to the language/library implementers too or
not...

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

isn't this easily fixable by providing a generator for iterators and pass that one intead of the iterator?

-------- Original-Nachricht --------
> Datum: Wed, 7 Dec 2011 15:30:44 +0100
> Von: "Seyed H. HAERI (Hossein)"
> An: scala-user
> Betreff: Re: [scala-user] Why Iterators ever?

> Hi Cay,
>
> > I looked through "Scala for the Impatient", and found iterators in the
> following situations:
>
> Yes, that was a nice list. Thanks. :)
>
> > Of course, you need to realize that they exhaust the iterator since you
> can't reset it. If you need to make more than one pass, just call toArray,
> toMap, etc.
>
> This is one of the places where C++ iterators categorically outshine
> their Scala counterparts. From a user's point of view the
> single-traversal restriction causes a lot of difficulty. My guess is
> though that this facilitates program correctness in the same way that
> pure Function code tends to generally do. I'm not sure whether this
> also has some benefits to the language/library implementers too or
> not...
>
> Cheers,
> --Hossein
>
> --------------------------------------------------------------------------------------------------------------
>
> Seyed H. HAERI (Hossein)
>
> Research Assistant
> Institute for Software Systems (STS)
> Technical University of Hamburg (TUHH)
> Hamburg, Germany
>
> ACCU - Professionalism in programming - http://www.accu.org/
> --------------------------------------------------------------------------------------------------------------

On Wed, Dec 7, 2011 at 9:04 AM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Hi Josh,

[MY WORDS BELOW ARE NOT TO PROVE SUPERIORITY OF C++ OVER SCALA. ONLY
FOR MYSELF TO UNDERSTAND THE COMPARISON BETTER. PLEASE DON'T TAKE ME
WRONG; THIS IS NOT A LANGUAGE WAR.]

> A Traversable exposes the "foreach" method that can traverse a collection, but does not care how this is done.

All STL algorithms in C++ traverse the iterator range they are given
and they don't care how this traversal business is done.

But they do.  There are a few guarantees in C++ iterators that are not there for Scala foreach implementations.  Specifically:
(1) They have to know when they are finished. (implement a .end() on the collection)(2) They have to be able to repeatedly obtain a single value.(3) The *user* determine when to iterate and when he is done.

Take a look at this traversable:
class FileLinesTraversable(file: java.io.File) extends Traversable[String] {  override def foreach[U](f: String => U): Unit = {      val in = new java.io.BufferedReader(new java.io.FileReader(file))     try {       def loop(): Unit = in.readLine match {          case null => ()          case line => f(line); loop()        }       loop()     } finally {       in.close()     }  }} 
We now have a collection of lines in a file.  When I iterate over the collection is will *open* the file first, allow me to perform some operations and *close* the file when I'm done.
I can combine this with views:
val lines = new FileLineTraversable(new java.io.File("tmp.txt"))val withoutComments = lines.view filterNot (_ startsWith "#")
Now the value 'withoutComments" reverse to a collection that will open a file, parse for lines not starting with the # character, and give me the remaining lines.  I have not yet opened a file or performed any calculations.
I can then do:
withoutComments take 10 force // Explicitly reads the first 10 non comment lines and returns a new collection.   The data has been read, and remains in memory now.

The other bit here is that even though "foreach" is implemented to read the entire file, the "take" method will break out early and case the finally block to close the file.  Your efficiency is the same as if you used an iterator and closed the file by hand (I have benchmarks in SPerformance).
Doing this same thing in C++ becomes a nightmare of unreadable code (I've tried).   So, while the STL is great, Scala's collections are far superior.  "TraversableOnce" Is a far better lowest level abstraction than "Iterator" with "Traversable" also being a better abstraction than "Iterable".  If you understand Traversable and how to implement foreach, you can accomplish *a lot* of handy code.
- Josh

> For trees, you can expose three Traversables (inorder, postorder, preorder) that know how to traverse the original tree and don't have much overhead.

And, you can have three iterators types in_iterator, post_iterator,
and pre_iterator, each of which to traverse your tree in their
designated way, and, all of which equally applicable to all the
relevant STL (or any generic) algorithms.

> Combined with views, this gives us a lot of flexibility to right efficient collection methods using the declarative style that Scala favors. You get *more* benefits than C++, in general.

Can I have some examples?

TIA,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Might be. But, my words below apply to the Iterator class as it
currently is. I would be more than delighted to see that
single-traversal restriction removed using any rational technique...
:)

On 7 December 2011 15:33, Dennis Haupt wrote:
> isn't this easily fixable by providing a generator for iterators and pass that one intead of the iterator?
>
> -------- Original-Nachricht --------
>> Datum: Wed, 7 Dec 2011 15:30:44 +0100
>> Von: "Seyed H. HAERI (Hossein)"
>> An: scala-user
>> Betreff: Re: [scala-user] Why Iterators ever?
>
>> Hi Cay,
>>
>> > I looked through "Scala for the Impatient", and found iterators in the
>> following situations:
>>
>> Yes, that was a nice list. Thanks. :)
>>
>> > Of course, you need to realize that they exhaust the iterator since you
>> can't reset it. If you need to make more than one pass, just call toArray,
>> toMap, etc.
>>
>> This is one of the places where C++ iterators categorically outshine
>> their Scala counterparts. From a user's point of view the
>> single-traversal restriction causes a lot of difficulty. My guess is
>> though that this facilitates program correctness in the same way that
>> pure Function code tends to generally do. I'm not sure whether this
>> also has some benefits to the language/library implementers too or
>> not...
>>
>> Cheers,
>> --Hossein
>>
>> --------------------------------------------------------------------------------------------------------------
>>
>> Seyed H. HAERI (Hossein)
>>
>> Research Assistant
>> Institute for Software Systems (STS)
>> Technical University of Hamburg (TUHH)
>> Hamburg, Germany
>>
>> ACCU - Professionalism in programming - http://www.accu.org/
>> --------------------------------------------------------------------------------------------------------------

well, use Iterable then. i don't see the problem, honestly.

On 7 Dec 2011, at 14:30, Seyed H. HAERI (Hossein) wrote:

>>
>> Of course, you need to realize that they exhaust the iterator since you can't reset it. If you need to make more than one pass, just call toArray, toMap, etc.
>
> This is one of the places where C++ iterators categorically outshine
> their Scala counterparts.

On Wed, Dec 7, 2011 at 12:30, Seyed H. HAERI (Hossein)
wrote:
>
> All STL algorithms in C++ traverse the iterator range they are given
> and they don't care how this traversal business is done.

Yes, and that requires you to produce an iterator for every algorithm
you want to apply to a collection. Why go to such trouble? Why not
have all these algorithms implemented in the collection itself?

The interesting thing about Scala collections is that code reuse is
very, very high. Notice how the "map" method is actually implemented
at the Traversable level? There's even a lot of code that is inherited
from the TraversableOnce level, which is *share* by collections and
iterators. There's a LOT of code reuse in Scala.

>
>> Of course, you need to realize that they exhaust the iterator since you can't reset it. If you need to make more than one pass, just call toArray, toMap, etc.
>
> This is one of the places where C++ iterators categorically outshine
> their Scala counterparts. From a user's point of view the
> single-traversal restriction causes a lot of difficulty. My guess is
> though that this facilitates program correctness in the same way that
> pure Function code tends to generally do. I'm not sure whether this
> also has some benefits to the language/library implementers too or
> not...

But that's because you are breaking the abstraction at the wrong
point. Consider this snippet:

vector::iterator it;
for (it=myvector.begin(); it!=myvector.end(); ++it)
cout << " " << *it;

The "reusable" iterator you speak of is the tuple myvector.begin() and
myvector.end(). The use of the iterator is composed by its creation
through the method ::iterator, the incrementing, the comparison and
the dereferencing. That's not how things break out in Scala.

In Scala, a reusable iterator is called Iterable. All of Scala's
collections *are* Iterable, meaning you can pass the class itself to a
method. So, where C++ would do this:

sort (myvector.begin(), myvector.end());

Scala does this:

sort(myvector)

The *use* part of an iterator in Scala is composed of a call to the
"iterator" method, plus the methods next and hasNext. On the other
hand, if there's no need to reuse the iterator, one can get the
Iterator itself, which makes it possible to pass objects that are
simpler (or could not implement) a full Iterable.

On Wed, Dec 7, 2011 at 6:30 AM, Seyed H. HAERI (Hossein)
wrote:

>> Of course, you need to realize that they exhaust the iterator since you can't reset it. If you need to make more than one pass, just call toArray, toMap, etc.
>
> This is one of the places where C++ iterators categorically outshine
> their Scala counterparts. From a user's point of view the
> single-traversal restriction causes a lot of difficulty.

But in C++, iterators were invented for an entirely different reason.
In C++, there is no common collection type. Many people wish there
was, but instead, iterators unify collections and arrays. So, you call
sort(begin, end) instead of coll.sort(), just so that you can also
call sort(a, a + SIZE). It's a bit of a hack, really.

In Scala, you use Iterable when you would use iterators in C++.
Iterator is for those few situations where Iterable would be wasteful.
In C++, you'd use an input iterator in these situations.

Except, those are a pain to use because you have to come up with some
bogus end. Scala iterators greatly outshine their C++ counterparts.
They have a hasNext method :-)

Cheers,

Cay

Sorry, can't resist the temptation to link this presentation in this thread.

Hi Josh,

Perhaps, I should first bow against the brevity in Scala. That I
cannot stop praising. As a seasoned C++ man, I have always hated the
syntactic noise in C++...

> (1) They have to know when they are finished. (implement a .end() on the collection)

No, this is not precise. C++ iterators are not for containers only.
(C++ Streams, for examples, don't come with and end() member function
and they do provide their iterators.) Nor do you always iterator until
you hit end(). For cases when you iterate until earlier on in the
container, you compare against the end-point.

> (2) They have to be able to repeatedly obtain a single value.

I'm not sure what this means.

> (3) The *user* determine when to iterate and when he is done.

Neither about this one. But, it seems to be the same story with
iter.next and iter.hasNext in Scala. Furthermore, in C++11, where you
traverse an entire container, you can avoid the syntactic mess using
the modern for/for_each notations.

> We now have a collection of lines in a file.  When I iterate over the collection is will *open* the file first, allow me to perform some operations and *close* the file when I'm done.
>
> I can combine this with views:
>
> val lines = new FileLineTraversable(new java.io.File("tmp.txt"))
> val withoutComments = lines.view filterNot (_ startsWith "#")
>
> Now the value 'withoutComments" reverse to a collection that will open a file, parse for lines not starting with the # character, and give me the remaining lines.  I have not yet opened a file or performed any calculations.
>
> I can then do:
>
> withoutComments take 10 force // Explicitly reads the first 10 non comment lines and returns a new collection.   The data has been read, and remains in memory now.

Here is your same cookie in C++:

template
list n_lines_where(ifstream& in, Predicate p, size_t n = 0)
{
string line;
list lines;
for(size_t i = 0; (n? i < n: true) && getline(in, line); ++i)
lines.push_back(line);
lines.erase(remove_if(lines.begin(), lines.end(), p), lines.end());
return lines;
}

int main()
{
ifstream in("test.txt");
const size_t n = 10;
n_lines_where(in, [const string& s]{return s[0] == " # ";}, n);
return 0;
}

Can you still insist any superiority in the Scala version except a bit
of neatness and readability?

> If you understand Traversable and how to implement foreach, you can accomplish *a lot* of handy code.

It is for similar reasons that I initiated this thread. And, I am
thankful of all you guys who help me over that. :)

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

среда, 7 декабря 2011 г. 19:56:21 UTC+7 пользователь Kevin Wright написал:

Other possibility would be an audio stream getting compressed, with both the input and output being iterators.

Sorry, but how do you express output as Scala iterator?

I'm not sure I understand the question.  An Iterator is just a bunch of values that can be read one at a time, perhaps forever.
Create an Iterator of the desired value type, call it "output", and let your client read from it.


On 7 December 2011 15:39, Pavel Pavlov <pavel.e.pavlov@gmail.com> wrote:

среда, 7 декабря 2011 г. 19:56:21 UTC+7 пользователь Kevin Wright написал:

Other possibility would be an audio stream getting compressed, with both the input and output being iterators.

Sorry, but how do you express output as Scala iterator?

On Wed, Dec 7, 2011 at 10:30 AM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Hi Josh,

Perhaps, I should first bow against the brevity in Scala. That I
cannot stop praising. As a seasoned C++ man, I have always hated the
syntactic noise in C++...

> (1) They have to know when they are finished. (implement a .end() on the collection)

No, this is not precise. C++ iterators are not for containers only.
(C++ Streams, for examples, don't come with and end() member function
and they do provide their iterators.) Nor do you always iterator until
you hit end(). For cases when you iterate until earlier on in the
container, you compare against the end-point.

Right, but I need a known end-point or I can potential fail.   Note: I'm not comparing iterators to iteraotrs here.  Scala is built on *Traversable*.  

> (2) They have to be able to repeatedly obtain a single value.

I'm not sure what this means.

the * opreator.   *iter 

> (3) The *user* determine when to iterate and when he is done.

Neither about this one. But, it seems to be the same story with
iter.next and iter.hasNext in Scala. Furthermore, in C++11, where you
traverse an entire container, you can avoid the syntactic mess using
the modern for/for_each notations.

Right, but the issue is the *collection* doesn't know when the iterator is done.  Cleanup code gets all messy.  You have to use some kind of "smart" iterator that informs the collection when it's destoryed...  

> We now have a collection of lines in a file.  When I iterate over the collection is will *open* the file first, allow me to perform some operations and *close* the file when I'm done.
>
> I can combine this with views:
>
> val lines = new FileLineTraversable(new java.io.File("tmp.txt"))
> val withoutComments = lines.view filterNot (_ startsWith "#")
>
> Now the value 'withoutComments" reverse to a collection that will open a file, parse for lines not starting with the # character, and give me the remaining lines.  I have not yet opened a file or performed any calculations.
>
> I can then do:
>
> withoutComments take 10 force // Explicitly reads the first 10 non comment lines and returns a new collection.   The data has been read, and remains in memory now.

Here is your same cookie in C++:

template<typename Predicate>
list<string> n_lines_where(ifstream& in, Predicate p, size_t n = 0)
{
 string line;
 list<string> lines;
 for(size_t i = 0; (n? i < n: true) && getline(in, line); ++i)
   lines.push_back(line);
 lines.erase(remove_if(lines.begin(), lines.end(), p), lines.end());
 return lines;
}

int main()
{
 ifstream in("test.txt");
 const size_t n = 10;
 n_lines_where(in, [const string& s]{return s[0] == " # ";}, n);
 return 0;
}

Can you still insist any superiority in the Scala version except a bit
of neatness and readability?

It's not the same code.  First, you're returning the top N lines *and then* checking to see if they have comments.  My code returns the top N lines that do *not* have comments.  Second, I've separated my iteration logic from my filtering logic.  You had to create an explicit n_lines_where method.  You didn't create a *collection* that represented lines in the file.  You didn't have an iterator that not only could be used with STL methods, but also closes things.  You had to use a separate function.
I can simply start using more collection method calls and your code will have to reimplement them in functions like "n_lines_where", whereas my code won't grow any more besides calling the methods.
You see, I've abstracted the *iteration/traversal* from the *declaration* of what the algorithm is.   In C++ you *almost* have this.  Unfortunately, iterators are higher level than Traversables, so the auto-close of resources requires a *lot* more potentially buggy tricks *or* creating new "n_lines_where" functions for every kind of method you may want to perform on files.
I encourage you to write the equivalent code in C++, here's the template main:
int main()
{
  // val lines = new FileLineTraversable(new java.io.File("tmp.txt"))
 <your collection type> lines("test.txt")


 // val withoutComments = lines.view filterNot (_ startsWith "#")   // note: This does not mutate the original collection.  This new collection should not affect the original "lines" collection. <your lazy view of a collection type> without_comments;  remove_copy_if(lines.begin(), lines.end(), without_comments.begin(), [const string& s]{return s[0] == " # ";})  // withoutComments take 10 force // Notice: I have to explicitly instantiate the collection *and* iterate over the collection here...  // Also notice iterators support a + method, allowing arbitrary advancement (Traversable does not need to). const size_t n = 10; vector<string> result; copy(without_comments.begin(), without_comments.begin()+n, result.begin())
 return 0;
}

If you can implement those in a nice concise way (like using Traversable) then perhaps you're winning.   However, I'd argue that this really *does* show how inflexible C++ is.   If you want nice code, you have to greatly uglify your implementation with RRID, you have to explicitly copy things (using iterators even...) or mutate in place (which hurts the point of *lazy* views and the efficiency that could be had here...).
Basically, if you tried to mimic the power of Scala's Traversable + TraversableView classes, you'd wind up with ugly, unmaintainable, slow code.  Even changing your code to mimic the actual semantics of the Scala code I've  shown will make it uglier.  Having tried to replicate Scala's collections in C++ STL, I can guarantee you that statements like "C++ iterators are by far better than Scala's iterators" means very little in day-to-day development.   Your goal is to beat out Traversable and TraversableView.   Scala's iterator is up to the task, as most uses stem from "Iterable" which extends from "Traversable".   
- Josh
P.S. - No offence has been taking in your strong statements, and I can somewhat understand your sentiment.  You need to dig a bit further into Scala before you'll see how truly painful C++'s STL (and Java's collection library) has been.   
- Josh

 

> If you understand Traversable and how to implement foreach, you can accomplish *a lot* of handy code.

It is for similar reasons that I initiated this thread. And, I am
thankful of all you guys who help me over that. :)

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

In C++, you can write to iterators.  In Scala, the default Iterator interface is imutable.
C++ ->  while(!done) { *(out++) = *(in++)  }
Scala ->  ??  (Note:  I don't think that comparison is necessary).

On Wed, Dec 7, 2011 at 11:09 AM, Kevin Wright <kev.lee.wright@gmail.com> wrote:

I'm not sure I understand the question.  An Iterator is just a bunch of values that can be read one at a time, perhaps forever.
Create an Iterator of the desired value type, call it "output", and let your client read from it.


On 7 December 2011 15:39, Pavel Pavlov <pavel.e.pavlov@gmail.com> wrote:

среда, 7 декабря 2011 г. 19:56:21 UTC+7 пользователь Kevin Wright написал:

Other possibility would be an audio stream getting compressed, with both the input and output being iterators.

Sorry, but how do you express output as Scala iterator?

On Wed, Dec 7, 2011 at 5:09 PM, Kevin Wright <kev.lee.wright@gmail.com> wrote:

I'm not sure I understand the question.  An Iterator is just a bunch of values that can be read one at a time, perhaps forever.
Create an Iterator of the desired value type, call it "output", and let your client read from it.

I think what Kevin really means here is that "next"/"hasNext" might block until next content can be determined.
 

On 7 December 2011 15:39, Pavel Pavlov <pavel.e.pavlov@gmail.com> wrote:

среда, 7 декабря 2011 г. 19:56:21 UTC+7 пользователь Kevin Wright написал:

Other possibility would be an audio stream getting compressed, with both the input and output being iterators.

Sorry, but how do you express output as Scala iterator?

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

I mean that usually you don't read the output, you do want to write to it.

среда, 7 декабря 2011 г. 23:09:17 UTC+7 пользователь Kevin Wright написал:

I'm not sure I understand the question.  An Iterator is just a bunch of values that can be read one at a time, perhaps forever.
Create an Iterator of the desired value type, call it "output", and let your client read from it.


On 7 December 2011 15:39, Pavel Pavlov <pavel.e...@gmail.com> wrote:

среда, 7 декабря 2011 г. 19:56:21 UTC+7 пользователь Kevin Wright написал:

Other possibility would be an audio stream getting compressed, with both the input and output being iterators.

Sorry, but how do you express output as Scala iterator?

perhaps like this:

trait Producer extends Iterator[ Double ]
trait Consumer extends Iterator[ Unit ]

class SinOsc( freq: Double, sr: Double ) extends Producer {
private val omega = math.Pi * 2 * freq / sr
private var phase = 0
def hasNext = true // till eternity
def next(): Double = {
val out = math.sin( phase * omega )
phase += 1
out
}
}

class Mult( a: Producer, b: Producer ) extends Producer {
def hasNext() = a.hasNext && b.hasNext
def next: Double = a.next() * b.next()
}

object hardware { def write( v: Double ) { println( v )}} // well....

class Output( in: Producer ) extends Consumer {
def hasNext = in.hasNext
def next() {
hardware.write( in.next() )
}
}

val x = new Mult( new SinOsc( 441, 8000 ), new SinOsc( 2, 8000 ))
val out = new Output( x )
for( i <- 0 to 100 ) out.next()

however, any real audio system wouldn't use iterators, but probably process samples in chunks which is much more efficient.

the channel compression could be done with some buffering and several input samples collapsing into a single output sample.

best, -sciss-

On 7 Dec 2011, at 16:09, Kevin Wright wrote:

> I'm not sure I understand the question. An Iterator is just a bunch of values that can be read one at a time, perhaps forever.
>
> Create an Iterator of the desired value type, call it "output", and let your client read from it.
>
>
> On 7 December 2011 15:39, Pavel Pavlov wrote:
>
>
> среда, 7 декабря 2011 г. 19:56:21 UTC+7 пользователь Kevin Wright написал:
> Other possibility would be an audio stream getting compressed, with both the input and output being iterators.
>
> Sorry, but how do you express output as Scala iterator?
>
>
>
>

Whilst true in strictly-evaluated imperative designs, you'll often find that declarative/functional approaches are pull-based rather than push-based.
Most problems can be thought about in either way.  For example, on the unix command line:
  cat someFile.txt | grep wantedstring

Clearly there is a pipe, with cat outputing and grep inputing.  Which you can describe as grep pulling the output from cat, or as cat pushing output into grep.  Both descriptions are conceptually valid at a high level, and represent an effective way in which the pipe *might* be implemented.
Something is an output because it's consumed by another service elsewhere, it doesn't necessarily have to be "written to".

On 7 December 2011 16:20, Pavel Pavlov <pavel.e.pavlov@gmail.com> wrote:

I mean that usually you don't read the output, you do want to write to it.

среда, 7 декабря 2011 г. 23:09:17 UTC+7 пользователь Kevin Wright написал:

I'm not sure I understand the question.  An Iterator is just a bunch of values that can be read one at a time, perhaps forever.
Create an Iterator of the desired value type, call it "output", and let your client read from it.


On 7 December 2011 15:39, Pavel Pavlov <pavel.e...@gmail.com> wrote:

среда, 7 декабря 2011 г. 19:56:21 UTC+7 пользователь Kevin Wright написал:

Other possibility would be an audio stream getting compressed, with both the input and output being iterators.

Sorry, but how do you express output as Scala iterator?

Hi Hossein,

First of all, it's absolutely unproductive to compare directly Iterator trait of Scala with iterator (family of) concept(s) of STL.
They are completely different despite the fact that they share the same name.

Well, STL has a bunch of concepts under the name "iterator" and they have different mappings to the traits of the Scala collection library.

In addition to well known concepts hierarchy you've referred to (input, output, forward, bidirectional, random-access iterators), there is also a division into constant(immutable) and non-constant(mutable) iterators in STL.
Also, as STL iterators often occur in pairs (begin, end), there is also implicit concept of ranges.

So the STL's language of iterators/ranges/containers/algorithms cannot be mapped directly to the Scala's language of collections/views/iterators.

However, it can be done to some extent on a case-by-case basis:

 - STL input iterator/range corresponds to Scala Iterator.

 - STL output iterator has no correspondence in Scala.
   You can reformulate your code in more functional/lazy/on-demand way (as Kevin Wright just wrotes), use Sciss' trick with Iterator[Unit] (which roughly corresponds to STL output iterator without *i operation and with another input iterator bounded into it), or something else.
   Building STL container from values (like filling vector with back_insert_iterator) translates to use of Scala Builder trait.
   However, none of these provides full genericity and power of STL output iterator.

 - STL constant forward iterator/range roughly corresponds to Scala Iterable/Seq.
   Seq always have a defined order of elements, while Iterable does not.

 - There is no correspondence in Scala for bidirectional iterators.

 - STL constant random-access iterator/range roughly corresponds to Scala IndexedSeq.

 - STL container's subrange formed by pair of its iterators corresponds to Scala collection's/iterator's subsequence  formed by view, slice, tail, take, drop, etc. methods.

 - There is no correspondence for STL mutable iterators at all.
   I don't know if it has some ideological FP reasons or it can be implemented in the future (I have long going to write & ask about it).

However, all STL iterators are "external iterators" (now I've overloaded the word "iterator" thrice), while Scala also has "internal(implicit) iterator" - Traversable trait, which allows to easily, safely and effectively express such tasks as tree/graph traversals, iteration + resource management etc.

So, I am strongly disagree that "Scala iterators greatly outshine their C++ counterparts".

As for me, both Scala collection library and STL have excellent (but different) designs, and no one completely outrivals the other.

However, Scala collections have more potential that STL because of its functional orientation:
- Core operations are immutable: it provides a direct path to parrallel/distributed collections.
- It's a way easier to extend Scala collections to the full power of STL then the other way around.
  Just imagine extending STL to full support of Scala-like map/filter/flatMap/partition operations.

Regards,
Pavel.

On Wed, Dec 7, 2011 at 13:30, Seyed H. HAERI (Hossein)
wrote:
>> I can then do:
>>
>> withoutComments take 10 force // Explicitly reads the first 10 non comment lines and returns a new collection.   The data has been read, and remains in memory now.
>
> Here is your same cookie in C++:

No, this is widely different.

>
> template
> list n_lines_where(ifstream& in, Predicate p, size_t n = 0)
> {
>  string line;
>  list lines;
>  for(size_t i = 0; (n? i < n: true) && getline(in, line); ++i)
>    lines.push_back(line);
>  lines.erase(remove_if(lines.begin(), lines.end(), p), lines.end());
>  return lines;
> }

Wrong. You have to design a class that will process all lines of a
file, opening the file first, closing the file when finished, and
never keeping the whole file in memory. This class should not be
hardwired to handle different uses, such as you made with Predicate
and size_t -- that doesn't scale, it is difficult to compose, and puts
the responsibility on the wrong place. It should take a file and
return an iterator, since the goal here is to compare the flexibility
of Traversable's foreach to C++'s iterator.

Once you have that class, you derive an object that will show only the
non-comment lines, without keeping all the lines in memory.

Finally, from that derived object you'll extract 10 lines into a
collection of your choice.

All of the above is possible with the "foreach" abstraction.

>
> int main()
> {
>  ifstream in("test.txt");
>  const size_t n = 10;
>  n_lines_where(in, [const string& s]{return s[0] == " # ";}, n);
>  return 0;
> }
>
> Can you still insist any superiority in the Scala version except a bit
> of neatness and readability?

It is not neatness and readability. Do try to implement that functionality.

>
>> If you understand Traversable and how to implement foreach, you can accomplish *a lot* of handy code.
>
> It is for similar reasons that I initiated this thread. And, I am
> thankful of all you guys who help me over that. :)
>
> Cheers,
> --Hossein
>
> --------------------------------------------------------------------------------------------------------------
>
> Seyed H. HAERI (Hossein)
>
> Research Assistant
> Institute for Software Systems (STS)
> Technical University of Hamburg (TUHH)
> Hamburg, Germany
>
> ACCU - Professionalism in programming - http://www.accu.org/
> --------------------------------------------------------------------------------------------------------------

On Wed, Dec 07, 2011 at 04:30:06PM +0100, Seyed H. HAERI (Hossein) wrote:
> Can you still insist any superiority in the Scala version except a bit
> of neatness and readability?

Just to help explain the point, I'll give you an implementation (which
I consider sufficiently composable) in a language that is not Scala:

# example in python
from itertools import *
path = "/home/erik/.bashrc"

# using a def for readability
def notComment(s): return not s.startswith('#')
lines = list(islice(ifilter(notComment, open(path)), 10))

# or using a lambda expression
lines = list(islice(ifilter(lambda s: s.startswith('#'), open(path)), 10))

Like the Scala version, the functions islice and ifilter don't have any
knowledge of files, comments, strings, etc. Like the Scala version,
this example doesn't read more lines than it needs to, or load the
whole file into memory. Like the Scala version there is automatic
garbage collection and resource management going on so that the
intermediate operations don't have to worry about when the file
descriptor should be closed, or similar concerns.

Hopefully that helps show what they're talking about, and hopefully I
will not get flamed too hard for admitting to knowing and writing
Python sometimes. :P

Iteratees are superior again. Try this in C++ :)

On Dec 8, 2011 5:45 AM, "Daniel Sobral" <dcsobral@gmail.com> wrote:

On Wed, Dec 7, 2011 at 13:30, Seyed H. HAERI (Hossein)
<hossein.haeri@gmail.com> wrote:
>> I can then do:
>>
>> withoutComments take 10 force // Explicitly reads the first 10 non comment lines and returns a new collection.   The data has been read, and remains in memory now.
>
> Here is your same cookie in C++:

No, this is widely different.

>
> template<typename Predicate>
> list<string> n_lines_where(ifstream& in, Predicate p, size_t n = 0)
> {
>  string line;
>  list<string> lines;
>  for(size_t i = 0; (n? i < n: true) && getline(in, line); ++i)
>    lines.push_back(line);
>  lines.erase(remove_if(lines.begin(), lines.end(), p), lines.end());
>  return lines;
> }

Wrong. You have to design a class that will process all lines of a
file, opening the file first, closing the file when finished, and
never keeping the whole file in memory. This class should not be
hardwired to handle different uses, such as you made with Predicate
and size_t -- that doesn't scale, it is difficult to compose, and puts
the responsibility on the wrong place. It should take a file and
return an iterator, since the goal here is to compare the flexibility
of Traversable's foreach to C++'s iterator.

Once you have that class, you derive an object that will show only the
non-comment lines, without keeping all the lines in memory.

Finally, from that derived object you'll extract 10 lines into a
collection of your choice.

All of the above is possible with the "foreach" abstraction.

>
> int main()
> {
>  ifstream in("test.txt");
>  const size_t n = 10;
>  n_lines_where(in, [const string& s]{return s[0] == " # ";}, n);
>  return 0;
> }
>
> Can you still insist any superiority in the Scala version except a bit
> of neatness and readability?

It is not neatness and readability. Do try to implement that functionality.

>
>> If you understand Traversable and how to implement foreach, you can accomplish *a lot* of handy code.
>
> It is for similar reasons that I initiated this thread. And, I am
> thankful of all you guys who help me over that. :)
>
> Cheers,
> --Hossein
>
> --------------------------------------------------------------------------------------------------------------
>
> Seyed H. HAERI (Hossein)
>
> Research Assistant
> Institute for Software Systems (STS)
> Technical University of Hamburg (TUHH)
> Hamburg, Germany
>
> ACCU - Professionalism in programming - http://www.accu.org/
> --------------------------------------------------------------------------------------------------------------



--
Daniel C. Sobral

I travel to the future all the time.

Hi Daniel,

(My apologies that I am pinning back in this late. I was indeed busy
in the mean time.)

> Yes, and that requires you to produce an iterator for every algorithm you want to apply to a collection. Why go to such trouble?

In C++, we deal with real-world data. It is therefore not uncommon at
all, for example, to have a distributed vector of size 10K each
element of which having several GB of memory maps. In such a case, you
decidedly want to deliberately avoid dealing with the entire container
at once. When you're frequently in similar situations, you will come
to love the beautiful and lightweight craft of iterator work in C++.
It scarcely happens ever that you deal with a container as a whole.

Alas, C++ Concepts didn't make their way to the C++11. Had they been
added, STL range algorithms could have been overloaded for containers
too, and this wouldn't have been an issue in such scarce situations
either.

> Why not have all these algorithms implemented in the collection itself?

Because that gives you much more code reuse. Implementing lightweight
iterators for a container is much less hassle than re-implementing all
the algorithms for it -- and, it's definitely less error-prone.

> Notice how the "map" method is actually implemented at the Traversable level?

Yes, other people have also pointed this out. I get the impression
that I need to give this further research. I have only just started
reading Chapter 25 which magnifies this impression. I'll come back to
the list after finishing the chapter -- I promise.

> There's a LOT of code reuse in Scala.

I have no reason to doubt that. In fact, my motivation for initiating
these threads is to gain some intuition over the details of similar
matters. So far, my impression is that Scala could have had even more
room for code reuse, had it designed things similar to STL. I might
end up finding out that I'm wrong though...

> The "reusable" iterator you speak of is the tuple myvector.begin() and myvector.end(). The use of the iterator is composed by its creation through the method ::iterator,

(This is not a member function -- which we call method in Scala. This
is a nested typedef -- similar to the way we use the type keyword in
classes in Scala.)

> the incrementing, the comparison and the dereferencing. That's not how things break out in Scala.

I know. But, then you get much less flexibility. You apparently don't
deal in Scala with very large data and therefore are all in favour of
whole-container algorithms. With the current machinery of Scala, would
you need to perform sub-container algorithms, you need to resort to
views, which -- although lazy and clean -- are still parts of the
container itself. Moving views around is absolutely less efficient
than the lightweight iterator approach in C++. Views get ultimately
forced at some point and passing them around afterwards is copying all
the members themselves. This contrasts the C++ approach of copying
lightweight iterators all the time.

So, in comparison, C++ in fact breaks the abstraction in the right
place where to get more flexibility (through range computation rather
than whole-container ones), as well as superior efficiency (by passing
around lightweight iterators rather than container parts, namely,
views).

> In Scala, a reusable iterator is called Iterable.

OK, I'll come back to this after reading Chapter 25.

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Hi Cay,

> Except, those are a pain to use because you have to come up with some bogus end.

Like I said in an earlier post today, that end thing is almost always
exactly what you want; in C++ where you deal with dead large data, you
almost never want to perform calculations over an entire container at
once. Generic algorithms based on iterator ranges becomes extremely
handy in such a situation.

> Scala iterators greatly outshine their C++ counterparts.

Not with real-world data where you need range algorithms rather than
whole-container ones.

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

On Thu, Dec 8, 2011 at 09:41, Seyed H. HAERI (Hossein)
wrote:
> Hi Daniel,
>
> (My apologies that I am pinning back in this late. I was indeed busy
> in the mean time.)
>
>> Yes, and that requires you to produce an iterator for every algorithm you want to apply to a collection. Why go to such trouble?
>
> In C++, we deal with real-world data. It is therefore not uncommon at
> all, for example, to have a distributed vector of size 10K each
> element of which having several GB of memory maps. In such a case, you
> decidedly want to deliberately avoid dealing with the entire container
> at once. When you're frequently in similar situations, you will come
> to love the beautiful and lightweight craft of iterator work in C++.
> It scarcely happens ever that you deal with a container as a whole.

You are equating "container" with "having everything together at the
same time". As Josh has shown, Scala collections handle exactly the
problem you describe and still provide all the functionality that is
relegated to iterators in C++.

The problem you describe is a *C++ deficiency* that is not shared by
Scala. C++ solution is a hack that is not necessary in Scala.

>> Why not have all these algorithms implemented in the collection itself?
>
> Because that gives you much more code reuse. Implementing lightweight
> iterators for a container is much less hassle than re-implementing all
> the algorithms for it -- and, it's definitely less error-prone.

You obviously did not look a the links I sent you. C++ does *NOT*
provide more code reuse (or, to be more precise, the current C++
library doesn't). In fact, Scala has more code reuse *and* make all
these methods available on the collection themselves. And,
furthermore, you even have a shared interface between iterators and
collections, and you can have collections that iterators cannot
implement at all.

>> the incrementing, the comparison and the dereferencing. That's not how things break out in Scala.
>
> I know. But, then you get much less flexibility. You apparently don't
> deal in Scala with very large data and therefore are all in favour of
> whole-container algorithms. With the current machinery of Scala, would
> you need to perform sub-container algorithms, you need to resort to
> views, which -- although lazy and clean -- are still parts of the
> container itself. Moving views around is absolutely less efficient
> than the lightweight iterator approach in C++. Views get ultimately
> forced at some point and passing them around afterwards is copying all
> the members themselves. This contrasts the C++ approach of copying
> lightweight iterators all the time.

Nothing in this paragraph is correct. I mean it: you have to negate
every sentence to make them true.

Honestly, everything you said above why things have to be the way C++
does them is not true, because Scala accomplish everything you
mentioned with none of the limitations.

And, to be absolutely clear about this point, I'm not saying that this
is an intrinsic C++ limitation. This is a deficiency in how C++
collections are implemented, and, in particular, with how C++
iterators work.

On Thu, Dec 8, 2011 at 09:41, Seyed H. HAERI (Hossein)
wrote:

>> In Scala, a reusable iterator is called Iterable.
>
> OK, I'll come back to this after reading Chapter 25.

Scala 2.8's collection are described in these two pages:

Overview: http://docs.scala-lang.org/overviews/collections/introduction.html
Design: http://docs.scala-lang.org/overviews/core/architecture-of-scala-collecti...

Hi Josh,

(I'll soon be proceeding with Chapter 25 of PinS and the links Daniel
kindly provided. That will hopefully give me a much better view over
the Scala machinery. Please bare with me...)

> Right, but the issue is the *collection* doesn't know when the iterator is done.

That's none of the container's business.

> Cleanup code gets all messy.

Cleanup? Of what? C++ iterators are very simple wrappers around raw
pointers. They don't own what they point to, and would therefore not
need to cleanup anything.

> You have to use some kind of "smart" iterator that informs the collection when it's destoryed...

If you insist your container to know about that. But, why might you
ever want to do so? (Are you sure you're not forgetting that C++ is
not a garbage-collected language?)

> I encourage you to write the equivalent code in C++, here's the template main:

OK, you pushed me outside STL, I 'fess up. :p Here, I use
Boost.IOStream and some line_iterator. Implementing the line_iterator
is trivial:

http://wiki.hsr.ch/Prog3/LoeW14_10

You can alternatively use boost::filter_iterator:

http://www.boost.org/doc/libs/1_48_0/libs/iterator/doc/filter_iterator.html

Here is my attempt without that:

boost::iostreams::filtering_istream in("test.txt");
in.push([const string& s]{return s[0] == " # ";});
list lines;
line_iterator line_iter(in);
for(size_t i = 0; line_iter && (i <= n); ++i, ++line_iter)
lines.push_back(*line_iter);

> P.S. - No offence has been taking in your strong statements, and I can somewhat understand your sentiment.  You need to dig a bit further into Scala

I'm glad to see that people are not taking me wrong and are so nice to
me. Thanks! :)

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

Hi Pavel,

This was a very nice comparison. It was definitely very productive for
me in that it gives a me basis for further investigation. I'll perhaps
come back to it after reading Chapter 25 and the two links Daniel
sent.

TTFN,
--Hossein

On 7 December 2011 19:18, Pavel Pavlov wrote:
> Hi Hossein,
>
> First of all, it's absolutely unproductive to compare directly Iterator
> trait of Scala with iterator (family of) concept(s) of STL.
> They are completely different despite the fact that they share the same
> name.
>
> Well, STL has a bunch of concepts under the name "iterator" and they have
> different mappings to the traits of the Scala collection library.
>
> In addition to well known concepts hierarchy you've referred to (input,
> output, forward, bidirectional, random-access iterators), there is also a
> division into constant(immutable) and non-constant(mutable) iterators in
> STL.
> Also, as STL iterators often occur in pairs (begin, end), there is also
> implicit concept of ranges.
>
> So the STL's language of iterators/ranges/containers/algorithms cannot be
> mapped directly to the Scala's language of collections/views/iterators.
>
> However, it can be done to some extent on a case-by-case basis:
>
>  - STL input iterator/range corresponds to Scala Iterator.
>
>  - STL output iterator has no correspondence in Scala.
>    You can reformulate your code in more functional/lazy/on-demand way (as
> Kevin Wright just wrotes), use Sciss' trick with Iterator[Unit] (which
> roughly corresponds to STL output iterator without *i operation and with
> another input iterator bounded into it), or something else.
>    Building STL container from values (like filling vector with
> back_insert_iterator) translates to use of Scala Builder trait.
>    However, none of these provides full genericity and power of STL output
> iterator.
>
>  - STL constant forward iterator/range roughly corresponds to Scala
> Iterable/Seq.
>    Seq always have a defined order of elements, while Iterable does not.
>
>  - There is no correspondence in Scala for bidirectional iterators.
>
>  - STL constant random-access iterator/range roughly corresponds to Scala
> IndexedSeq.
>
>  - STL container's subrange formed by pair of its iterators corresponds to
> Scala collection's/iterator's subsequence  formed by view, slice, tail,
> take, drop, etc. methods.
>
>  - There is no correspondence for STL mutable iterators at all.
>    I don't know if it has some ideological FP reasons or it can be
> implemented in the future (I have long going to write & ask about it).
>
> However, all STL iterators are "external iterators" (now I've overloaded the
> word "iterator" thrice), while Scala also has "internal(implicit) iterator"
> - Traversable trait, which allows to easily, safely and effectively express
> such tasks as tree/graph traversals, iteration + resource management etc.
>
> So, I am strongly disagree that "Scala iterators greatly outshine their C++
> counterparts".
>
> As for me, both Scala collection library and STL have excellent (but
> different) designs, and no one completely outrivals the other.
>
> However, Scala collections have more potential that STL because of its
> functional orientation:
> - Core operations are immutable: it provides a direct path to
> parrallel/distributed collections.
> - It's a way easier to extend Scala collections to the full power of STL
> then the other way around.
>   Just imagine extending STL to full support of Scala-like
> map/filter/flatMap/partition operations.
>
> Regards,
> Pavel.
>

On Thu, Dec 8, 2011 at 10:16 AM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Hi Josh,

(I'll soon be proceeding with Chapter 25 of PinS and the links Daniel
kindly provided. That will hopefully give me a much better view over
the Scala machinery. Please bare with me...)

> Right, but the issue is the *collection* doesn't know when the iterator is done.

That's none of the container's business.

But it is, if the container wishes to offer reasonable "clean up the reosurce" guarantees.  You can argue whether or not this is useful, but I find it highly valuable in my own code.  Resource leakages are *very* easy to create, especially in the presence of exceptions.  

> Cleanup code gets all messy.

Cleanup? Of what? C++ iterators are very simple wrappers around raw
pointers. They don't own what they point to, and would therefore not
need to cleanup anything.

What you mean is they *can't* clean things up.  Using iterators for traversal means you have no *option* to cleanup.  *or* you have to track the lifetime of every iterator to know when the collection can be cleaned up.   I'm  huge boost::shared_ptr fan in my own code.
Otherwise, you have to track the lifetime of the object you're dealing with *and* ensure that none of the iterators or used after the collection has been cleaned up.   That's a huge PITA IMHO, and completely unecessary in 99% of use cases.
 

> You have to use some kind of "smart" iterator that informs the collection when it's destoryed...

If you insist your container to know about that. But, why might you
ever want to do so? (Are you sure you're not forgetting that C++ is
not a garbage-collected language?)

No, I'm not forgetting that.   However, if you don't use these kinds of principles in your collection, then you're not fitting the sample I showed, which removes the need for *resource* cleanup (not memory cleanup).   I.e. the file handle is opened and closed within the collection and user code need not worry about it.   It will "do the right thing(TM)".  You can accomplish this in C++ with a lot of effort.  

> I encourage you to write the equivalent code in C++, here's the template main:

OK, you pushed me outside STL, I 'fess up. :p Here, I use
Boost.IOStream and some line_iterator. Implementing the line_iterator
is trivial:

http://wiki.hsr.ch/Prog3/LoeW14_10

You can alternatively use boost::filter_iterator:

http://www.boost.org/doc/libs/1_48_0/libs/iterator/doc/filter_iterator.html

Here is my attempt without that:

boost::iostreams::filtering_istream in("test.txt");
in.push([const string& s]{return s[0] == " # ";});
list<string> lines;
line_iterator<string> line_iter(in);
for(size_t i = 0; line_iter && (i <= n); ++i, ++line_iter)
 lines.push_back(*line_iter);

This is getting much closer to what I was showing.  The remaining difference is that your original stream is "contaminated" by the filtering code.  You could not re-use that input stream somewhere else.   Also, the collection I have opens the file upon every traversal.   It's a re-usable "method of reading a file", rather than just simply an iterator.
Also, you have to explicitly close the input if you want the resource to be closed.  If you do so, line_iter is now "broken" in future code.
Coming from C++ you should well be aware the issues of ownership, and management of resources (memory, file handles, etc.).  If I can design a library such that it makes it easy for me to deal with resources and not leak them, I'd argue that's a "Good Thing(TM)".   In C++, I've seen lots of RRID mechanisms used to scope resources and all sorts of other hackery like "shared_ptr<T>" that's now in the standard library.  If you want to protect yourself from messing up resource handling, you'd have to add all this effort into iterators.
Scala's mechanisms does not need any of that.  You could argue that GC solves all this, but actually GC makes it harder to clean up *other* resources, like file handles.   You cannot rely on Finalize running, or when, so resource handling code is often ugly looking.   Java even added in special syntax in Java 7 to try to make resource handling easier.   So no, GC has nothing to do with my statement.  It's about resources (Transactions, File Handles, Threads, etc.).   If I have a collection I need to obtain within a resource and that resource needs to be opened/closed then there's no better mechanism I've seen than Scala's Traversable***.
This is what I mean when I say "C++ iterators are severely limited and Scala's abstraction is more powerful".   It's much *simpler* in Scala to support *all* of the use cases in C++ as efficiently (O notation wise) and to support even more use cases that would be very hard to get right in C++.
- Josh
*** Note:  You could argue that the Traversable I suggest is zipped monad stack, and you may be right.
P.S.  I love boost.  It's by far my favorite C++ library.  Working @ Google where boost wasn't allowed was maddening for a lot of code I was writing.

Dear Josh,

I would like to first apologise for not being prompt in response. On
the other hand, this thread is getting out of Scala Iterators. So,
maybe I should fork it into other threads with more specific topics.
I'll just reply quickly and move to the new threads ASAP.

>> That's none of the container's business.
>
>
> But it is, if the container wishes to offer reasonable "clean up the reosurce" guarantees.

No that's plain wrong. All STL/Boost containers provide very
reasonable resource guarantees. Yet, no C++ iterator has such a stitch
to the respective container. I have myself implemented a few new
containers with good resource awareness with no need for that. Adding
parallelism -- which makes things severely difficult in C++ -- doesn't
demand such a stitch either. See "C++ Concurrency in Action" for a lot
of relevant discussion.

>> > Cleanup code gets all messy.
>>
>> Cleanup? Of what? C++ iterators are very simple wrappers around raw
>> pointers. They don't own what they point to, and would therefore not
>> need to cleanup anything.
>>
> What you mean is they *can't* clean things up.

No, that's wrong too. I really meant it: They don't OWN what they
point to. It is therefore conceptually wrong for them to care about
deleting their pointees.

> However, if you don't use these kinds of principles in your collection, then you're not fitting the sample I showed, which removes the need for *resource* cleanup (not memory cleanup).
> I.e. the file handle is opened and closed within the collection and user code need not worry about it.

Again, that's wrong. C++ istream objects are automatic. The respective
destructor will automatically close the file -- unless you manually
instruct it otherwise.

> You could not re-use that input stream somewhere else.   Also, the collection I have opens the file upon every traversal.   It's a re-usable "method of reading a file", rather than just
> simply an iterator.

Likewise, you can put my entire code in a loop and all the
constructions/destructions work automatically.

> In C++, I've seen lots of RRID mechanisms used to scope resources and all sorts of other hackery like "shared_ptr" that's now in the standard library.

Of course, in C++, not everything comes for free. You have neat access
to deepest corners of real memory -- something out of Scala's access.
Yet, you also have full control over making things completely
automatic. This unique combination needs somehow to be paid off...

> This is what I mean when I say "C++ iterators are severely limited and Scala's abstraction is more powerful".

We'll get to that in my new thread. Bare with me for now...

> P.S.  I love boost.  It's by far my favorite C++ library.  Working @ Google where boost wasn't allowed was maddening for a lot of code I was writing.

Just a quick note: Boost can extend STL neatly for the latter's
beautiful craft and very thoughtful design. All that is possible
because of the unique way C++ combines paradigms. Forgive me if that's
too cryptic; I'm in a hurry. :p

Cheers,
--Hossein

--------------------------------------------------------------------------------------------------------------

Seyed H. HAERI (Hossein)

Research Assistant
Institute for Software Systems (STS)
Technical University of Hamburg (TUHH)
Hamburg, Germany

ACCU - Professionalism in programming - http://www.accu.org/
--------------------------------------------------------------------------------------------------------------

On Mon, Dec 12, 2011 at 5:54 PM, Seyed H. HAERI (Hossein) <hossein.haeri@gmail.com> wrote:

Dear Josh,

I would like to first apologise for not being prompt in response. On
the other hand, this thread is getting out of Scala Iterators. So,
maybe I should fork it into other threads with more specific topics.
I'll just reply quickly and move to the new threads ASAP.

>> That's none of the container's business.
>
>
> But it is, if the container wishes to offer reasonable "clean up the reosurce" guarantees.

No that's plain wrong. All STL/Boost containers provide very
reasonable resource guarantees. Yet, no C++ iterator has such a stitch
to the respective container. I have myself implemented a few new
containers with good resource awareness with no need for that. Adding
parallelism -- which makes things severely difficult in C++ -- doesn't
demand such a stitch either. See "C++ Concurrency in Action" for a lot
of relevant discussion.

What I'm saying is that in Scala, you have a completely *different* mental model on resource ownership and cleanup.  Cleaning up a resource on container destruction != safe iterators IMHO.  

>> > Cleanup code gets all messy.
>>
>> Cleanup? Of what? C++ iterators are very simple wrappers around raw
>> pointers. They don't own what they point to, and would therefore not
>> need to cleanup anything.
>>
> What you mean is they *can't* clean things up.

No, that's wrong too. I really meant it: They don't OWN what they
point to. It is therefore conceptually wrong for them to care about
deleting their pointees.

This is exactly my point.  They do not own what they point to.  Even if they *should* own it.  It requires you to manage an owner *and* the iterators on that owner in your code.  This is a whole class of problem i can safely ignore in Scala with no ill effects.  However, if I *need* to separate the iterators from the owners, I can do so.  I'm not forced into managing more complexity because the base abstraction discourages it.  

> However, if you don't use these kinds of principles in your collection, then you're not fitting the sample I showed, which removes the need for *resource* cleanup (not memory cleanup).
> I.e. the file handle is opened and closed within the collection and user code need not worry about it.

Again, that's wrong. C++ istream objects are automatic. The respective
destructor will automatically close the file -- unless you manually
instruct it otherwise.

That's correct.  What happens if an istream object is destroyed but I still have an iterator to it?   This has been an all-to-easy occurence in my experience in C++, especially when dealing with threads.  The cognitive load of ensuring that resources hang around and who owns them is a constant frustration in C++ when all I really want to do is implement Feature X in an efficient manner and ship the code.   C++'s abstractions tend to be leaky, making me worry about everything all the time.   It did help me become a paranoid programmer, but it wears on you after a while.  

> You could not re-use that input stream somewhere else.   Also, the collection I have opens the file upon every traversal.   It's a re-usable "method of reading a file", rather than just
> simply an iterator.

Likewise, you can put my entire code in a loop and all the
constructions/destructions work automatically.

In this simple example yes.  Extrapolate both examples, and you may see issues.  Mine can be passed to another thread and allow the loop to continue.  The resource will be cleaned appropriately when needed, even it is opened in the current thread and not closed until a later thread "owns" it.  

> In C++, I've seen lots of RRID mechanisms used to scope resources and all sorts of other hackery like "shared_ptr<T>" that's now in the standard library.

Of course, in C++, not everything comes for free. You have neat access
to deepest corners of real memory -- something out of Scala's access.
Yet, you also have full control over making things completely
automatic. This unique combination needs somehow to be paid off...

In my experience the "full control" over making things automatic is somewhat of a mistruth.  Yes, I can make things a lot simpler with some tricks in C++, but by no means can I reduce my cares to the point that Scala can reduce them.  Once you get into this mindset, it is *very* freeing.   Again, I recommend coding in this style for a bit before knocking it.   External Iterators are 'ok', but internal iterators are far nicer for performance code and better abstractions.
- Josh