Dilson Higa (Jun 15 2024 at 18:19): Dilson Higa (Jun 15 2024 at 18:19):After a brief exchange with @Anton on the beginners channel I decided to bring a proposal for adding a function to the List module.
The function, which I am calling reduce, would work the same as List.walk but using the first element of the list as the initial state.
Proposed type signature:
reduce : List elem, (elem, elem -> elem) -> Result elem [ListWasEmpty]
Of course this function is trivial for implementation on "user space", but I believe it is worth for the convenience.
Drawbacks:
Ian McLerran (Jun 15 2024 at 18:41):Personally I like the idea. I can see where the argument could be made that the functionality already exists through walk, but I think reduce adds a concise and descriptive way to handle a common use of List.walk. List.walk is kind of a utility knife that could be doing all kinds of things. If you see reduce, you know exactly what it’s doing on a surface level.
Brendan Hansknecht (Jun 15 2024 at 18:59):Just a warning, this will have sharp edges with some numeric things. For example, if you have a List U8, it will accumulate in U8 and likely overflow or underflow
Brendan Hansknecht (Jun 15 2024 at 19:01):I do agree that walk can often feel quite heavy handed....I wonder if there is an in-between where we can still accumulate in a different type
Kasper Møller Andersen (Jun 15 2024 at 19:19):I'm not particularly for or against this, but:
1) naming-wise, I feel reduce is more in line with names like filter and fold, which Roc has avoided. Maybe a name like mergeElements would be better?
2) I don't think I've ever personally had a use for a function like this, so I'm curious what use cases it actually serves.
Ian McLerran (Jun 15 2024 at 19:21):That’s a good point Brendan… So maybe instead reduce : List a, (b, a -> b) -> Result b [ListWasEmpty]
Ian McLerran (Jun 15 2024 at 19:29):Hmm.. yeah, I’be noticed Roc has opted in some cases for more verbose/descriptive names. Personally I like the shorter names. I also think reduce is still pretty descriptive of what it does, unlike fold, which could be a little more confusing for a functional programming novice.
As to what it could be used for, there are many examples, but a few simple examples are: summing the elements in a list, finding the min or max element, etc. Come to think of it, we already have explicit functions for this in the List module for Num types, but it would be useful for extending that to opaque types, or for other uses where you want to extract a single value from a list.
Dilson Higa (Jun 15 2024 at 19:34):I agree with the name mergeElements if it ever gets accept.
Regarding point 2, minutes after proposing it I am already having second thoughts.
When I wrote this idea I had a concrete case in which I am merging a bunch of sets of intervals where each set had additional properties. Those properties made it impossible to use call List.walk with a neutral element as a starting point. But midway my code I realized I was going to need to hold more information into my State type, meaning I would not use my reduce function anymore.
Dilson Higa (Jun 15 2024 at 19:35):Long story short, I don't have a concrete use case anymore.
Ian McLerran (Jun 16 2024 at 00:21):Ian McLerran said:
That’s a good point Brendan… So maybe instead
reduce : List a, (b, a -> b) -> Result b [ListWasEmpty]
I'm realizing this implementation wouldn't actually work: in order for reduce automatically begin with the first element, that means your accumulator must the same type as the element.
So in order to have an implicit accumulator, your transform function must be (a, a -> a).
Ian McLerran (Jun 16 2024 at 00:42):If you want a reduce function, you could also define your own in a utils module:
listReduce : List a, (a, a -> a) -> Result a [ListWasEmpty]
listReduce = \list, f ->
when list is
[x, .. as xs] -> List.walk xs x f |> Ok
[] -> Err ListWasEmpty
For anyone who wants a reduce function like this, I created a package roc-reduce which includes functions like described here. I included:
Reduce.listLeftReduce.listRightReduce.dictReduce.dictKeysReduce.dictValuesReduce.set Brendan Hansknecht (Jun 16 2024 at 16:16):Since you are just walking the result, I would avoid calling Dict.keys or Dict.values. that will materialize the intermediate list of keys or values.
Brendan Hansknecht (Jun 16 2024 at 16:17):Instead, I would use Dict.toList then match [(k, _), ... as rest]. That will avoid the intermediate allocation
Ian McLerran (Jun 16 2024 at 16:30):Okay, let me try to understand that… when you say “materialize”, are you saying that an intermediate allocation is being done for a list of keys in the case of Dict.values, and a list of values in the case of Dict.keys?
And that .toList with an empty pattern for keys or values avoids this? That is the opposite behavior from what I would expect… did I understand that correctly?
Ian McLerran (Jun 16 2024 at 16:48):Then i'll also have to accommodate for the fact that rest is now of type (k, v) instead of type v.
Brendan Hansknecht (Jun 16 2024 at 16:50):Fundamentally, toList is just exposing an internal list that already exists. No allocation necessary. You can walk that, extracting keys, values, or both as you go. That gets you a reduce with no allocations.
Dicy.keys and Dict.values both take the list you would get from Dict.toList and apply List.map to it. That will create a new allocation of only keys or only values
Ian McLerran (Jun 16 2024 at 16:52):Ah yeah, of course. That makes sense... btw what is time complexity of lookup for a roc dict?
Brendan Hansknecht (Jun 16 2024 at 16:56):O(1) (barring any refcounting bugs that lead to n refcounts)
Ian McLerran (Jun 16 2024 at 17:01):Alright, Reduce.dictKeys and dictValues now use toList instead of the less efficient .keys and .values functions.
Ian McLerran (Jun 16 2024 at 17:01):Thanks for the pointer there!
Last updated: Jun 16 2026 at 16:19 UTC