# Laziest encoding of map\_product for Seq.t

**URL:** <https://discuss.ocaml.org/t/laziest-encoding-of-map-product-for-seq-t/10677>\
**Category:** Learning\
**Created:** [October 22, 2022, 9:08am UTC](https://discuss.ocaml.org/t/laziest-encoding-of-map-product-for-seq-t/10677 "2022-10-22T09:08:12Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Gopiandcode](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gopiandcode/32/5346_2.png) [@Gopiandcode](https://discuss.ocaml.org/u/Gopiandcode)\
**Post date:** [October 22, 2022, 9:08am UTC](https://discuss.ocaml.org/t/laziest-encoding-of-map-product-for-seq-t/10677/1 "2022-10-22T09:08:12Z")

</div>

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:

```ocaml
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:

```ocaml
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).

---

<div class="post-metadata">

**Author:** ![art-w](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/art-w/32/4728_2.png) [@art-w](https://discuss.ocaml.org/u/art-w)\
**Post date:** [October 22, 2022, 10:06am UTC](https://discuss.ocaml.org/t/laziest-encoding-of-map-product-for-seq-t/10677/2 "2022-10-22T10:06:18Z")

</div>

You might want to compare with `OSeq.map_product_l` [implementation](https://github.com/c-cube/oseq/blob/master//src/OSeq.ml#L618) which produces values in a different order (which looks a bit more “fair” thanks to `interleave`, but which one is better depends on your use-case!)  
Also, the outer `'a Seq.t` has to be forced from the get-go, so perhaps it’s easier to reason about an implementation of `'a Seq.t list -> 'a list Seq.t`?

---

<div class="post-metadata">

**Author:** ![Gopiandcode](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gopiandcode/32/5346_2.png) [@Gopiandcode](https://discuss.ocaml.org/u/Gopiandcode)\
**Post date:** [October 22, 2022, 10:27am UTC](https://discuss.ocaml.org/t/laziest-encoding-of-map-product-for-seq-t/10677/3 "2022-10-22T10:27:35Z")

</div>

Ah, nice, thanks for the pointer. I should definitely have a read through OSeq.

> [@art-w](#):
>
> `OSeq.map_product_l` [implementation](https://github.com/c-cube/oseq/blob/master//src/OSeq.ml#L618) which produces values in a different order (which looks a bit more “fair” thanks to `interleave`, but which one is better depends on your use-case!)

Yes, I had considered the issue of fairness w.r.t the sequence of outputs, although for now, as the original list implementation I was using wasn’t doing any interleavings, I wanted to preserve the existing functional behaviour and purely experiment with evaluation strategy (which actually turned out to be quite fruitful, taking my peak memory usage from 10GBs down to just 200MB).

> [@art-w](#):
>
> Also, the outer `'a Seq.t` has to be forced from the get-go, so perhaps it’s easier to reason about an implementation of `'a Seq.t list -> 'a list Seq.t`?

Yes, good point - I had considered taking a list as input, and maybe I should instead, but my initial implementation decided to operate over `Seq.t`s simply to preserve a consistent interface for my utility functions (most of the sequences being passed around were already as Seq.t now, so changing the interface to List.t would require adding additional conversion operators throughout my codebase).

---

<div class="post-metadata">

**Author:** ![art-w](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/art-w/32/4728_2.png) [@art-w](https://discuss.ocaml.org/u/art-w)\
**Post date:** [October 22, 2022, 11:17am UTC](https://discuss.ocaml.org/t/laziest-encoding-of-map-product-for-seq-t/10677/4 "2022-10-22T11:17:52Z")

</div>

Ha yes, that’s a good exercise! I mentioned `interleave` because it’s an interesting difference of how we program with List vs Seq, as we have to take into consideration that they could be _infinite_ lazy lists (see for example the [LogicT.pdf](https://okmij.org/ftp/Computation/monads.html#LogicT) paper for motivations)

---

<div class="post-metadata">

**Author:** ![edwin](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/edwin/32/627_2.png) [@edwin](https://discuss.ocaml.org/u/edwin)\
**Post date:** [October 24, 2022, 10:28pm UTC](https://discuss.ocaml.org/t/laziest-encoding-of-map-product-for-seq-t/10677/5 "2022-10-24T22:28:01Z")

</div>

If you are looking at reducing the work the GC has to do with temporaries (I’m assuming that is the memory optimization you are refering to) then try looking at iterators too, they have somewhat less overhead than sequences depending on the situation (although the stdlib doesn’t provide composable iterators, there are a few libraries on opam that do), especially if you combine it with flambda.

I haven’t done my own benchmarks to confirm, but [GitHub - rizo/streams-bench: Benchmarks for different streaming models: iterators, generators, sequences, transducers, etc.](https://github.com/rizo/streams-bench) contains a quite thorough measurements of the various sequence/iterator implementations (with `flambda`, YMMV).  
There is a product implementation that you can compare with here too [Stream (streaming.Streaming.Stream)](https://odis-labs.github.io/streaming/streaming/Streaming/Stream/index.html#val-product) (and you can compare the eagerness/lazyness of that implementation with yours).