Stream: ideas

Topic: List.mapAdjacent

Kilian Vounckx (Dec 09 2023 at 09:21):

Hi all, Long time since I've been here because of studies, but now I'm using roc for AoC!

I found myself wanting a function like List.mapAdjacent a lot. Not just in AoC, but other situations as well. I just happened to want to use it in today's puzzle.

For those who don't know what mapAdjacent is. It is found in a few utility libraries in haskell (so it can be found on hoogle), but I know it from c++ as adjacent_transform (because in c++, every map function must be named transform). It takes a List a and a binary function a, a -> b and takes any two adjacent pairs in the list and applies the function to them.
For example, List.mapAdjacent [1, 2, 3, 4, 5] Num.add would return [3, 5, 7, 9]. The resulting list's length is always one smaller than the input list's length. Only if the input was empty, the result is still empty.

This can be implemented in pure roc as

List.mapAdjacent = \list, f ->
    List.map2 list (List.dropFirst list 1) f

Every time I needed it in roc, I implemented something like this with the function filled in, but this does not work well in pipelines because you need the list twice. This is why I want it in the standard library.

What do you guys think?

Luke Boswell (Dec 09 2023 at 09:35):

link to haskell docs

LoipesMas (Dec 09 2023 at 09:36):

I was thinking about having a List.windows functions, similar to the one in Rust. Then you could use it to achieve the same result

Kilian Vounckx (Dec 09 2023 at 09:39):

True!
The only difference is you then need to pipe it to a List.map with a function which takes a list as an input. Most of the times however, you know the length of that list beforehand (2 in mapAdjacent), so this makes it annoying to have to unpack it

Kilian Vounckx (Dec 09 2023 at 09:39):

I'm not against adding both List.mapAdjacent and List.windows though

Kilian Vounckx (Dec 09 2023 at 13:34):

I have a working fork with it implemented. I'll wait for some more answers here. If it is agreed to add it, I will make a pull request. If not, it was a nice exercise for me to get back into contributing :smiley:

Richard Feldman (Dec 09 2023 at 14:48):

interesting! I'm curious to know how this is used in practice - does anyone have some code snippets of how they've used this in Roc?

Artur Domurad (Dec 09 2023 at 17:08):

Here is an example:

calculatePercentageDiff : F64, F64 -> F64

mapAdjacent : List a, (a, a -> b) -> List b

# -- Function to calculate the daily percentage change in stock prices
calculateDailyPercentageChange : List F64 -> List F64
calculateDailyPercentageChange = \stockPrices ->
    stockPrices
    |> mapAdjacent calculatePercentageDiff

In F# instead of special map function, there is a List.pairwise function that makes a list of tuples - this way you can use it with map, filter, reduce, etc (more flexible, but probably also a performance hit):

pairwise : List a -> List (a, a)

calculatePercentageDiff : (F64, F64) -> F64

# -- Function to calculate the daily percentage change in stock prices
calculateDailyPercentageChange : List F64 -> List F64
calculateDailyPercentageChange = \stockPrices ->
    stockPrices
    |> pairwise
    |> List.map calculatePercentageDiff

You could also use this to check if a list is sorted:

pairwise : List a -> List (a, a)

# -- Function to check if a list is sorted in ascending order
isSortedAsc : List (Num a) -> Bool
isSortedAsc = \list ->
    list
    |> pairwise
    |> List.all \(a, b) -> a <= b

Isaac Van Doren (Dec 09 2023 at 17:12):

I like the idea of adding pairwise! I prefer that over mapAdjacent because it would be more general. For example, you could map or walk over the list of pairs depending on your needs instead of only being able to map.

Kilian Vounckx (Dec 09 2023 at 17:39):

I don't have a strong opinion on if we use pairWise or mapAdjacent. If you want to filter on pairs you could still do it with mapAdjacent:

list |> mapAdjacent (\x, y -> (x, y)) |> keepIf foo

I tend to do the same when using map2 sometimes

Kilian Vounckx (Dec 09 2023 at 17:40):

I think is is a matter of preference which to pick (or both), but I don't have a strong preference

Kilian Vounckx (Dec 09 2023 at 17:46):

Richard Feldman said:

interesting! I'm curious to know how this is used in practice - does anyone have some code snippets of how they've used this in Roc?

I tend to use it with differences most of the time. If I have a list of numbers (either in a variable, or in a pipeline), and I want to calculate the differences between them.
I think that is the most common use case, as it is called adjacent_difference when used with c++ iterators.

A code snippet from today's AoC (paraphrased as I am using a phone) was something like

numbers =
    line
    |> Str.split " "
    |> List.mapTry Str.toI32
    |> okOrCrash
differences = List.map2 numbers (List.drop1 numbers) \a, b -> b - a

Here it would have been nice to have the mapAdjacent to not have to name the badly named numbers

Richard Feldman (Dec 09 2023 at 18:15):

so one of the tradeoffs I think about with convenience functions like this is: what happens if someone later comes along to read the code and they don't know what the convenience function does, because it's rarely used?

Richard Feldman (Dec 09 2023 at 18:17):

like for example https://package.elm-lang.org/packages/elm-community/list-extra/latest/List-Extra#break

Kilian Vounckx (Dec 09 2023 at 18:18):

Richard Feldman said:

so one of the tradeoffs I think about with convenience functions like this is: what happens if someone later comes along to read the code and they don't know what the convenience function does, because it's rarely used?

Totally understandable

I have had a few situations where I missed it, but to be honest, I have mainly used roc for AoC and similar puzzles, so maybe my experiences are not a proper represenation for the average roc user

Richard Feldman (Dec 09 2023 at 18:18):

yeah I think this is just on the side of the line where I'd rather not have it as a builtin :big_smile:

timotree (Dec 11 2023 at 07:12):

Kilian Vounckx said:

This can be implemented in pure roc as

List.mapAdjacent = \list, f ->
    List.map2 list (List.dropFirst list 1) f

For what it's worth, this simple implementation actually has a performance pitfall as far as I can tell: it fails to be in-place likeList.map when list is uniquely owned and a = b. I can only see how to make an in-place implementation using List.update, which requires that the input and ouput type are the same. Is there a way to make a pure roc implementation which is in-place when a = b but still generic over two type variables? If not, maybe a builtin is warranted?

# In-place, but requires input and output are same type
mapAdjacent : List a, (a, a -> a) -> List a
mapAdjacent = \l, f ->
    mapAdjacentHelper l f 0
mapAdjacentHelper = \l, f, i ->
    when List.get l (i + 1) is
        Ok y ->
            newL = List.update l i \x -> f x y
            mapAdjacentHelper newL f (i + 1)

        Err OutOfBounds ->
            List.dropLast l 1

timotree (Dec 11 2023 at 07:16):

I think the missing primitive here is an in-place implementation of

mapWithTails : List a, (a, List a -> b) -> List b
mapWithTails = \l, f ->
    List.mapWithIndex l \elem, i -> f elem (List.dropFirst l (i + 1))

timotree (Dec 11 2023 at 07:18):

(For fully general builtin, you would actually want walkMapWithTailsUntil :P)

Brian Carroll (Dec 11 2023 at 10:26):

Is there a way to make a pure roc implementation which is in-place when a = b but still generic over two type variables?

I think that's possible yes. All of the reference counting stuff comes after type specialization. (It has to, because different types have different memory layouts, with pointers to their children in different places.) So the concept of "type variables" doesn't exist at that point in the compiler pipeline. All types are concrete.

timotree (Dec 11 2023 at 17:42):

But could you define it using existing list builtins? I don't think so

Brendan Hansknecht (Dec 11 2023 at 17:47):

Not in a way that avoids reallocation while being fully general.

Brendan Hansknecht (Dec 11 2023 at 17:48):

(deleted)

Brendan Hansknecht (Dec 11 2023 at 17:50):

Cause you need builtin magic to check if the list is unique and the output type is equal in size to the input type if you want it to be fully generic

Brendan Hansknecht (Dec 11 2023 at 17:50):

I guess you could also make it inplace if the output type is smaller.

Last updated: Jun 16 2026 at 16:19 UTC