List.scan · ideas · Zulip Chat Archive

Stream: ideas

Topic: List.scan

Anthony Bullard (Dec 07 2024 at 15:27):

I'd love to have this in the builtins

List.scan : List a, (a, a -> b) -> List b

Obviously you could have scanLeft and scanRight, and maybe even List.window with a variable sized scan

Anthony Bullard (Dec 07 2024 at 15:28):

You can _kind of_ do this today with List.walk, but requires a lot of ugly handling for the first iteration

Anthony Bullard (Dec 07 2024 at 15:37):

Here's a pure Roc implementation. I feel like we could do better in Zig:

Anthony Bullard (Dec 07 2024 at 15:37):

scan : List a, (a, a -> b) -> List b
scan = \list, scanner ->
    when list is
        [] | [_] -> []
        [first, .. as rest] ->
            walker = \(l, prev), item -> (List.append l (scanner prev item), item)
            empty = List.withCapacity ((List.len rest) - 1)

            List.walk rest (empty, first) walker
            |> .0

Richard Feldman (Dec 07 2024 at 16:07):

seems worth exploring! Some things to think about:

what do other languages which have this operation call it?
do other languages use the name scan to mean something else? e.g. Rust's scan is totally different
what would the API look like to have a window of 3, 4, 5, etc? is that desirable?
is this a common enough need that a stdlib function is worth it? something I often think about is: what happens if someone else comes across code that uses it? If their immediate reaction is "scan? What does that do?" and then they have to go look it up and understand it, then a convenience function can actually become an inconvenience depending on whether it comes up enough for people to know what it does offhand

Eli Dowling (Dec 07 2024 at 16:58):

"slidingWindow" is what I know it as.
I think that name is very self explanatory, if I see that and see the signature it would be immediately obvious "it's a window into the list that slides along"

Eli Dowling (Dec 07 2024 at 17:00):

But also I agree that it's common enough that I want it.

Paul Stanley (Dec 07 2024 at 18:40):

I agree that it's a useful function. When I need to do it I tend to do this (rather than walking) because I just find it easier to understand ... I _think_ I got it from APL where this is the standard idiom for this.

But I've no idea how the efficiency compares. I suppose that's an argument for having a builtin that is as efficient as it can be.

scan : List a, (a, a -> b) -> List b
scan = \list, scanner ->
    if List.len list > 1 then
            first = List.dropLast list 1
            last = List.dropFirst list 1
            List.map2 first last scanner
    else []

(The other very common function that I miss from the builtin List is zip ... not because it's hard to write, but because one actually needs it rarely enough that it's useful to have sitting ready.)

Brendan Hansknecht (Dec 07 2024 at 18:46):

Oh, scan is sliding window size two

Brendan Hansknecht (Dec 07 2024 at 18:46):

I was really confused looking at these implementations....

Anthony Bullard (Dec 07 2024 at 18:47):

I think I got used to scan in Scala

Brendan Hansknecht (Dec 07 2024 at 18:47):

I thought scan was a fold that keeps all intermediate results

Anthony Bullard (Dec 07 2024 at 18:47):

I’m 6 years separated

Anthony Bullard (Dec 07 2024 at 18:47):

So maybe my memory is faulty

Brendan Hansknecht (Dec 07 2024 at 18:48):

That map2 solution should be essentially as efficient as a bespoke zig builtin

Brendan Hansknecht (Dec 07 2024 at 18:48):

Probably how it should get implemented if we add it to the std lib

Brendan Hansknecht (Dec 07 2024 at 18:49):

The initial impl should be ok as well, but I would need to double check it

Kilian Vounckx (Dec 07 2024 at 19:23):

In most languages I know of, scan is a fold with keeping intermediate results. Like an accumulated sum for example.

Sliding windows of size 2 I've seen called mapAdjacent.

I think both would make a good addition to std

Luke Boswell (Dec 07 2024 at 19:36):

We've discussed sliding windows before somewhere.

Luke Boswell (Dec 07 2024 at 19:37):

https://roc.zulipchat.com/#narrow/channel/231634-beginners/topic/List.2Ewalk.20with.20.22sliding.20window.22/near/451137188

Richard Feldman (Dec 07 2024 at 21:03):

Kilian Vounckx said:

Sliding windows of size 2 I've seen called mapAdjacent.

I like that name!

Richard Feldman (Dec 07 2024 at 21:04):

is there significant interest in more than a window bigger than 2?

Sam Mohr (Dec 07 2024 at 22:00):

I've used const generics to make larger arrays before

Sam Mohr (Dec 07 2024 at 22:00):

It's probably worth keeping the door open

Sam Mohr (Dec 07 2024 at 22:02):

It sounds like you're implying that mapAdjacent would be dangerous

Brendan Hansknecht (Dec 07 2024 at 22:11):

Richard Feldman said:

is there significant interest in more than a window bigger than 2?

I have seen it in array languages a lot. Ends up being useful for physics calculations and some other simulation things. Also for some sound transforms. That said, most of those use large enough windows that they would use seamless slices instead of a tuple. Nice thing about a seamless slice version is that it is completely generic to any size. Sad part is that it adds in extra list len checks.

Brendan Hansknecht (Dec 07 2024 at 22:13):

This is where allowing for a seamless slice with a compile time known size would be a magical optimization.

Anthony Bullard (Dec 07 2024 at 22:14):

Screenshot 2024-12-07 at 4.13.58 PM.png

I guess I melded Iterator.scan and Iterator.sliding in my brain in Scala

Brendan Hansknecht (Dec 07 2024 at 22:14):

Hmm, that might be a general optimization we may want to consider in roc. Behind the sense tracking of list length if it can be guaranteed at compile time. Use it just for removing length checks.

Anthony Bullard (Dec 07 2024 at 22:16):

@Brendan Hansknecht Don't you only need to check the length once? To ensure the list is of the minimum length?

Brendan Hansknecht (Dec 07 2024 at 22:17):

I'm thinking this API:

List.slidingWindow: List a, U64, (List a -> b) -> List b

Anthony Bullard (Dec 07 2024 at 22:17):

That should be no more than field access for a RocList right? It's a pointer to the data, the length, and the capacity, so just pull the length one time and that's it

Anthony Bullard (Dec 07 2024 at 22:17):

Yeah, That's what I would expect

Brendan Hansknecht (Dec 07 2024 at 22:17):

So the passed in lambda will also be checking list size when it access the data in the window

Anthony Bullard (Dec 07 2024 at 22:18):

Oh yeah, destructuring lists requires a length check :man_facepalming:

Brendan Hansknecht (Dec 07 2024 at 22:19):

Llvm may manage to optimize it away, but definitely in the category of maybe maybe not, but it can 100% of the time be removed if the size passed to slidingWindow is constant.

Anthony Bullard (Dec 07 2024 at 22:19):

But using a tuple either limits the options you have, or seriously bloats our list of builtins. scan, scan3, scan4, scan5, etc

Brendan Hansknecht (Dec 07 2024 at 22:19):

Exactly

Brendan Hansknecht (Dec 07 2024 at 22:20):

And given we have seamless slices, lists feel like the right option here.

Anthony Bullard (Dec 07 2024 at 22:20):

Yeah, this type of function is pretty much always expensive

Anthony Bullard (Dec 07 2024 at 22:20):

Without a fixed size array

Anthony Bullard (Dec 07 2024 at 22:22):

I'd like to learn more about Seamless Slices because I know all about Slices and have never before entering this chat seen "Seamless" but before it :-)

Anthony Bullard (Dec 07 2024 at 22:22):

I figure it's just a pointer to a start and a length?

Anthony Bullard (Dec 07 2024 at 22:23):

And maybe some way for it to affect the RC for the underlying array?

Anthony Bullard (Dec 07 2024 at 22:26):

Or does it also include the number of elements after the end so that you can just increment its start to move it

Brendan Hansknecht (Dec 07 2024 at 22:29):

Yeah, pointer, length, and pointer to deal with refcounting of the original list. Seamless cause there is no slice type in roc, just list. But under the hood, you can get a slice to part of a list.

Brendan Hansknecht (Dec 07 2024 at 22:35):

If we guaranteed that the size checks where elided, I would 100% go with the API I mentioned above. Without that, tuple feels safest.

My current gut feeling is that we should go for the list API and generally llvm should do ok with it. Long term, we could look at optimizing the size checks out manually.

Luke Boswell (Dec 07 2024 at 23:25):

List.slidingWindow or List.mapAdjacent?

I think we should make a tracking issue so we dont forget about it again. :grinning:

I can do it later, just out and on my phone rn.

Brendan Hansknecht (Dec 07 2024 at 23:26):

I would push for slidingWindow it makes more sense for the generic case. mapAdjacent only feels right for the 2 element case and not the N case. Though either name is ultimately fine.

Brendan Hansknecht (Dec 07 2024 at 23:27):

Also, as a zig builtin, this could take advantage of just incrementing the slices pointer instead of generating a new slice. So probably worth doing that.

Eli Dowling (Dec 08 2024 at 01:48):

Brendan Hansknecht said:

Hmm, that might be a general optimization we may want to consider in roc. Behind the sense tracking of list length if it can be guaranteed at compile time. Use it just for removing length checks.

I think this would be great. Particularly given roc makes getting from an index a little onerous what with returning a result.
I had a problem that would have probably benefited from a ring buffer recently and just decided the performance would probably not be much better given all the length checks and results :sweat_smile:

Sky Rose (Dec 08 2024 at 23:27):

I've used sliding windows with size 3, which is like a map, but you also get the previous and next elements. This is useful for adding prev/next links, or for calculating the time since the previous event, or finding local maxima, or...

But a difference between 3 and 2 is with 3, you're thinking about the central element, and the other two are just context. So the type is more like mapWithPrevNext : List a, (a, [Prev a, First], [Next a, Last] -> b) -> List b where you still want to map over the first and last elements.

Luke Boswell (Dec 11 2024 at 05:29):

Had a use for this in today's AoC ... unfortunately found something that hangs the compiler rolling my own.

https://github.com/roc-lang/roc/issues/7333

Joshua Warner (Dec 18 2024 at 23:36):

It would be really cool if some type system magic existed to make scan/window functions generic across tuple arities (where all elements are the same type, but there’s a statically known size)

Brendan Hansknecht (Dec 18 2024 at 23:37):

And we have now invented arrays

Brendan Hansknecht (Dec 18 2024 at 23:37):

But yeah, I agree

Joshua Warner (Dec 18 2024 at 23:40):

I would have called it a vector, as in vector register (and it’d be great for simd!). But that’s a significant tangent

Alex Nuttall (Dec 19 2024 at 00:00):

Typescript can do it. Of course there's the massive problem that the underlying language doesn't even have tuples

Brendan Hansknecht (Dec 19 2024 at 00:02):

Also it wouldn't really be simd related cause it could contain complex types while simd is only for numeric types.

Brendan Hansknecht (Dec 19 2024 at 00:02):

Like you could have a window of (Str, List U8, Dec)s

Last updated: Jun 16 2026 at 16:19 UTC