OCaml中的固定时间列表串联

Question

是否可以在OCaml中实现固定时间列表串联？

我想象一种方法，通过将第一个列表的末尾指向第二个列表的开头，我们直接处理内存并连接列表。本质上，我们正在创建某种类型的链接列表，例如object。

Answer 1

对于普通列表类型，不可以，不能。您给出的算法正是实现的算法...但是您仍然必须真正找到第一个列表的末尾...

有多种方法可以实现恒定时间串联（有关详细信息，请参见Okazaki）。我只给您实现它的ocaml库的名称：BatSeq，BatLazyList（均在电池中），sequence，gen，Core.Sequence。可以肯定的是，在某处也有一个diff-list实现。