Kilian Vounckx (Jun 01 2023 at 09:35): Kilian Vounckx (Jun 01 2023 at 09:35):I think there is nothing in the std like Haskell's unfoldr. As its name suggests, it can do the reverse of foldr (List.walk in roc). foldr takes a list and a binary operation and produces a single value. unfoldr takes a single value and a unary operation (which takes a single value and returns a pair of values), and produces a list from this.
I suggest we have a similar function. Its signature would be state, (state -> [Continue { state : state, elem : elem }, Break]) -> List elem. (The names of the record fields and tags could be changed of course.)
The first argument is the initial state used to build the list. The second is a function which, based on the state, produces a value and a new state. The element is put in the list, the state is used in the next iteration. The function can also return Break. This signals that all values are produced and the list can be returned.
Many other functions can be built on top of this one, such as List.range, or List.takeWhile (if it gets implemented).
A simple implementation would be:
unfoldr : state, (state -> [Continue { state : state, elem : elem }, Break]) -> List elem
unfoldr = \init, func ->
when func init is
Break -> []
Continue { state, elem } -> List.prepend (unfoldr state func) elem
The reason I would want this in the std can be seen in this implementation. I feel like many users would implement this like the above, because it is the simplest. Maybe they would use a specific function they need instead of a generic one, but the algorithm would be the same. This algorithm is really slow however since it uses List.prepend. This is needed to keep the order. A better implementation would keep an accumulator and have tail recursion:
unfoldr : state, (state -> [Continue { state : state, elem : elem }, Break]) -> List elem
unfoldr = \init, func ->
helper : state, List elem -> List elem
helper = \s, acc ->
when func s is
Break -> acc
Continue { state: s2, elem } -> helper s2 (List.append acc elem)
helper init func []
This implementation is less trivial and I feel like especially beginners would not create this. This is the main reason I would want this in std. (Besides it just being a useful function)
For the hardest part, the name, I like List.build, but any other suggestions are welcome! naming is hard :big_smile:
Kilian Vounckx (Jun 01 2023 at 09:43):Maybe there could also be a way to give a size estimate, so the list can be pre-allocated. Maybe have the first argument be a record with optional fields like { initialState : state, sizeEstimate ? Nat }, where sizeEstimate defaults to 0?
Richard Feldman (Jun 01 2023 at 10:37):hm, what are some scenarios where this function would be used?
Kilian Vounckx (Jun 01 2023 at 10:51):Whenever you want to build a list without knowing the size beforehand. A contrived example would be fibonacci:
fibsLessThan : Nat -> List Nat
fibsLessThan = \max ->
List.build { a: 0, b: 1 } \state ->
if state.a > max then
Break
else
Continue { state: { a: state.b, b: state.a + state.b }, elem: state.a }
If you know the number of elements beforehand, you can often use a combination of List.range and List.map though
Richard Feldman (Jun 01 2023 at 11:55):hm, what's a non-contrived example of where it would be used? :big_smile:
Richard Feldman (Jun 01 2023 at 11:55):by default I'm wary of adding functions to the stdlib without a known use case, and the more complicated the type, the more wary I get - and this one is very far toward the "complicated type" end of the spectrum! :sweat_smile:
Kilian Vounckx (Jun 01 2023 at 15:57):Richard Feldman said:
hm, what's a non-contrived example of where it would be used? :big_smile:
In my regex parser, I used a helper function to keep parsing a char, for between brackets. As long as there is no right bracket, it should keep parsing. Now it is implemented without a function like unfoldr, but it would be cleaner (imho) with it.
Kilian Vounckx (Jun 01 2023 at 15:57):Looking further at that file, all the helper functions are of the same form, building an accumulator. In the case I mentioned, the accumulator just happens to be a list
Kilian Vounckx (Jun 01 2023 at 15:58):So maybe this is an indication it shouldn't be in the standard library
Kilian Vounckx (Jun 01 2023 at 15:58):Richard Feldman said:
by default I'm wary of adding functions to the stdlib without a known use case, and the more complicated the type, the more wary I get - and this one is very far toward the "complicated type" end of the spectrum! :sweat_smile:
I totally get it! It is a complicated type and should not be put in std without careful consideration
Kilian Vounckx (Jun 01 2023 at 15:59):I do feel List.walkUntil has a similarly complicated type.
Then again, I would use walkUntil more than unfoldr I think
Richard Feldman (Jun 01 2023 at 17:31):yeah walkUntil is essentially a for loop that can early return/break - I can certainly think of plenty of times I've reached for those in imperative programs! :big_smile:
and without walkUntil, there's no way to express that (or rather, to get those performance characteristics) in Roc
Richard Feldman (Jun 01 2023 at 17:31):that's the real motivation there - performance, not convenience
Richard Feldman (Jun 01 2023 at 17:31):because without that, you always have to traverse the entire collection and there's no way to bail out, because Roc doesn't have the equivalent of return or break to exit a loop early
Kilian Vounckx (Jun 01 2023 at 17:52):In this analogy, unfoldr would be a while loop which appends to a list in the body. But maybe it is best to always do an explicit recursion (with or without accumulator and tail recursion), than have a complicated function in std
Last updated: Jun 16 2026 at 16:19 UTC