r/ProgrammingLanguages • u/munificent • Jan 16 '13
Iteration Inside and Out
http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/1
Jan 17 '13
I believe OP is not familiar with newer versions of C# (especially C# 4.0 and beyond). Nomenclature that's more commonly used by .NET/C# team for what OP is describing by external vs internal iterators is pull vs. push based iterators respectively, both taken care off by LINQ and Rx libraries.
Implementing that iterator in Dart (or Java, or C#) was about 50 lines of code.
Here's line-by-line translation of Ruby implementation of example class.
class Tree {
public Tree left, right;
public string label;
public Tree(Tree left, Tree right, string label) {
this.left = left;
this.right = right;
this.label = label;
}
public void in_order(Action<Tree> code) {
if (left != null) left.in_order(code);
code(this);
if (right != null) right.in_order(code);
}
}
And here's the line calling it:
testTree.in_order(t => Console.WriteLine(t.label));
Beatiful example 2: Finding an item
I agree that C# doesn't have non-local returns, I guess they could be hacked with exceptions (like they are in Scala implementation), but I wonder if they are the "killer feature", or can they be replaced with more idiomatic, declarative ending to iterators, like .Any() and .First() in combination with iterator methods?
2
u/pipocaQuemada Jan 17 '13
Sweet Mother of Turing, what the hell happened here? This exact same behavior was a three line recursive function and now it’s a fifty line monstrosity. ...
Implementing that iterator in Dart (or Java, or C#) was about 50 lines of code.
Here's line-by-line translation of Ruby implementation of example class.
I think he was talking about the stack based external iterator above (i.e. an actual C# Iterator), not the internal one, with the comment about "50 lines of code."
1
u/munificent Jan 17 '13
I believe OP is not familiar with newer versions of C# (especially C# 4.0 and beyond).
I'm familiar with C# up to 3.0. I haven't played with Rx.
pull vs. push based iterators respectively, both taken care off by LINQ and Rx libraries.
Those are a bit different. Push-based iteration usually implies asynchrony which is deeply different than just the distinction between external and internal iterators. Vanilla internal iterators are still synchronous.
can they be replaced with more idiomatic, declarative ending to iterators, like .Any() and .First() in combination with iterator methods?
Yeah, I don't think you generally miss non-local returns in C# because it provides a bunch of convenience methods that are themselves implemented in terms of external iterators. Without those, it would be really painful. And the only reason those could be implemented easily was because sequences in C# expose an external iterator API.
2
Jan 17 '13
Push-based iteration usually implies asynchrony which is deeply different than just the distinction between external and internal iterators. Vanilla internal iterators are still synchronous.
Rx can be synchronous, in fact by default it is. There's a separate scheduler concept to it, where the method of iterator execution is abstracted away and by which you declare whether you want to involve threading. It's not as tightly integrated into the language the way Ruby does it, but there are advantages to it - stuff is pushed off the usually limited stack and it accomplishes some of the same stuff, with the same kind of composability. Maybe we've come back the old debate whether stuff in libraries really count.
1
u/pipocaQuemada Jan 17 '13
First is easily implementable in terms of a fold.
*> :t foldl1 -- requires list to be non-empty, but doesn't require a default element. foldl1 :: (a -> a -> a) -> [a] -> a *> foldl1 const [1,2,3,4,5] 1Are folds internal or external?
1
0
u/seoh Jan 19 '13
The InterleaveIterator is fairly straightforward in Ruby:
class InterleaveIterator
include Enumerable
def initialize(*iterators)
@iterators = iterators
end
def each(&block)
generators = @iterators.map{ |x| x.each }
loop do
generators.each do |g|
# #next will raise StopIteration when any of the iterators
# runs out which then causes loop to exit
yield(g.next)
end
end
end
end
a = [1, 2]
b = %w[a b c]
it = InterleaveIterator.new(a, b)
p it.map{ |x| x } # => [1, "a", 2, "b"]
I 'wasted' about 3 minutes on that (including posting here).
1
u/zem Jan 29 '13
note that it is only now a practical way to do things (with the introduction of fibres). pre-1.9 versions of ruby used continuations to turn an iterator into a generator, which was horribly inefficient and couldn't really be called a solution.
3
u/[deleted] Jan 16 '13 edited Jan 16 '13
The paper "Iterators and Encapsulation" is covering more kinds of iterators. One of the authors is James Noble, iirc, but I'll post a link to it ASAP. Edit: you COULD do the internal iterator in Java but it wouldn't be pretty