# A tail-recursive List.flatten in Stdlib?

**URL:** <https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382>\
**Category:** Ecosystem\
**Tags:** stdlib, list\
**Created:** [October 3, 2024, 8:11pm UTC](https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382 "2024-10-03T20:11:47Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![Chris1](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chris1/32/4847_2.png) [@Chris1](https://discuss.ocaml.org/u/Chris1)\
**Post date:** [October 3, 2024, 8:11pm UTC](https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382/1 "2024-10-03T20:11:47Z")

</div>

I was perusing the OCaml source code for `Stdlib.List` and noticed that `List.flatten` is implemented in a non-tail-recursive manner.

> ```auto
> let rec flatten = function
> [] -> []
> | l::r -> l @ flatten r
> 
> ```

Is there a compelling reason not to implement this using [tail\_mod\_cons](https://ocaml.org/manual/5.2/tail_mod_cons.html) to make this function tail-recursive?

It doesn’t seem like a very difficult [change](https://github.com/ocaml/ocaml/compare/trunk...cdutton80:ocaml:patch-1) to make.

```auto
let[@tail_mod_cons] rec flatten = function
  | [] -> []
  | []::xs -> flatten xs
  | [x]::xs -> x :: flatten xs
  | (x::x'::xs)::ys -> x :: x' :: flatten (xs::ys)

```

---

<div class="post-metadata">

**Author:** ![nojb](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nojb/32/519_2.png) [@nojb](https://discuss.ocaml.org/u/nojb)\
**Post date:** [October 4, 2024, 4:40am UTC](https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382/2 "2024-10-04T04:40:43Z")

</div>

> [@Chris1](#):
>
> It doesn’t seem like a very difficult [change](https://github.com/ocaml/ocaml/compare/trunk...cdutton80:ocaml:patch-1) to make.

The definition you propose can be simplified to:

```auto
let[@tail_mod_cons] rec flatten = function
  | [] -> []
  | []::xs -> flatten xs
  | (x::xs)::ys -> x :: flatten (xs::ys)

```

This function performs twice as many allocations as the total number of elements (because each element gives rise to two allocations, `x ::` and `xs ::`). Hence it performs twice as many allocations as the (non-tail-recursive) version found in the standard library. It is better than the naïve tail-recursive function using an accumulator which performs three times as many allocations as the total number of elements, but it will still lose against the non-tail-recursive version for most practical inputs.

Cheers,  
Nicolas

---

<div class="post-metadata">

**Author:** ![yallop](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/yallop/32/517_2.png) [@yallop](https://discuss.ocaml.org/u/yallop)\
**Post date:** [October 4, 2024, 6:17am UTC](https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382/3 "2024-10-04T06:17:27Z")

</div>

That definition can be transformed to avoid the extra allocation by specializing the call `flatten (xs :: ys)` via a function `flatten_cons` that takes `xs` and `ys` separately, like this:

```ocaml
let[@tail_mod_cons] rec flatten = function
  | [] -> []
  | []::xs -> flatten xs
  | (x::xs)::ys -> x :: flatten_cons xs ys
and[@tail_mod_cons] flatten_cons xs ys =
  match xs with
  | [] -> flatten ys
  | x::xs -> x :: flatten_cons xs ys

```

The paper [Tail Modulo Cons](https://inria.hal.science/hal-03146495/document) (by @let-def, @Elarnon and @gasche) gives a similar implementation, but obtained by inlining append in the non-tail-recursive version, as does the [manual](https://ocaml.org/manual/5.2/tail_mod_cons.html).

---

<div class="post-metadata">

**Author:** ![craff](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/craff/32/3281_2.png) [@craff](https://discuss.ocaml.org/u/craff)\
**Post date:** [October 4, 2024, 6:46am UTC](https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382/4 "2024-10-04T06:46:45Z")

</div>

A bit simpler and fixing the xs that should be ys

```auto
let[@tail_mod_cons] rec flatten = function
  | [] -> []
  | xs::ys -> flatten_cons xs ys
and[@tail_mod_cons] flatten_cons xs ys =
  match xs with
  | [] -> flatten ys
  | x::xs -> x :: flatten_cons xs ys

```

---

<div class="post-metadata">

**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:** [October 4, 2024, 7:07am UTC](https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382/5 "2024-10-04T07:07:24Z")

</div>

Note that, if you do not also annotate `flatten` with `[@tail_mod_cons]`, then `flatten_cons` will be calling a non-specialized function (`[] -> flatten ys`), so the optimization cannot trigger. Both functions need to be annotated.

---

<div class="post-metadata">

**Author:** ![gasche](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gasche/32/4_2.png) [@gasche](https://discuss.ocaml.org/u/gasche)\
**Post date:** [October 4, 2024, 7:28am UTC](https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382/6 "2024-10-04T07:28:12Z")

</div>

The rule we followed so far in the stdlib is to convert functions to use TMC on-demand (no big change where we reviewed all trmc-able functions), and to perform a micro-benchmark to check that the TMC definition is as fast as the non-tail-rec one, including on small lists. In our experience this generally requires some manual unrolling of the TMC version (one or two steps of unrolling is often enough). See for example [TRMC implementation of @ by yallop · Pull Request #11859 · ocaml/ocaml · GitHub](https://github.com/ocaml/ocaml/pull/11859) , which moved `@` to be tail-recursive.

Anyone should feel free to propose a TMC version of `List.flatten`, as long as they follow the same policy: write a micro-benchmark to check the impact on small inputs.

---

<div class="post-metadata">

**Author:** ![Chris1](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/chris1/32/4847_2.png) [@Chris1](https://discuss.ocaml.org/u/Chris1)\
**Post date:** [October 6, 2024, 6:16pm UTC](https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382/7 "2024-10-06T18:16:55Z")

</div>

Having done some testing on speed the impact seems to range from 8-20% slower with TMC using ocamlc. Results with ocamlopt were worse seeing ~40-50+% longer execution times.

I cheerfully withdraw my suggestion in the face of pragmatism.

---

<div class="post-metadata">

**Author:** ![nojb](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nojb/32/519_2.png) [@nojb](https://discuss.ocaml.org/u/nojb)\
**Post date:** [October 6, 2024, 8:05pm UTC](https://discuss.ocaml.org/t/a-tail-recursive-list-flatten-in-stdlib/15382/8 "2024-10-06T20:05:05Z")

</div>

> [@Chris1](#):
>
> Results with ocamlopt were worse

Note that there are some GC effects related to the write barrier that need to be taken into consideration when benchmarking; see the discussion at

> <https://github.com/ocaml/ocaml/pull/11362#issuecomment-1168396482>
>
> There are interesting GC effects related to the write barrier, that create a per…formance disadvantage for TRMC when:
> \- you \`ignore\` the result of List.map right away instead of keeping it alive until the next minor GC
> \- the allocation work of the List.map size is comparable to the minor heap size
> 
> This may very well be what you observe in your benchmark. I would try writing the result of \`List.map\` to a global reference instead of \`ignore\`-ing it right away. (This corresponds to the case where the lifetime of the result is extended until at least the next minor collection, which is a reasonable assumption.)
> 
> For more details, see the discussion of "Promotion" in \[the second TRMC PR\](https://github.com/ocaml/ocaml/pull/9760).

Cheers,  
Nicolas