Hey, all! Somewhat of a quick question: Recently, I’ve been trying to optimise the memory usage of a program of mine that uses lists by swapping to Seq.t and switching from eager to lazy computation.

One thing that I’ve found was missing from the stdlib and from the stdlib replacement I’m currently using (`Containers`

), is a generalised cartesian product `map_product: ('a -> 'b Seq.t) -> 'a Seq.t -> 'b list Seq.t`

function for Seqs.

Naturally, it’s not too hard to write your own version, but I’ve been running into difficulties working out what would be the best encoding for this function to ensure that the computation is as lazy as possible.

My initial encoding was just a straightforward translation of the map_product function for Lists defined in the containers stdlib:

```
let seq_map_product_l (type a b) (f: a -> b Seq.t) (l: a Seq.t) : b list Seq.t =
let rec prod_rec (left: b list) (right: a CCSeq.t) (acc: b list Seq.t) () =
match right () with
| Seq.Nil -> Seq.Cons (List.rev left, acc)
| Seq.Cons (l1, tail) ->
let (l1: b CCSeq.t) = f l1 in
Seq.fold_left
(fun acc x -> prod_rec (x::left) tail acc)
acc l1 in
prod_rec [] l Seq.nil
```

But the problem turns out to be slightly more subtle than I expected and this naive translation ends up being too eager. In particular, Seq.fold_left is an eager computation, and fully traverses the sequence it is passed in as an argument. Thus, in order to even get a single element out of this combinator, you’d have to effectively compute all of the sequences produced by each invocation of `f`

.

After running into this, I ended up switching to the following implementation, which seems to fare a lot better:

```
let seq_map_product_l (type a b) (f: a -> b Seq.t) (l: a Seq.t) : b list Seq.t =
let rec prod_rec (left: b list) (right: a CCSeq.t) () =
match right () with
| Seq.Nil -> Seq.Cons (List.rev left, Seq.nil)
| Seq.Cons (l1, tail) ->
let (l1: b CCSeq.t) = f l1 in
Seq.flat_map (fun l1_elt ->
prod_rec (l1_elt::left) tail
) l1 () in
prod_rec [] l
```

Anyway, I was wondering if this updated implementation is optimal, or whether there might be any further changes I should make (excluding things like memoization etc. which I don’t need for my usecase).