I'm trying to get into a functional mind set with Rust by struggling with sequencing/cartesian products of vectors

Im trying to make a rust version of this F# snippet:

let sequence list =
     let folder (item: _ list) (state: _ list list) =
         [ for x in item do 
              for xs in state -> x::xs ]
     List.foldBack folder list [[]]

Which is essentially taking a list of lists and creating a cartesian product of each list, and yes I know I can just use the itertools crate like this:

    let x = vec![1, 2, 3];
    let y = vec![10, 20, 30];
    let z = vec![100, 200, 300];
    let all = vec![x, y, z];
    let all_combinations = all.iter().multi_cartesian_product().collect::<Vec<_>>();

Which produces the output:

[[1, 10, 100], [1, 10, 200], [1, 10, 300], [1, 20, 100], [1, 20, 200], [1, 20, 300], [1, 30, 100], [1, 30, 200], [1, 30, 300], [2, 10,
 100], [2, 10, 200], [2, 10, 300], [2, 20, 100], [2, 20, 200], [2, 20, 300], [2, 30, 100], [2, 30, 200], [2, 30, 300], [3, 10, 100], [
3, 10, 200], [3, 10, 300], [3, 20, 100], [3, 20, 200], [3, 20, 300], [3, 30, 100], [3, 30, 200], [3, 30, 300]]

But I want to do this with the standard library and just fold if possible?

Do you specifically want to use linked lists like you do in F#?

Here's one version (Playground) with a focus on translating the F# code as directly as possible, without regard for performance:

    all.iter().rev().fold(vec![vec![]], |state, item| {
        item.iter().flat_map(|x| 
            state.iter().map(|xs| {
                let mut v = vec![x];
                v.extend(xs);
                v
            }).collect::<Vec<_>>()
        ).collect::<Vec<_>>()
    })
2 Likes

I was trying to use vectors but Im struggling to map functional concepts over to rust so any collections really.

Thanks, Im wondering about removing the flat_map at the top.

I mean the F# code is idiomatic, but I want to gain the mental mapping of what this would be in idiomatic Rust too?

1 Like

The inner state.iter().map(...).collect() will produce a Vec<Vec<T>> with all the combinations for a single starting element, like [[10, 100], [10, 200], [10, 300]].

We'll get one of these Vec<Vec<T>> for each starting element in item. If the outer operation were also item.iter().map(...).collect() then we'd end up with a Vec<Vec<Vec<T>>>, with where each item is one of the Vec<Vec<T>> returned by the inner collect:

[
    [[10, 100], [10, 200], [10, 300]], 
    [[20, 100], [20, 200], [20, 300]],
    [[20, 100], [30, 200], [30, 300]],
]

We don't want each of these to be a separate item in the output list; instead we want to concatenate ("flatten") them. This is what flat_map does: It iterates over all the items of the inner collections, turning them into items of the new, larger iteration.

1 Like

In F# or Haskell terms, you can think of flat_map as being the bind operation for the Iterator "monad".

1 Like

Sorry, I misread your comment. If you want to get rid of flat_map, then you could maybe replace it with a fold like this:

    all.iter().rev().fold(vec![vec![]], |state, item| {
        item.iter().fold(vec![], |mut items, x| {
            items.extend(state.iter().map(|xs| {
                let mut v = vec![x];
                v.extend(xs);
                v
            }).collect::<Vec<_>>());
            items
        })
    })

As for idiomatic Rust, I would probably either implement a custom iterator (like itertools does), or use a more "procedural" approach with explicit recursion like this:

fn cartesian_product<T>(v: &[Vec<T>]) -> Vec<Vec<&T>> {
    if let Some((item, items)) = v.split_first() {
        let state = cartesian_product(items);
        let mut result = vec![];
        for x in item {
            for xs in &state {
                let mut v = vec![x];
                v.extend(xs);
                result.push(v)
            }
        }
        result
    } else {
        vec![vec![]]
    }
}
1 Like

Yeah in F# its xs |> List.concat or xs |> List.collect id

If the type needs to be mma -> ma, bind has that capacity, but join is more precisely what you are suggesting. Finally, only because this is a “thing” for me, to the degree monad remains useful here, we should be describing Applicative instead.

This would be an applicative sequence or traverse id

I think one thing that didn't occur to me is the list comprehension was effectively:

List.collect (fun x -> List.map (fun xs -> x::xs))

So that would correlate closer to your first suggestion:

 item.iter().flat_map(|x| 
            state.iter().map(|xs| {
...

Theres also rfold in the std lib so that would eliminate the rev.

I guess its going to take a little time to get used to a more rust like approach, I guess I expected rust to be more functional in style.

Thanks!

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.