我正在编写一个程序，我想使用的一种算法需要一种廉价的反向访问列表的方法才能有效。是否有一种有效的方法从最后一个元素开始访问列表?或者，因为我认为由于SML列表的结构，这可能是不可能的，是否有一种有效的数据结构来实现它?
数据的长度在执行之前是未知的，因此不需要对数据进行串行遍历。
我认为你需要一个功能队列。参见冈崎关于这个主题的论文。具体来说，图5显示了deque的实现。
如果使用函数队列似乎有点过分，并且您需要以反向顺序遍历列表一次，那么使用List.last和List.take来模拟hd和tl但以反向顺序的解决方案，如您所知，坏的，因为它们会使列表遍历二次。另一方面，内置函数rev非常高效，因为它既是尾部递归的，又是线性的。如果将一个列表提供给一个需要反向遍历该列表的函数，一个简单的解决方案是使用let绑定，使用rev以反向顺序创建列表的本地副本，然后以通常的方式遍历反向列表。