Stream: beginners

Topic: Iteration tools: combinations, cartesian product, etc.

Aurélien Geron (Jul 30 2024 at 11:25):

What is the recommended way to iterate over all the combinations of n elements in a list, or over the cartesian product of multiple lists? Is there a module I can use for this?

Aurélien Geron (Jul 30 2024 at 11:31):

For example, I'd like all the possible pairs of elements in a list. I wrote this function:

pairs = \list ->
    List.mapWithIndex list \a, indexA ->
        List.mapWithIndex list \b, indexB ->
            if indexA < indexB then
                [Pair a b]
            else
                []
    |> List.join
    |> List.join

It's pretty long and inefficient, but I can't find a better way to implement this.

Anton (Jul 30 2024 at 11:57):

I don't think we have a builtin for that

Brendan Hansknecht (Jul 30 2024 at 15:02):

I think a manual recursive function would be best for these cases

Brendan Hansknecht (Jul 30 2024 at 15:02):

Probably doesn't fit in the standard library, but would make for a great package

Luke Boswell (Jul 30 2024 at 19:38):

This sounds similar to https://github.com/mulias/roc-array2d

Luke Boswell (Jul 30 2024 at 19:38):

@Elias Mulhall I think even did some demos with that in online meetup if I recall

Aurélien Geron (Jul 30 2024 at 21:02):

Thanks for your feedback. I wrote the following function:

combinations = \list, n ->
    if n == 0 || List.len list < n then
        []
    else if n == 1 then
        List.map list \v -> [v]
    else
        when list is
            [x, .. as rest] ->
                with = combinations rest (n - 1) |> List.map \combi -> List.prepend combi x
                without = combinations rest n
                List.concat with without

            _ -> crash "Unreachable"

To get pairs, I use:

toPair = \list ->
    when list is
        [a, b] -> Ok (Pair a b)
        _ -> Err "Element must be a list with 2 elements"

pairs = \list ->
    combinations list 2 |> List.keepOks toPair

I'm not sure how idiomatic or efficient this is, but it works. I wonder how I could avoid the crash "Unreachable" path. Not a big deal.

Brendan Hansknecht (Jul 30 2024 at 21:25):

I am not 100% sure the goal of your function, so this may be wrong, but I think it matches your original pairs function. This would be how I would write it efficiently:

pairs = \list ->
    len = Num.subSaturated (List.len list) 1
    cap = (len * (len + 1)) // 2
    List.walkWithIndex list (List.withCapacity cap) \outerAcc, elemA, i ->
        rem = List.dropFirst list (i + 1)
        List.walk rem outerAcc \innerAcc, elemB ->
            List.append innerAcc (elemA, elemB)

Last updated: Jul 06 2025 at 12:14 UTC