Об исполнении `first` функции Clojure в

Question

я увидел следующий пример в видео Рича на последовательностях http://blip.tv/file/734409 около 33-36 минут в него:

(first "abcd") => \a 

Теперь он говорит, что это расширяется (вроде):

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

Таким образом, это выглядит как O(N) операции, так как полная копия строки делается. Прежде всего, если значение String является неизменным, то почему оно копируется? (Редактирование: на основе ответа, вероятно, это не так, просто выглядели так, когда печатались.) Во-вторых, предположим, что first работает на чем-то другом в Java, который изменен, скажем, связанный список целых чисел. Должно ли first действовать ленивым способом (например, сначала создать постоянную последовательность)? Разве это не имеет смысла оценивать это сразу и сохранять его? Это был бы какой-то хак, который сломал бы хорошую абстракцию, но, я думаю, быстро проделайте эту работу. Когда вы вызываете (seq "abcd"), вы не знаете, как он будет использоваться. Когда вы вызываете first на seq, вы знаете, что делать. Но, когда вы вызываете first на "abcd", я думаю, что выполнение хакерских и быстрых «захватов и сохранения», подход лучше, чем захватить последовательность, а затем позвонить first.

Я что-то упустил? Разве Рик Хики пропустил несколько шагов?

Дайте мне знать, если у меня есть вопросы. Благодаря!

Answer 1

Другие ответы верны, но я воспользуюсь этим шансом, чтобы указать на интересный эффект философии неизменности Clojure.

Таким образом, это выглядит как операция O (N), потому что выполняется полная копия строки.

Строки, как и другие структуры данных в Clojure, неизменяемы. (Это особый случай, который реализуется в JVM, а не в Clojure, но это несущественно.)

Копии неизменяемых объектов: . Правильно, бесплатно.Потому что вам совсем не нужно копировать. Тот же выделенный объект в памяти можно просто использовать повторно, потому что он всегда будет таким же, как когда он был «скопирован».

Так что функция, подобная seqникогда должна фактически что-то копировать. Он просто работает над тем, что передается напрямую, и возвращает (возможно, ленивую) последовательность, которая предоставляет абстрактный интерфейс к тому, что вы назовете seq.

А так, seq всегда O (1).

Answer 2

Из этого не вытекает полная копия строки. (Но это хороший вопрос.)

В источнике для 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); 
      . 
      . 
      . 

Так на самом деле, это ява вопрос, не clojure вопрос. Я не проверял, но я уверен, что CharSequence делает «правильную вещь».

Answer 3

Вы можете посмотреть на seq, как если бы он создавал ленивую последовательность на основе строки.

Это фактически не создает ленивую последовательность, это на самом деле короткие замыкания на Java-реализацию CharSequence, но это деталь реализации.

С точки зрения сложности, first является O(1) на seq, и вы можете создать seq постоянное время от чего-либо итерацию.