论Clojure的"第一"功能

Question

我在Rich的视频中看到了以下关于序列http://blip.tv/file/734409的示例, 大约需要33-36分钟:

(first "abcd") => \a

现在,他说这扩展到(有点):

(first "abcd") => (first (seq "abcd")) => (first '(\a \b \c \d))

因此,它看起来像一个O(N)操作,因为正在创建字符串的完整副本.首先,如果a String是不可变的,那为什么要复制？(编辑:根据答案,它可能不是;只是在打印时看起来那样.)其次,假设first在Java中的其他东西上操作是可变的,比如一个整数的链表.应该first以懒惰的方式行事(例如,首先创建一个持久的序列)？将它立即评估并保存是否有意义？我认为,这将是一种破坏漂亮抽象的黑客,但能快速完成工作.当你打电话时(seq "abcd"),你不知道它将如何使用.当你打电话给firsta时seq,你知道该怎么做.可是,当你调用first上"abcd",我认为执行一个hacky和快速"抓住并保存它",方法比抓住一个序列然后调用更好first.

我错过了什么吗？Rich Hickey跳过了一些步骤吗？

如果我有疑问,请告诉我.谢谢!

Answer 1

这并不意味着正在制作完整的字符串副本.(但这是一个很好的问题.)

在clojure.lang.RT的源代码中,您会注意到运行时使用charsequence来创建序列:

static ISeq seqFrom(Object coll){
    if(coll instanceof Seqable)
        return ((Seqable) coll).seq();
    else if(coll == null)
        return null;
    else if(coll instanceof Iterable)
        return IteratorSeq.create(((Iterable) coll).iterator());
    else if(coll.getClass().isArray())
        return ArraySeq.createFromObject(coll);
    else if(coll instanceof CharSequence)
        return StringSeq.create((CharSequence) coll);
          .
          .
          .

所以,这是一个java问题,而不是一个clojure问题.我没有检查,但我相当确定CharSequence做了"正确的事情".

Answer 2

其他答案是正确的，但我将利​​用这个机会指出 Clojure 不变性哲学的一个有趣的效果。

因此，它看起来像是一个 O(N) 操作，因为正在制作字符串的完整副本。

与 Clojure 中的其他数据结构一样，字符串是不可变的。（它们是一个特例，是在 JVM 而不是 Clojure 中实现的，但这对于这一点来说并不重要。）

不可变对象的副本是免费的。没错，免费。因为你根本不需要复制。内存中分配的同一对象可以简单地重复使用，因为它保证始终与“复制”时相同。

所以像这样的函数seq 永远不需要实际复制任何东西。它只是直接对传递的任何内容进行操作，并返回一个（可能是惰性的）序列，该序列为您调用的任何内容提供抽象接口seq。

所以，seq总是 O(1)。