[spooky_deep]

A good compiler will make the lists disappear in many cases. No runtime overhead. I actually love single linked lists as a way to break down sequences of problem steps.

[kragen]

In Haskell, yes, because laziness permits deforestation. ML, including OCaml, is eager and consequently cannot do this.

[MrJohz]

I believe it's possible in theory - Koka has a whole "functional but in-place" set of compiler optimisations that essentially translate functional algorithms into imperative ones. But I think that's also possible in Koka in part because of its ownership rules that track where objects are created and freed, so might also not be feasible for OCaml.

[int_19h]

Why would a specific way of structuring data in memory be relevant to breaking down sequences of problem steps?

If what you mean is the ability to think in terms of "first" and "rest", that's just an interface that doesn't have to be backed by a linked list implementation.

[olivia-banks]

I’m curious what you mean. Surely there’s the overhead of unpredictable memory access?

[deredede]

Not GP but bump allocation (OCaml's GC uses a bump allocator into the young heap) mitigates this somewhat, list nodes tend to be allocated near each other. It is worse than the guaranteed contiguous access patterns of a vector, but it's not completely scattered either.

[otabdeveloper4]

Ah yes, our old friend - the sufficiently smart compiler.