Yes, this seems to be basically the right understanding. If you're iterating an array, the state is an index into the array. If you're iterating a linked list, the state can be a node (and you can ignore the iterator object itself). For some situations, the special iteration object just becomes a wrapper that changes how to iterate the thing in question.
On Thu, Jun 12, 2014 at 2:48 PM, Philippe Lavoie <[email protected] > wrote: > Ok so I just an implementation for a doubly linked list in Julia and I > think it answers my question. Basically, you avoid heap allocation during > iteration passing around something's that has already been allocated, like > a node. Therefore, the start function should be called directly on the > "container" or whatever iterates. So, a container typically has to provide > a default iteration method to answer "start". > > > On Thursday, June 12, 2014 2:26:04 PM UTC-4, Philippe Lavoie wrote: >> >> Yes I agree to the heap allocated thing. That is indeed what Java does >> but I think in C++ you usually wrap it in a struct and pass it by value to >> function templates, so no real overhead. >> >> What do I have to do in Julia to avoid heap allocation in such a case? >> Does the "state" value have to be a primitive type, like Int? >> Is the "start" function supposed to be applied to a container type or to >> an iterator. In the former case, does that mean container should provide >> one default iteration way. In the latter case, does returning an iterator >> uses heap allocation? >> >> Thanks, >> Phil >> >> On Thursday, June 12, 2014 1:54:17 PM UTC-4, Stefan Karpinski wrote: >>> >>> I'm saying that using a heap-allocated mutable object to store your >>> iterator state is going to be slow no matter what language you use. Where >>> "slow" means "not fast enough to be how you count from 1 to n" – which is a >>> very high performance requirement. In Java, C++, for loops are fast but >>> require you to explicitly manage state, whereas iterators hide state >>> management inside a mutable object but are relatively slow. In particular, >>> they have quite different interfaces and syntax. We wanted a single >>> protocol that could be fast enough to be how your basic `for k = 1:n` loop >>> works, but general enough to implement all kinds of iterable things. The >>> way to do this is to use external state in a functional way, allowing state >>> to be kept in registers instead of having it live in a mutable, >>> heap-allocated object like C++ and Java do. The for loop syntax hides this >>> explicit state, so that you don't actually have to be aware of it, but the >>> for loop is just sugar for calling start, done and next in the appropriate >>> ways. >>> >>> >>> On Thu, Jun 12, 2014 at 1:37 PM, Philippe Lavoie <[email protected]> >>> wrote: >>> >>>> Hi, >>>> Thanks for you answer. I am still hung up on a couple of details: >>>> Are you saying that, in Julia, in order for an iterator to be >>>> efficient, it has to be an immutable type? >>>> Would it be possible to just use it like this: >>>> iter = getacomplicatediter(myCollection) >>>> (elt, current ) = next(myImmutableIter) >>>> stopCondition = done(iter) >>>> >>>> I guess I don't understand what the additional argument/return value >>>> "state" is for? >>>> >>>> Thanks, >>>> Phil >>>> >>>> >>>> On Thursday, June 12, 2014 12:09:22 PM UTC-4, Stefan Karpinski wrote: >>>> >>>>> Mutable state is lousy for performance. Since the iteration protocol >>>>> is used for things as basic as a for loop count up from 1 to n, it has to >>>>> be very fast. If it used a mutable iterator object, getting that to be >>>>> fast >>>>> enough would be a nightmare. Using explicit external state makes it easy >>>>> to >>>>> translate a for loop into very fast, efficient code, equivalent to what >>>>> you >>>>> would write by hand with a while loop. >>>>> >>>>> >>>>> On Thu, Jun 12, 2014 at 11:59 AM, Philippe Lavoie < >>>>> [email protected]> wrote: >>>>> >>>>>> Hi, >>>>>> So I was seduced by a lot of things Julia had to offer and I found >>>>>> the documentation really fun and helping. >>>>>> >>>>>> However, I do have some questions, one of them would be: "why >>>>>> iterator functions pass state?". >>>>>> In a more traditional language, you would address an iterator as >>>>>> such: iter.next(), iter.done(), iter.popFront(), iter.front(), >>>>>> iter.empty(), etc... >>>>>> >>>>>> I am curious to know why, in Julia, iterator functions pass around >>>>>> state: >>>>>> init = start(iter) >>>>>> (i, current) = next(iter, init) >>>>>> done = (iter, current) >>>>>> >>>>>> First of all, I am not sure why a method called "start" would exist, >>>>>> given the iterator might be provided by another function, like >>>>>> "ascendingValues(myRedBlackTree)", which would return an iterator >>>>>> for values in ascending order for example. >>>>>> Second, given you have an iterator, why pass its state around instead >>>>>> of just modifying it at every functional call, like traditionally (java, >>>>>> c++, etc...). IMHO, the iterator interface should/could borrow from other >>>>>> programming languages and could be something like: >>>>>> done = isDone(iter) >>>>>> next = next(iter) >>>>>> >>>>>> >>>>>> >>>>> >>>
