群组首页 → 编程语言 → Scala圈子 → 论坛
发表回复

我一直觉得Scala里的List设计的很诡异

davepkxxx 2012-01-18
如果List做不到增加自己的元素，那么它和Array有什么区别？
Eastsun 2012-01-18
区别大了。
List不能添加元素是为了保持immutable，函数式编程语言中的List基本都是这么设计的。
如果你需要能添加元素的list，完全可以用ListBuffer啊。

而且要注意的是List中访问一个元素的时间是O(n)级的。

如果你需要的是一个能添加元素的类Array，可以用ArrayBuffer，当然也可以用Vector。
davepkxxx 2012-01-18
但是为什么要保持immutable呢？Array已经保持了immutable，没必要在设计一个集合来保持immutable吧？
Eastsun 2012-01-18
davepkxxx 写道
但是为什么要保持immutable呢？Array已经保持了immutable，没必要在设计一个集合来保持immutable吧？



Array是immutable的？囧....
Array的大小固然不可以改变，但里面的内容是可以改变的。
davepkxxx 2012-01-18
为什么要做出一个而完全不可变的集合呢？
Eastsun 2012-01-18
davepkxxx 写道
为什么要做出一个而完全不可变的集合呢？


一方面函数式编程的风格就是不可变性：如果你用过Haskell就知道，里面的一切都是不可变的。

另一方面为了并行、多线程，一个集合是不可变的就保证了它可以安全的被多个线程共享。一个mutable的集合如何在多个线程之间安全操作是一个非常烦人的事情。immutable就没这个问题了。
kidneyball 2012-01-25
我的理解是：List是一个保证了前端入队和取尾集（tail）效率的不可变队列。
例如你写：
val a = List (1,2,3)
val b = 4 :: a
能得到b为List(4,1,2,3)，而且在这个赋值过程中，没有发生对象复制（不会出现两份1,2,3）。b的内部表示可以理解为是 4 -> List(1,2,3)，也就是 4 -> a。

其实，a的内部表示可以理解为 1 -> (2 -> (3 -> List()))，这也解释了为什么List的元素访问复杂度是O(n)

List与Array（即使你不去改Array内的元素）的主要区别是：
1. 它在API层面上保证了内部元素不变
2. 它取尾集（去掉头几个元素后剩下的List）的效率是很高的，非常适用基于模式匹配的迭代。
例如：
def foo(l : List[Int]) => match l {
    case x::xs => x + foo(xs);
    case _ => 0;
}
如果用Array，每次递归都会导致n-1个元素被复制。如果在java里，一般只能通过额外Index或Iterator来进行迭代。而Index本身，就形成了副作用，你必须关注某个动作应该在Index变化之前还是之后做。
发表回复
Global site tag (gtag.js) - Google Analytics