为什么需要rlist数据结构?它有哪些优点?
如果示例显示为(4, (3, (2, (1, None))))
,我会认为它可以扩展到(5, (4 (3, (2, (1, None)))))
,这就像任何其他链接列表一样完全有意义。
但由于这个例子是(1, (2, (3, (4, None))))
,尽管可能的话,像(5, (1, (2, (3, (4, None)))))
一样向外延伸,似乎与所示数据的方向相反。我觉得这不是这种数据结构的意图。由于(4, None)
无法修改,因此无法扩展tuples
。
那么,这种数据结构的真正目的是什么?即使有可能扩展它,我也不明白为什么它比(1, 2, 3, 4)
更好!
由于课程改编自Scheme,他们是否试图展示Scheme的lists?如果是这样,Scheme的lists
会增长还是静止?甚至Lisp的example显示cons
像(cons 5 x)
一样构造来展示(5 1 2 3)
,这对像我这样的初学者来说真的是反直觉的。
我正在尝试适应点点滴滴,请帮忙!
评论中已经提到过这一点,但要将其作为答案发布:
递归列表(不是特定于Scheme的)在两个上下文中很有用:
这是因为它们允许在不修改原始列表的情况下扩展列表。
在图表中查找路径时会出现这种情况。比如说,你试图找到从你家到工作场所的N条最佳路径(想想谷歌地图),你开始从工作场所(你的目的地)搜索并考虑不同的街道,向后移动,直到你找到你的房子0.1
这里发生的是许多路径将共享相同的“后缀”,因此您只需要共享这些部分并代表它们一次,以节省内存(因为您不重复路径)和时间(因为您不必花时间复制前一个路径只是为了添加不同的前缀)。
现在,你可能会想到“为什么我想要的目的地超过一些路径?”好吧,你可能不想,如果“你”在某个特定时间点将你称为一个人。但是,如果您尝试在不同的交通条件下(例如在不同的时间点)模拟许多驱动程序,那么突然节省内存和计算时间将非常重要,并且能够共享部分数据结构并在此基础上构建平行的顶部可以产生巨大的差异。
1您也可以使用某些算法向前搜索,但向后搜索更为通用。无论如何,方向在这里并不重要。