SML/NJ - 从头到尾访问的有效方式或数据结构
SML/NJ - Effective way or data structure to access from end towards the start
我正在制作一个程序，我想使用的算法需要一种廉价的向后访问列表的方法才能有效。有没有一种有效的方法可以从最后一个元素向前访问列表？或者，因为我认为由于 SML 列表的结构，这可能是不可能的，是否有有效的数据结构来实现它？
数据长度在执行前是未知的，除了串行遍历外不需要数据。
我想你想要一个功能性的双端队列。参见例如Okasaki's paper on the subject。具体来说，图 5 显示了双端队列的实现。
如果使用函数式双端队列看起来有点矫枉过正，并且您只需要以相反的顺序遍历列表一次，那么解决方案例如使用 List.last 和 List.take 来模拟 hd 和 tl，但如您所知，相反的顺序是不好的，因为它们会使列表遍历二次。另一方面，内置函数 rev 非常高效，因为它既是尾递归又是线性的。如果您将列表提供给需要以相反顺序遍历该列表的函数，一个简单的解决方案是使用 let 绑定，使用 rev 以相反顺序创建列表的本地副本，然后以通常的方式遍历反向列表。
我正在制作一个程序，我想使用的算法需要一种廉价的向后访问列表的方法才能有效。有没有一种有效的方法可以从最后一个元素向前访问列表？或者，因为我认为由于 SML 列表的结构，这可能是不可能的，是否有有效的数据结构来实现它？
数据长度在执行前是未知的，除了串行遍历外不需要数据。
我想你想要一个功能性的双端队列。参见例如Okasaki's paper on the subject。具体来说，图 5 显示了双端队列的实现。
如果使用函数式双端队列看起来有点矫枉过正，并且您只需要以相反的顺序遍历列表一次，那么解决方案例如使用 List.last 和 List.take 来模拟 hd 和 tl，但如您所知，相反的顺序是不好的，因为它们会使列表遍历二次。另一方面，内置函数 rev 非常高效，因为它既是尾递归又是线性的。如果您将列表提供给需要以相反顺序遍历该列表的函数，一个简单的解决方案是使用 let 绑定，使用 rev 以相反顺序创建列表的本地副本，然后以通常的方式遍历反向列表。