Becker A. (Dec 13 2023 at 05:07): Becker A. (Dec 13 2023 at 05:07):I'm trying to wrap my head around roc concepts and best practices, and I don't understand what Roc would have a programmer do in place of the "iterator" concept that Rust or Python have.
I haven't seen any mention of "iterators" in the new roc docs (they look great btw!). I understand that Roc makes available the List type through the standard library, which in terms of functionality does all the things iterators might do. but it seems like this is more similar to Python's list or Rust's Vec, and the downside of these compared to an "iterator" is an increase in memory usage. However, I've also watched that one talk by Our Lord And Savior about how the compiler makes use of "pure-functional"-ness to do things that can't be done in non-pure-functional languages; and since I don't know any better, it seems possible to me that Lists used in specific ways (i.e., each element accessed once and in order from front to back) could just get compiled into "iterators" in the resulting binary. but I haven't seen any evidence or suggestion of this.
so my questions:
List doesn't get magic performance benefits in Roc, does it? (aside from the general "one reference? then no copies, just mutate in-place!" rule that all objects follow) Pearce Keesling (Dec 13 2023 at 05:13):I believe the current design goal is to not have iterators but there's a few other threads going on about potential special cased optimizations for list/range iteration I think
Brendan Hansknecht (Dec 13 2023 at 05:25):I think currently it stands in a weird spot between
1) need
2) simplicity focus of the language
3) future chance to make optimizations of this form automatically.
I would say explicit iterators aren't a goal currently, but if there was a large enough need, maybe they would be added. At the same time I would guess implicit designs or suggestions to build up the iterator manually with a recursive function are much more likely aligned with roc style.
Brendan Hansknecht (Dec 13 2023 at 05:26):Generally iterators are pretty easy to do manually by just grouping functions smartly, but it is not as nice as an automatic chaining when just using a list like type.
Brendan Hansknecht (Dec 13 2023 at 05:27):Do you have any specific examples? Real examples of something you want to do in roc but is either really bad in terms of ergonomics or performance tend to be big motivators for design. (Best with actual roc code to look at not just an idea from another language)
Brendan Hansknecht (Dec 13 2023 at 06:36):More chat in: https://roc.zulipchat.com/#narrow/stream/304641-ideas/topic/Rust.20like.20iterators.20for.20List.20fn.20piping
Brian Carroll (Dec 13 2023 at 07:49):Best practice is to use functions like List.map and List.walk. You can do most things with those, and other similar functions in the standard library.
If you need something more custom, use recursion. Roc optimises tail calls to loops so this is efficient
https://en.m.wikipedia.org/wiki/Tail_call
Oli (Dec 13 2023 at 12:05):I guess something like OCaml's Seq might be possible? I'm not sure how well the compiler would optimise this compared to how well Rust optimises its iterator though. (disclaimer: I'm very new to Roc and haven't finished the tutorial yet)
Pearce Keesling (Dec 13 2023 at 13:14):From what I understand the main advantage of iterators like rust is that I can chain lots of them together and then it's pull based so it only actually computes what is needed for the final result. In roc I'd need to collapse it all into one walk to get that behavior I think.
Pearce Keesling (Dec 13 2023 at 13:16):So something like .map.filter.any won't ever actually make a new allocation and potentially only actually processes one item through the iterators
Becker A. (Dec 13 2023 at 17:36):Brendan Hansknecht said:
Do you have any specific examples? Real examples of something you want to do in roc but is either really bad in terms of ergonomics or performance tend to be big motivators for design. (Best with actual roc code to look at not just an idea from another language)
Good constructive question! tbh I don't have an actual real-world need (I'm using Roc mostly for AoC atm). but anything that deals with sequential data and several cascaded sequence operations (i.e., several .map or .filter operations). so maybe something like these?:
Lists you'd lex the whole string into an array of tokens (O(n) memory), and then search the array.List.map for each of the 10 stages means I'd be making 10 arrays; 9 arrays for each of the intermediate results and 1 array for the output I care about. to me it seems like such a generic, commonplace opportunity for optimization that I'm having a hard time justifying it, if that makes sense :sweat_smile:
Becker A. (Dec 13 2023 at 17:40):Oli said:
I guess something like OCaml's Seq might be possible? I'm not sure how well the compiler would optimise this compared to how well Rust optimises its iterator though. (disclaimer: I'm very new to Roc and haven't finished the tutorial yet)
yeah exactly! I've also heard people talk about "lazy execution" in Haskell, maybe that's what I mean here?
Becker A. (Dec 13 2023 at 17:51):also Brendan, this isn't necessarily a pitch for explicit iterators. this would all still be useful if the roc compiler magically did this sort of thing under-the-hood on Lists when deemed possible
Brendan Hansknecht (Dec 13 2023 at 17:59):Yeah, that all makes senses. Roc has no laziness, so doesn't just get iterators like haskel.
That said, automatic iterators gets really complex. For example, if you look at most high performance compiler lexing and parsing pipelines. They no longer use iterators. They will generate a full list of tokens. Why? Data oriented design. Many hot tight loops over sequential memory is what cpus perfer. At the cost of creating the list, lexing and parsing run much much faster.
Brendan Hansknecht (Dec 13 2023 at 18:01):So in that lexing and parsing case, iterators are actually generally a disadvantage. In fact, as long as you can keep your data dense, it is often faster to have multiple tight loops over data. That said, this is most pronouced when an iterator has some form of conditional logic (that can ruin loop perf). If the iterator is just combining a bunch of straight logic, it can often be much more performant.
Brendan Hansknecht (Dec 13 2023 at 18:01):My point in all of this is that there is a lot of nuance to when you actually want iterators.
Brendan Hansknecht (Dec 13 2023 at 18:03):using List.map for each of the 10 stages means I'd be making 10 arrays; 9 arrays for each of the intermediate results and 1 array for the output I care about.
So just use one map and a pipeline of stage functions?
instead of
data
|> List.map stage1
|> List.map stage2
|> List.map stage3
|> List.map stage4
|> List.map stage5
do:
data
|> List.map runAllStages
runAllStages = \x->
x
|> stage1
|> stage2
|> stage3
|> stage4
|> stage5
The second example is almost identical to what iterators would generate (though it assumes and input and output list, have to be a bit fancier to avoid those)
Richard Feldman (Dec 13 2023 at 18:20):fwiw I'd like to optimize things like consecutive List.maps to remove the intermediate allocation
Richard Feldman (Dec 13 2023 at 18:21):in general this is an optimization called "deforestation" in e.g. Haskell
Becker A. (Dec 13 2023 at 19:33):Yeah the consecutive List.map refactor makes sense as an appropriate fix.
-> given that, I think the examples that would be of more interest would be those that:
List (e.g. something like “generate the first N fibonacci numbers, then map each one”)List.map (e.g., List.keepIf, List.joinMap, etc.) Brendan Hansknecht (Dec 13 2023 at 19:36):Yeah, that has to be done as a recursive function with accumulator. Maybe one day it could use automatic iterators too, but would probably only work with builtin lists and not other wrapping types.
Becker A. (Dec 13 2023 at 19:36):@Brendan Hansknecht re: the parsing example, what about chunk iteration, as a middle-ground between single-item iteration and bulk processing? At a high-level it sounds like a nice “best of both worlds” approach, but idk how well it would work in practice
Becker A. (Dec 13 2023 at 19:38):(Not to make you repeat yourself, you did mention that automatic decisions would be tough. Just mentioning the thought :smile:)
Brendan Hansknecht (Dec 13 2023 at 19:38):Specifically talking about the parsing and lexing context:
Yeah, chunked works for sure. It gives you a mix of the high performance and low memory. I think it is ignored often cause it is more complex and generally low gain (computers have so much memory that allocating the full array tends not to matter).
Brendan Hansknecht (Dec 13 2023 at 19:40):To clarify my comment about automatic iterators:
I personally care a bit too much about low level details. So I am not a fan of automatic conversions of that nature, but if we do end up adding it, we might as well expand support.
So personally I think I would prefer essentially a decorator or some other special function to tell the compiler to enable iterators for a pipeline, but I don't think that is likely to fit roc.
Brendan Hansknecht (Dec 13 2023 at 19:41):Otherwise, it can always be done with a recursive function and accumulator
Pearce Keesling (Dec 14 2023 at 05:53):Will roc ever have intermediate allocations for a series of chained maps? Won't the first one allocate a new list and then the ref count is 1 so the rest will be in place mutations and return that first allocation?
Brendan Hansknecht (Dec 14 2023 at 05:54):Only if the element is the same size (or smaller). Otherwise you need a new allocation to fit the larger elements. Also, not 100% sure we support smaller yet, but definitely can add the optimization if it is missing
Last updated: Jul 06 2025 at 12:14 UTC