Clojure, last

[metaclass]

По мотивам: http://tonsky.livejournal.com/266027.html
Часто ли нужно найти последний элемент последовательности?

Впрочем, я не очень понимаю, причем тут полиморфизм к оптимизации last для векторов - по-моему, другое имя для метода работающего O(1) для конкретной реализации (вектор) вместо O(n) для произвольных последовательностей - это вполне разумная идея.

Рассуждать об производительности алгоритма гораздо проще, зная, что вызов всегда отрабатывает за известное время, а не "в зависимости от того, что за реализацию мы туда передали".
По-моему, очевидно, что не нужно делать обобщенную реализацию, например quicksort, передавая ей абстракцию "последовательность"+"функция получения n-ного элемента", потому что единственный вариант, в котором это работает - мутабельный массив с O(1) для доступа и замены элемента. Соответственно и алгоритмы, использующие last обобщать и надеятся на оптимальную реализацию в некотором роде бессмысленно.

Comments

[max630.livejournal.com]

> это никому не нужно
конечно не нужно, можно же просто скопипастить модуль, поменять импорт и написать в хаскель-кафе: пакет XXX теперь поддерживает Text. Ищите в XXX.Text и XXX.Text.Lazy

[vshabanov.livejournal.com]

Не понял. Какой еще модуль скопипастить? И что значит пакет теперь поддерживает Text?

[max630.livejournal.com]

Я хочу сказать, что это работает пока у нас 1 список, который по совместительству строка, 1 Map и 1 Array (для Array впрочем есть класс). А если активно используемых строк - 3 типа, которые требуют явной конвертации, и никакиого общего интерфейса у них нет (если быть точным - есть, но он так далеко в хакадже, что его никто не использует), то любая библиотека работающая сo строками обросла своей копией для каждого из текстов.

При этом различия в реализации этих модулей минимальны, и нет, они не обусловлены тем что там алгоритмы разные.

[vshabanov.livejournal.com]

> А если активно используемых строк - 3 типа, которые требуют явной конвертации, и никакиого общего интерфейса у них нет

Общий интерфейс к ним и не нужен, т.к. уж слишком разное у них назначение. С общим интерфейсом/неявными преобразованиями будут проблемы с производительностью и кодировками.

> то любая библиотека работающая сo строками обросла своей копией для каждого из текстов.

А пример можно? Обычно библиотеки либо работают с одним видом строк, либо имеют внутри какой-нить type class и работают со всеми строками одинаково.

[max630.livejournal.com]

я это видел в attoparsec

[max630.livejournal.com]

собственно, достаточно сравнить исходники Data.Text и Data.Text.Lazy

[vshabanov.livejournal.com]

Собственно, в этих исходниках можно увидеть кучу RULES, которые врядли будут срабатывать и выдавать такой же эффективный код, если код будет на typeclass-ах.

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