# Recommended patterns and techniques for Seqs (especially when memoized) **URL:** \ **Category:** Learning\ **Tags:** lazy, seq, memoization\ **Created:** [January 24, 2025, 2:35am UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019 "2025-01-24T02:35:05Z")\ **Posts on this page:** 14\ **Page:** 1
**Author:** ![bsidhom](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bsidhom/32/5763_2.png) [@bsidhom](https://discuss.ocaml.org/u/bsidhom)\ **Post date:** [January 24, 2025, 2:35am UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/1 "2025-01-24T02:35:05Z")
I’ve been playing with lazy sequences in the context of [this post](https://discuss.ocaml.org/t/why-dont-we-use-lazy-lists-in-ocaml/16010/3) (reimplementation of the [Power series, power serious paper](https://www.cambridge.org/core/journals/journal-of-functional-programming/article/power-series-power-serious/19863F4EAACC33E1E01DE2A2114EC7DF)). The performance problems I alluded to there were apparently due to nested/excessive memoziation being done (by calls to `Seq.memoize`). I was doing this pessimistically in an attempt to recreate the Haskell list behavior in OCaml. The ultimate fix I landed on was to implement _all_ base operations from the ground up using non-memoized `Seq.t`s and then expose a wrapper at the next level to simply wrap all of the inner `Seq.t`s in a call to `Seq.memoize`. So, for example, here’s the base interface (`Series_trunc.mli`): ```auto type t = Q.t Seq.t val coeffs : t -> Q.t Seq.t val nth : int -> t -> Q.t val zero : t val one : t val z : t val zpow : int -> t val neg : t -> t val ( + ) : t -> t -> t val ( - ) : t -> t -> t val ( *. ) : Q.t -> t -> t val ( * ) : t -> t -> t val ( / ) : t -> t -> t val compose : t -> t -> t ``` And here’s the memoized wrapper (`Series_memo.ml`): ```auto type t = Q.t Seq.t let coeffs fs = fs (* NOTE: We explicitly do NOT memoize anything we know to have O(1) terms. *) let nth = Series_trunc.nth let zero = Series_trunc.zero let one = Series_trunc.one let z = Series_trunc.z (* TODO: Consider memoizing iff n exceeds some threshold. *) let zpow n = Series_trunc.zpow n |> Seq.memoize let neg t = Series_trunc.neg t |> Seq.memoize let ( + ) fs gs = Series_trunc.(fs + gs) |> Seq.memoize let ( - ) fs gs = Series_trunc.(fs - gs) |> Seq.memoize let ( *. ) c fs = Series_trunc.(c *. fs) |> Seq.memoize let ( * ) fs gs = Series_trunc.(fs * gs) |> Seq.memoize let ( / ) fs gs = Series_trunc.(fs / gs) |> Seq.memoize let compose fs gs = Series_trunc.compose fs gs |> Seq.memoize ``` You can see the rest of the implementation [here](https://gist.github.com/bsidhom/6aa326d286cda811396baf6f09b1d100/613dcb0eb590c4ce3b1a127ca4349674f656f2e3). Is there a better way of doing this? In general, what are the pitfalls that one should avoid while working with memoized `Seq`s? I’m not sure _exactly_ what was going on with my original implementation (I no longer have that code and went through a lot of iterations), but I suspect that the problem was that I was double-memoizing many internal Seqs and causing extra memory pressure due to this. Obviously (based on empirical performance) the top-level memoziation is better, but it’s not clear if this is the best I can do. It is nearly certain that some extra memoization is happening where it doesn’t need to happen, and also that some recursive operations in the base implementation are _not_ memoized but should be. The fundamental issue is that there is no memoization by default (as in Haskell lists). As a result, _only_ explicitly memoized lists are retained. It looks like under the hood, this gets translated into a call to [`Lazy.from_fun`](https://github.com/ocaml/ocaml/blob/0adac826c991a8e5b2d7b4a9f6106ebeed10d0a5/stdlib/seq.ml#L436). Even if that function did explicitly avoid double-wrapping lazy results, I suspect that _any_ levels of indirection would prevent nested lazy cells from being collapsed. Can anybody point me to reliable patterns for avoiding this issue with lazy sequences, or is the general advice simply to ignore lazy/memoized values in general? (That’s the gist I was getting from the other thread). Beyond memoization per se, I’m not happy with how I ended up “manually” constructing the recursive sequence parts by helper functions (e.g., see [here](https://gist.github.com/bsidhom/6aa326d286cda811396baf6f09b1d100/613dcb0eb590c4ce3b1a127ca4349674f656f2e3#file-series_trunc-ml-L42)). I suspect there is a more idiomatic way to do this using the various `Seq` combinators, but I couldn’t figure out which if so. In this case, I’m essentially popping a single element off of the heads of two lists and then constructing the tail as a recursive expression possibly involving the head _and_ tails of two lists. This is more general than a simple operation like `map2`, etc., but it also requires in some cases extending the list beyond the length of the shortest of the two `Seq`s. (Implementation note: I ended up implementing this differently than the original Haskell version due to performance reasons. Many operations end up exponential in the number of sequences you are combining, so you can dramatically speed up computation by _truncating_ sequences at some upper bound; this allows you to propagate zeros indefinitely past that point and, in many cases, terminate early. It adds a bit of complexity to the implementation but yields big wins in runtime.) ---
**Author:** ![bsidhom](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bsidhom/32/5763_2.png) [@bsidhom](https://discuss.ocaml.org/u/bsidhom)\ **Post date:** [January 24, 2025, 6:22am UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/2 "2025-01-24T06:22:40Z")
After doing some test runs with the composition operator, I think I’m not actually memoizing enough here. I’m just not sure how to get more structural sharing of the various tails that get generated during the traversal. As I noted above, part of the problem is the “indirection” between the base `Seq.t` itself and its memoized version. Perhaps I’m not thinking of this correctly. Can I get what I want by throwing in a `lazy` cell somewhere? And if so, where? ---
**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\ **Post date:** [January 24, 2025, 8:38am UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/3 "2025-01-24T08:38:27Z")
I would not have memoized `zpow`. Regarding your question “Is it better to return the original fs or gs sequence below rather than reconstructing it?”, yes it is better to return the original value. (That is a generally valid advice, not even specific to your use case.) But notice that you have an issue here: you will end up memoizing something that is potentially already memoized (or deemed to not be worth memoizing). So, you are better handling laziness yourself rather than relying on `Seq.memoize` to do it. Finally, as you already noted, there is an issue with `compose`, as it will end up computing `go fs' gs` again and again. Its result should be memoized. ---
**Author:** ![bsidhom](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bsidhom/32/5763_2.png) [@bsidhom](https://discuss.ocaml.org/u/bsidhom)\ **Post date:** [January 24, 2025, 3:47pm UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/4 "2025-01-24T15:47:05Z")
How would you propose that I handle laziness myself? I’m having a hard time figuring out exactly where to put the lazy cell to get the desired behavior without double-wrapping. Just around the head, just around the tail, both, or around the entire Seq? ---
**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\ **Post date:** [January 24, 2025, 4:12pm UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/5 "2025-01-24T16:12:08Z")
Something like that (completely untested): ```ocaml let rec add fs gs = let value = lazy Seq.( match fs (), gs () with | Cons (f, fs'), Cons (g, gs') -> Cons (f + g, add fs' gs') | (Cons _ as fs), Nil -> fs | Nil, (Cons _ as gs) -> gs | Nil, Nil -> Nil) in fun () -> Lazy.force value ``` ---
**Author:** ![bsidhom](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bsidhom/32/5763_2.png) [@bsidhom](https://discuss.ocaml.org/u/bsidhom)\ **Post date:** [January 25, 2025, 12:15am UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/6 "2025-01-25T00:15:21Z")
Thanks, that works great! I didn’t consider making the _outer_ sequence value itself lazy. I also wouldn’t have considered the pattern of explicitly tying the `uncons` operation directly to `Lazy.force`, but this makes sense. Anyway, it turns out that the `compose` operator is the least of my concerns–the powerset and multiset constructions (in the context of analytical combinatorics) turn out to be non-trivial to implement for _unbounded_ sequences. That’s another topic for another day. 🙂 ---
**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\ **Post date:** [January 25, 2025, 1:14am UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/7 "2025-01-25T01:14:38Z")
You might be interested in \<[https://github.com/c-cube/oseq/](https://github.com/c-cube/oseq/)\>. I don’t recall if there’s multiset stuff but it should have combinations at least, and a memorization operator. ---
**Author:** ![zoj613](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/zoj613/32/5253_2.png) [@zoj613](https://discuss.ocaml.org/u/zoj613)\ **Post date:** [January 26, 2025, 3:56pm UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/8 "2025-01-26T15:56:06Z")
@dbuenzli once mentioned that use of `Seq` in a code base is a code smell and that there’s likely a better way to accomplish the task than using `Seq`. @dbuenzli Do you still feel the same, and if so, why? ---
**Author:** ![bsidhom](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bsidhom/32/5763_2.png) [@bsidhom](https://discuss.ocaml.org/u/bsidhom)\ **Post date:** [January 26, 2025, 5:21pm UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/9 "2025-01-26T17:21:12Z")
I’m _very_ curious to hear why. Specifically, whether these hang ups are around specific API design decisions in Seq itself or whether this is due to an opposition to the notion of lazy lists in general. FWIW, I do find the API a bit strange because it almost suggests an imperative/nondeterministic sequence due to the `unit -> 'a` signature. I suspect that in most cases, sequences are backed by a deterministic/reiterable implementation. Otherwise, why bother with a sequence abstraction at all? You might as well just provide some unit-callback in whatever context the Seq appears. Perhaps @c-cube can provide more color the decisions of the API shape, but my understanding was that this was more performant than alternatives considered (and wrapping everything in a lazy _forces_ users into memoization). ---
**Author:** ![bsidhom](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bsidhom/32/5763_2.png) [@bsidhom](https://discuss.ocaml.org/u/bsidhom)\ **Post date:** [January 26, 2025, 5:48pm UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/10 "2025-01-26T17:48:33Z")
The stereotypical situation where I find myself using Seq is when I have some computation that is naturally expressed as some recursion (or loop) and I want to share/reuse that computation in a “suspended” fashion. My only complaint with the Seq API is that it requires you to drop into continuation-passing style. This is why I’m so excited about the possibility of [first-class (or at least ergonomic) generators](https://discuss.ocaml.org/t/implementing-simple-generators-with-effect-handlers/16020). ---
**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\ **Post date:** [January 26, 2025, 5:53pm UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/11 "2025-01-26T17:53:19Z")
You can read the two PRs that lead to Seq. \<[https://github.com/ocaml/ocaml/pull/635](https://github.com/ocaml/ocaml/pull/635)\> \<[https://github.com/ocaml/ocaml/pull/1002](https://github.com/ocaml/ocaml/pull/1002)\> In essence, Seq is the design that got merged, after failing to agree on basically every other design first over the years. It works for mutable and immutable sources and it’s simple. I sometimes wish the design was different, but it’s better to have _something_ than nothing and we failed to do better (in terms of performance, mostly). ---
**Author:** ![dbuenzli](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/dbuenzli/32/18_2.png) [@dbuenzli](https://discuss.ocaml.org/u/dbuenzli)\ **Post date:** [January 26, 2025, 9:52pm UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/12 "2025-01-26T21:52:37Z")
> [@zoj613](#): > > @dbuenzli Do you still feel the same, and if so, why? Seqs are fine and natural for certain things. They are just not a very good tool for the reason they have been introduced to in the stdlib which was something like “provide a uniform interface to enumerate the elements of containers”. So when I see them used in that context I find them a smell. First due to life times and mutation they are not a very good enumerator for imperative datastructures which the stdlib is littered with. Second what one is seeking to do is very often more efficiently done via an `iter` or a `fold`. This is exactly what happend when I made the comment you mentioned: > I’m not sure exactly how came up with the idea of converting to maps, partition them and then iterate over them with Seqs (Seqs are always code smells). At that point you have gone twice over the member of your archive, have sorted its paths twice, redone the map twice, and generated a lot of gc garbage with totally useless Seqs. Intead of a simple Zipc.fold. I can see why people reach for them (direct style) but I think that most of the time code is better off if people [learn](https://people.cs.nott.ac.uk/pszgmh/fold.pdf) to `fold`. ---
**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\ **Post date:** [January 27, 2025, 12:34am UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/13 "2025-01-27T00:34:16Z")
For that use case I still favor my `iter` package, which is fairly fast (at least with flambda) and generally reads better than folds as soon as things go beyond a simple traversal 🙂. It’s compatible with stdlib containers, too (but it’s push, not pull, so slightly less general than Seq). ---
**Author:** ![bsidhom](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bsidhom/32/5763_2.png) [@bsidhom](https://discuss.ocaml.org/u/bsidhom)\ **Post date:** [January 27, 2025, 1:24am UTC](https://discuss.ocaml.org/t/recommended-patterns-and-techniques-for-seqs-especially-when-memoized/16019/14 "2025-01-27T01:24:03Z")
`Seq` is also nice for idiomatically implementing things like `Traversable`, which is not a common idiom in OCaml. In fact, I find `Seq` to be a nice atomic primitive given that operations are generally ad hoc in OCaml. The issue is that you–as a data structure author–don’t assert up-front which interfaces your structure implements but do so implicitly through the functions you _happen_ to implement. And because those are not stated explicitly, it can often be difficult to generalize or recognize patterns without having seen them called out elsewhere. Case in point: much of the vocabulary and common interfaces used in modern OCaml originated in Haskell. This is all to say that I don’t think it’s immediately obvious that one is better than the other. The fact that–as you call out–translation to-and-from Seq generates a lots of intermediate garbage is an “implementation detail”. On the other hand, something that I appreciate about OCaml (and the OCaml community) is the attention to detail that can have a material impact on runtime properties. Edit: that was meant to be a response to @dbuenzli l, but I think I clicked the wrong button.