О выполнении функции `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.lang.RT вы заметите, что среда выполнения использует последовательность символов для создания последовательности:

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, а не закрытый вопрос.Я не проверял, но я вполне уверен, что CharSequence делает "правильную вещь".

Answer 2

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

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

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

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

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

Итак, seq - это всегда O (1).

Answer 3

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

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

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