Clojure, last
Aug. 16th, 2012 12:21 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
metaclassПо мотивам: http://tonsky.livejournal.com/266027.html
Часто ли нужно найти последний элемент последовательности?
Впрочем, я не очень понимаю, причем тут полиморфизм к оптимизации last для векторов - по-моему, другое имя для метода работающего O(1) для конкретной реализации (вектор) вместо O(n) для произвольных последовательностей - это вполне разумная идея.
Рассуждать об производительности алгоритма гораздо проще, зная, что вызов всегда отрабатывает за известное время, а не "в зависимости от того, что за реализацию мы туда передали".
По-моему, очевидно, что не нужно делать обобщенную реализацию, например quicksort, передавая ей абстракцию "последовательность"+"функция получения n-ного элемента", потому что единственный вариант, в котором это работает - мутабельный массив с O(1) для доступа и замены элемента. Соответственно и алгоритмы, использующие last обобщать и надеятся на оптимальную реализацию в некотором роде бессмысленно.
Часто ли нужно найти последний элемент последовательности?
Впрочем, я не очень понимаю, причем тут полиморфизм к оптимизации last для векторов - по-моему, другое имя для метода работающего O(1) для конкретной реализации (вектор) вместо O(n) для произвольных последовательностей - это вполне разумная идея.
Рассуждать об производительности алгоритма гораздо проще, зная, что вызов всегда отрабатывает за известное время, а не "в зависимости от того, что за реализацию мы туда передали".
По-моему, очевидно, что не нужно делать обобщенную реализацию, например quicksort, передавая ей абстракцию "последовательность"+"функция получения n-ного элемента", потому что единственный вариант, в котором это работает - мутабельный массив с O(1) для доступа и замены элемента. Соответственно и алгоритмы, использующие last обобщать и надеятся на оптимальную реализацию в некотором роде бессмысленно.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-08-15 10:17 pm (UTC)В обсуждаемом случае авторы (и автор) просто решили показать, какие они дартаньяны и какой у них белый фрак. Имеют право, хуле.
no subject
Date: 2012-08-15 10:36 pm (UTC)Это совершенно другая функция, next.
no subject
Date: 2012-08-15 11:17 pm (UTC)Теперь вот вы с кложурой. Чо на ей писать-то?
no subject
Date: 2012-08-15 11:24 pm (UTC)no subject
Date: 2012-08-15 11:25 pm (UTC)no subject
Date: 2012-08-15 11:34 pm (UTC)no subject
Date: 2012-08-16 05:01 am (UTC)no subject
Date: 2012-08-16 05:48 am (UTC)no subject
Date: 2012-08-16 05:56 am (UTC)no subject
Date: 2012-08-16 06:08 am (UTC)no subject
Date: 2012-08-16 04:59 am (UTC)Вот, например: http://clojuredocs.org/clojure_core/1.2.0/clojure.core/last и http://clojuredocs.org/clojure_core/1.2.0/clojure.core/peek. Сигнатуры, как видим, идентичны.
no subject
Date: 2012-08-16 06:13 am (UTC)no subject
Date: 2012-08-16 11:49 am (UTC)Я бы поставил вопрос чуть шире: а нужны ли вообще общие интерфейсы к последовательностям? Зачем last-у работать и со списком и с массивом?
С трудом себе представляю ситуацию, когда вместо списка вдруг потребовался массив или мапка и при этом алгоритм работы не изменился. Т.е. все равно придется перепиливать код и замена last на какой-нить V.last/Map.last не сильно напряжет.
Если же хочется краткости, то уже вылезают проблемы с понятностью кода (везде last, а че делается, с какими структурами данных работаем, непонятно).
В том же самом хаскеле для каждой структуры данных свой отдельный набор ф-ий в отдельном модуле, причем часто с пересекающимися названиями. При этом запросто можно сделать type class с нужными ф-иями и везде писать какой-нить foldl вместо Map.foldl/IntMap.foldl/Text.foldl, но это никому не нужно.
С моей точки зрения всякие обобщенные коллекции/итераторы -- это изврат и переусложнение, возможно вызванное бедностью языков (неудобные/отсутствующие замыкания).
no subject
Date: 2012-08-16 12:02 pm (UTC)no subject
Date: 2012-08-16 12:33 pm (UTC)конечно не нужно, можно же просто скопипастить модуль, поменять импорт и написать в хаскель-кафе: пакет XXX теперь поддерживает Text. Ищите в XXX.Text и XXX.Text.Lazy
no subject
Date: 2012-08-16 01:50 pm (UTC)no subject
Date: 2012-08-16 06:35 pm (UTC)При этом различия в реализации этих модулей минимальны, и нет, они не обусловлены тем что там алгоритмы разные.
no subject
Date: 2012-08-16 07:39 pm (UTC)Общий интерфейс к ним и не нужен, т.к. уж слишком разное у них назначение. С общим интерфейсом/неявными преобразованиями будут проблемы с производительностью и кодировками.
> то любая библиотека работающая сo строками обросла своей копией для каждого из текстов.
А пример можно? Обычно библиотеки либо работают с одним видом строк, либо имеют внутри какой-нить type class и работают со всеми строками одинаково.
no subject
Date: 2012-08-16 09:11 pm (UTC)no subject
Date: 2012-08-16 09:16 pm (UTC)no subject
Date: 2012-08-17 11:44 am (UTC)attoparsec и text -- одни из наиболее скоростных библиотек на хаскеле. Краткость в них принесена в жертву производительности (не думаю, кстати, что можно добиться такой же производительности где бы то ни было с сохранением абстрактных интерфейсов коллекций и итераторов).
no subject
Date: 2012-08-16 12:04 pm (UTC)