Yes, it seems easy to implement.

Yes, students should absolutely implement the classic algorithms to learn.

Yes, there are some occasions when you need to home grow one at $work.

BUT, in my opinion, most of the time, professional code should use a battle tested, vuln hardened library or builtin version. These things are VERY HARD to get exactly right. Jon Bently's Programming Pearls famously had a latent bug in its binary search for 20 years before someone caught it.

https://research.google/blog/extra-extra-read-all-about-it-n...

So yeah, it looks easy but don't do it. Stand on some giant's shoulders instead.

Your reply is not relevant to my reply. The original poster is asking for this functionality and appears to believe it is something other than an iterator and requires some sort of special language support. However, it is completely implementable as an iterator, in a reasonably usable manner, with no additional language support. My specific code is written only to show that fact off.

Anyone who copies and pastes it is welcome to both pieces when it breaks. Others have already alluded to possible improvements that could be made, and I already have my own analysis in a grandchild reply as to why I don't think this is a terribly pressing need or necessarily even a good idea.

The reason I provide code is that it gets past the "oh, you say it's just an iterator, but I still don't believe you, since you haven't spelled it out to the n'th degree". When code is provided, belief ceases to be an issue. It is clearly something an iterator can implement, in existing languages, with existing iterator support.

Unless you're going to claim it is somehow impossible to provide this functionality in a tested manner, you're completely changing the topic in an uninteresting direction, since it is always true that functionality generally needs testing and bits of code slammed into an HN conversation just to make a particular point probably shouldn't be copied wholesale into your production code.

Sure but all pre-made, battle-tested tree datastructures you'd use in production in all languages already come with some form of iterator that you can just for-loop over, so the original articles point is still moot.

Sure, but it can be done by a library. There's no reason it needs to be built into the language.

Yeah, tree traversal is really easy and implementing it as an iterator is natural. Maybe don't use a recursive technique if you plan on working with non-toy datasets, Python's default stack limit is pretty small (1000), but this is otherwise a very flexible API.

While easy, I think bisect would be a good addition to every stdlib too.

I did the tree just to match the author's example. I would agree that a bespoke iterator for breadth- and depth-first iteration for any given tree is probably a better way to go. As long as we're in a language like Python, build in something that allows you to examine a branch and decline to descend into it while you're at it.

I don't think this is a large problem in practice because you shouldn't be using dozens of tree types in a given code base, so adding iterators to a tree is no big deal. In general there aren't enough types of iteration available to a given data structure that you need to describe how to iterate on it from the "outside". (Generally when you are doing that, it's too non-trivial to fit into this pattern anyhow; see the Visitor pattern in general.) This strikes me as maybe the sort of default tool you might slap in a library somewhere, but it should be a niche tool. If you're using it all the time you're probably doing something wrong. By default your data structures should be providing iteration packaged with them and it should generally be what you need. And your language should support aborting iteration, in whatever that looks like normally. I'm not sure I know a language that doesn't, it's a fairly basic element of iterator support when you get into implementation.

There are also many cases where a tree iterator will perform significantly better, including CPython. I don't have enough experience with PyPy to know if it could inline the Tree.left and Tree.right calls down to zero penalty at JIT time. Rust and C++ and the other static languages with sophisticated compilers might be able to get that down to fully inlined and zero-cost, but even if they can it's probably better not to push that on to the optimizer as the optimizers will eventually give up if this is composed with enough other stuff. Better to just have an efficient implementation in the first place.

I avoided the stack limit by using itertools.chain: https://github.com/DavidBuchanan314/millipds/blob/15727d474c...

(this is for iterating over nested JSON-like objects, which are just weird trees)

CBOR objects, to be specific ;)

There are a lot of ways you could avoid the recursion, but that's a particularly nice way!

Rust has a bisect [1], which is surprising since the std is kept relatively small.

[1] https://doc.rust-lang.org/std/vec/struct.Vec.html#method.bin...

Well, the whole point of the blog post is to argue for a new kind of syntactic sugar and the author explicitly mentions iterators.

> Well a range based for loop requires that your tree exist in memory AND that you have an iterator defined for your tree. With for_tree you could operate on an entirely imperative tree, without needing to define any iterators or generator functions. Here's an example where I'm checking every single string composed of "a", "b", and "c" of length 8 or less.

    for_tree(string x = ""; x.size() <= 8; x : {x+"a", x+"b", x+"c"}){
     print(x);
    }

You could definitely find every string composed of "a", "b", and "c" of length 8 or less by defining a custom iterator but it would be a verbose and unpleasant way of writing it:

    class StringIterator {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = std::string;
        using difference_type = std::ptrdiff_t;
        using pointer = const std::string*;
        using reference = const std::string&;

        StringIterator(bool begin = false) : is_end_(!begin) { if (begin) s_ = ""; }

        const std::string& operator*() const {
            if (is_end_) throw std::out_of_range("End iterator");
            return s_;
        }

        StringIterator& operator++() {
            if (is_end_) return *this;
            if (s_.size() < 8) return s_.push_back('a'), *this;
            while (!s_.empty() && s_.back() == 'c') s_.pop_back();
            if (s_.empty()) is_end_ = true;
            else s_.back() = s_.back() == 'a' ? 'b' : 'c';
            return *this;
        }

        StringIterator operator++(int) { auto tmp = *this; ++(*this); return tmp; }

        bool operator==(const StringIterator& other) const {
            return is_end_ == other.is_end_ && (is_end_ || s_ == other.s_);
        }

        bool operator!=(const StringIterator& other) const { return !(*this == other); }

    private:
        std::string s_;
        bool is_end_;
    };

    int main() {
        StringIterator begin(true), end;
        int count = 0;
        for (auto it = begin; it != end; ++it) ++count;
        std::cout << (count == 9841 ? "Pass" : "Fail") << std::endl;
        return 0;
    }

    def itWithStop(init, stop, *options):
        if init is not None and not stop(init):
            yield(init)
            for f in options:
                newVal = f(init)
                yield from itWithStop(newVal, stop, *options)

    for s in itWithStop("",
                       lambda x: len(x) > 2,
                       lambda x: x + "a",
                       lambda x: x + "b",
                       lambda x: x + "c"):
        print(s)

yields the combinations of 0 - 2 length strings with a, b, and c.

Python has a number of ways to achieve this depending on exactly how you want to pass the arguments; multiple functions, optional arguments, etc. How nice the final call looks is more about your local language's closures look.

The main point here is that this will happily iterate on things that don't "exist".

    module Tmp where

    iter :: forall a. (a -> Bool) -> [a -> a] -> a -> [a]
    iter p opts x = if p x then x:concatMap (iter p opts) (opts <*> [x]) else []


    ghci> :l tmp.hs
    [1 of 1] Compiling Tmp              ( tmp.hs, interpreted )
    Ok, one module loaded.
    ghci> iter (\x -> length x < 3) [(++ "a"), (++ "b"), (++ "c")] "" 
    ["","a","aa","ab","ac","b","ba","bb","bc",
     "c","ca","cb","cc"]

(Since things are lazy in Haskell, functions that return lists effectively are iterators. There's probably something in the standard library somewhere for (opts <*> [x]) to avoid the wrapping x in an unnecessary list, but my Haskell is rusty.)

The iterator in my example will also happily iterate on things that don't exist. We all agree that it's possible to do in any language. But the main point is that the blog post is talking about syntactic sugar for an easier way to do it.

And yes, Haskell is amazing at this sort of thing.

The syntactic sugar being asked for in this case is awfully thin. I definitely put this in the class of "stop pining for it and just use what's there".

If the poster wants to particularize this to C++ because C++'s syntax can't support it in any reasonable manner, that's fine, but that's a C++ problem, not a "Programming languages..." problem. Which would be perfectly understandable and I'm not really complaining, more clarifying that most of the rest of the world can just rub together three or four existing constructs in a pretty reasonable manner to get this.

Same thing, but the iterator is instead hidden inside the language implementation. `foreach` is already a quite general construct, and iterators are the way to extend them. However, I can see the benefit of designing a library to help implement more intricate iterators.

Ceterum censeo this would be a family of simple macros in LISP.

It seems like it should be possible to factor out most of the iterator boilerplate into a helper class. Then each place where you want to iterate you can construct an instance of that helper class and supply a lambda that specifies how to descend into children. If you're doing the same iteration in several places then you can use a named function instead of a lambda, which means less typing for each `for` loop. Here's a rough sketch: https://godbolt.org/z/x94WY77rv

I kind of agree, but at the same time, for loops are just a fancy control structure that any student should be able to implement with goto.

I mean people do use iterator instead of for loops quite a lot.

IMO the thing that would be really nice is if control flow like `for` was actually the same as using an iterator. This would really help in Rust too where handling errors inside iterator callbacks is a right pain.

I've seen a few languages try this but it seems to not be very popular. I think it can get a bit confusing how control flow keywords like `return` and `break` work if you turn `if` into syntactic sugar for a function call taking a closure etc.

In what way is for different than an iterator?

In PHP you loop through an iterator with the foreach control structure.

In JavaScript you use for of.

In rust it’s for in.

What am I missing?

You're missing that I am an idiot and was mixing up iterators with functional style programming :D

That's why i said "goto". Iterators are already a high level cintrol structure.

Whoops, my edit window closed, but that first comment derives from a previous version that had a different signature for the functions in the "options" list. Ignore it.