为什么你只能在功能语言中加入列表？ [英] Why can you only prepend to lists in functional languages?
问题描述
我只使用了三种函数式语言 - scala，erlang和haskell，但在所有这三种语言中，构建列表的正确方法是将新数据预先放在前面，然后倒转它，而不是仅追加到结束。当然，你可以追加到列表中，但是会产生一个全新的列表。
这是为什么？我可以想象这是因为列表内部实现为链接列表，但为什么它们不能被实现为双向链接列表，因此您可以追加到最后而没有任何处罚？是否有一些原因，所有的功能语言都有这个限制？
函数式语言中的列表是不可变的/持久的。
追加到不可变列表的前面是很便宜的，因为您只需分配一个节点，其下一个指针指向前一列表的开头。没有必要更改原始列表，因为它只是一个单独链接列表，并且指向前一个头部的指针无法看到更新。
在列表末尾添加一个节点需要修改最后一个节点以指向新创建的节点。只有这是不可能的，因为节点是不可变的。唯一的选择是创建一个与最后一个节点具有相同值并指向新创建尾部的新节点。这个过程必须一直重复到列表的前面，产生一个全新的列表，它是第一个列表的副本，但是不包括尾部节点。因此更昂贵。
I have only used 3 functional languages -- scala, erlang, and haskell, but in all 3 of these, the correct way to build lists is to prepend the new data to the front and then reversing it instead of just appending to the end. Of course, you could append to the lists, but that results in an entirely new list being constructed.
Why is this? I could imagine it's because lists are implemented internally as linked lists, but why couldn't they just be implemented as doubly linked lists so you could append to the end with no penalty? Is there some reason all functional languages have this limitation?
Lists in functional languages are immutable / persistant.
Appending to the front of an immutable list is cheap because you only have to allocate a single node with the next pointer pointing to the head of the previous list. There is no need to change the original list since it's only a singly linked list and pointers to the previous head cannot see the update.
Adding a node to the end of the list necessitates modifying the last node to point to the newly created node. Only this is not possible because the node is immutable. The only option is to create a new node which has the same value as the last node and points to the newly created tail. This process must repeat itself all the way up to the front of the list resulting in a brand new list which is a copy of the first list with the exception of thetail node. Hence more expensive.
这篇关于为什么你只能在功能语言中加入列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
