How to compare Lists

Indeed! My function minimizes the number of cons cells read (so has the right asymptotic complexity), but it does keep allocating lists and pairs (options do not really matter, I hope they are optimized away with enough inlining). We can avoid it using mutable fields and a mutable linked list, but… at that point I don’t think there is any advantage over your function.

Initially I thought that, maybe, folding with List.compare_lengths might have a worse complexity, but now that I think about it, I realize it is just a factor 2*. So your allocation-less function is much better.

[*: If L is the length of the longest list, and ℓ1, ℓn are the lengths of all lists but the longest one, then the number of cons cells read by my function is ℓ1 + … + ℓn + max(ℓ1, …, ℓn), while with your function it is 2ℓ1 + … + 2ℓn, because List.compare_lengths xs ys reads 2 * min (length xs) (length ys) cons cells.]