Clojure, last

[metaclass]

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

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

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

Comments

[bydl0coder.livejournal.com]

Взять редко, а проверить, последний или нет, постоянно.
В обсуждаемом случае авторы (и автор) просто решили показать, какие они дартаньяны и какой у них белый фрак. Имеют право, хуле.

[dair-spb.livejournal.com]

Вот Айсед меня уже заинтересовал руби с рельсами, так я на них даже написал.
Теперь вот вы с кложурой. Чо на ей писать-то?

[blackyblack.livejournal.com]

Наверное, самым разумным было бы сделать набор методов для класса ISeq с наиболее общими реализациями и явно это выделить в неймспейсах. Для конкретных структур данных сделать свои более эффективные варианты и тоже это явно прописать в документации, а лучше сделать что-то типа классов. То, как это сделано сейчас в кложури, пока что вводит программера в заблуждение: где-то применяется только обобщенная версия, где-то полиморфная, а где-то специфическая. Притом по имени функции понять где что невозможно, да и с сигнатурой метода ненамного легче.
Вот, например: http://clojuredocs.org/clojure_core/1.2.0/clojure.core/last и http://clojuredocs.org/clojure_core/1.2.0/clojure.core/peek. Сигнатуры, как видим, идентичны.

[ilya-portnov.livejournal.com]

Кто-то вроде предлагал использовать систему типов для контроля сложности. Ну, например, тип Complexity c m a обозначает действие, выполняемое в монаде m со сложностью c, и возвращающее a. Ну и функции, скажем, forM :: SizedList size a -> (a -> Complexity c m b) -> Complexity (size :*: c) m (SizedList size b).

[vshabanov.livejournal.com]

> Часто ли нужно найти последний элемент последовательности?

Я бы поставил вопрос чуть шире: а нужны ли вообще общие интерфейсы к последовательностям? Зачем last-у работать и со списком и с массивом?

С трудом себе представляю ситуацию, когда вместо списка вдруг потребовался массив или мапка и при этом алгоритм работы не изменился. Т.е. все равно придется перепиливать код и замена last на какой-нить V.last/Map.last не сильно напряжет.

Если же хочется краткости, то уже вылезают проблемы с понятностью кода (везде last, а че делается, с какими структурами данных работаем, непонятно).

В том же самом хаскеле для каждой структуры данных свой отдельный набор ф-ий в отдельном модуле, причем часто с пересекающимися названиями. При этом запросто можно сделать type class с нужными ф-иями и везде писать какой-нить foldl вместо Map.foldl/IntMap.foldl/Text.foldl, но это никому не нужно.

С моей точки зрения всякие обобщенные коллекции/итераторы -- это изврат и переусложнение, возможно вызванное бедностью языков (неудобные/отсутствующие замыкания).

[kkirsanov.livejournal.com]

Кстати про пауков http://www.youtube.com/watch?v=jd_c0JHbflI&feature=player_embedded#!