SML/NJ - 有效的方法或数据结构从头开始访问开始

Question

我正在制作一个程序，而我以为使用的算法需要一种廉价的方式来访问列表以使其有效。有没有一种有效的方法来访问最后一个元素的列表？或者，因为我认为这可能是不可能的，因为SML列表的结构，是否有一个有效的数据结构来实现它？

数据的长度在执行之前是未知的，除了串行遍历数据外，不需要其他数据。

Answer 1

我认为你想要一个功能性的双层屋顶。见例如Okasaki's paper on the subject。具体来说，图5显示了deques的实现。

Answer 2

如果使用功能性deque看起来像是矫枉过正，并且您只需要以相反顺序遍历列表一次，那么解决方案（例如，使用List.last和List.take来模拟hd和tl，但是按照您看起来知道的那样，倒序是相反的，因为它们会使列表遍历为二次方。另一方面，内置函数rev非常高效，因为它既是尾递归又是线性的。如果您向需要以相反顺序遍历该列表的函数提供列表，则一个简单的解决方案是使用let使用rev进行绑定，以相反顺序创建列表的本地副本，然后以常规方式遍历反向列表。