Списки Рок

безусловно, самой удобной структурой данных для последовательных данных в Haskell является List

 data [a] = a:[a] | []

списки дают вам cons (1) минусы и соответствие шаблону. Стандартная библиотека, и в этом отношении прелюдия, полна полезных функций списка, которые должны засорять ваш код (foldr,map,filter). Списки - это постоянные, он же чисто функциональный, что очень приятно. Списки Haskell на самом деле не являются" списками", потому что они являются коиндуктивными (другие языки называют эти потоки) так что вещи, как

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

чудесно работать. Бесконечные структуры данных рок.

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

с другой стороны

первая проблема со списками заключается в том, что индексировать в них (!!) занимает Θ (k) время, что раздражает. Кроме того, добавление может быть медленным ++, но ленивая модель оценки Хаскелла означает, что они могут рассматриваться как полностью амортизированные, если они вообще происходят.

вторая проблема со списками заключается в том, что они имеют плохую локальность данных. Реальные процессоры имеют высокие константы, когда объекты в памяти не расположены рядом друг с другом. Так, в C++ std::vector имеет более быстрый "snoc" (размещение объектов в конце), чем любая чистая структура данных связанного списка, о которой я знаю, хотя это не постоянная структура данных, поэтому менее дружелюбная, чем Haskell списки.

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

Последовательности Функциональных

Data.Sequence внутренне основан на деревья палец (я знаю, вы не хотите этого знать), что означает, что у них есть некоторые хорошие свойства

1. чисто функциональной. Data.Sequence это полностью устойчивые данные структура.
2. чертовски быстрый доступ к началу и концу дерева. Θ (1) (амортизируется) для получения первого или последнего элемента или для добавления деревьев. В списках вещей быстрее всего,Data.Sequence на постоянное медленнее.
3. Θ (log n) доступ к середине последовательности. Это включает в себя вставку значений для создания новых последовательностей
4. высокое качество API

С другой стороны, Data.Sequence не делает много для проблемы локализации данных, и работает только для конечных коллекций (это менее лениво, чем списки)

массивы не для слабонервных

массивы являются одной из самых важных структур данных в CS, но они не очень хорошо вписываются в ленивый чистый функциональный мир. Массивы обеспечивают Θ (1) доступ к середине сбора и исключительно хорошие данные о местоположении/постоянных факторах. Но, поскольку они не очень хорошо вписываются в Haskell, они являются болью для использования. Есть на самом деле множество различных типы массивов в текущей стандартной библиотеке. К ним относятся полностью устойчивые массивы, изменяемые массивы для монады ввода-вывода, изменяемые массивы для монады ST и неупакованные версии выше. Для получения дополнительной информации проверьте Haskell wiki

вектор-это" лучший " массив

The Data.Vector пакет обеспечивает всю доброту массива, в более высоком уровне и более чистом API. Если вы действительно знаете, что вы делаете, вы должны использовать их, если вам нужен массив спектакль. Конечно, некоторые предостережения все еще применяются-изменяемый массив, такой как структуры данных, просто не играет хорошо в чистых ленивых языках. Тем не менее, иногда вы хотите, чтобы O(1) производительность, и Data.Vector дает его к вам в годном к употреблению пакете.

у вас есть другие варианты

если вы просто хотите списки с возможностью эффективной вставки в конце, вы можете использовать список разница. Лучший пример списков, ухудшающих производительность, как правило, исходит от [Char] который прелюдия имеет псевдоним как String. Char списки удобны, но, как правило, работают на порядок в 20 раз медленнее, чем строки C, поэтому не стесняйтесь использовать Data.Text или очень быстро Data.ByteString. Я уверен, что есть другие библиотеки, ориентированные на последовательность, о которых я сейчас не думаю.

вывод

90+% времени мне нужна последовательная коллекция в списках Haskell-это правильная структура данных. Списки похожи на итераторы, функции, которые потребляют списки, могут легко быть используется с любой из этих других структур данных с помощью toList функции они оснащены. В лучшем мире прелюдия была бы полностью параметрической относительно того, какой тип контейнера она использует, но в настоящее время [] засоряет стандартную библиотеку. Так что, используя списки (почти) каждый, где, безусловно, хорошо.
Вы можете получить полностью параметрические версии большинства функций списка (и благородно использовать их)

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

в самом деле Data.Traversable определяет API, который является более или менее универсальной на любую вещь "список".

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

---

EDIT: на основе комментариев я понимаю, что никогда не объяснял, Когда использовать Data.Vector vs Data.Sequence. Массивы и векторы обеспечивают чрезвычайно быструю индексацию и операции срезания, но в основном являются переходными (императивными) структурами данных. Чисто функциональный структуры данных, такие как Data.Sequence и [] пусть эффективно производят новая значения из старых значений, как если бы вы изменили старые значения.

  newList oldList = 7 : drop 5 oldList

не изменяет старый список, и он не должен копировать его. Так что даже если oldList невероятно долго, эта "модификация" будет очень быстрой. Точно так же

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

произведет новую последовательность с newValue ибо на месте своего 3000 элемента. Опять же, это не разрушает старую последовательность, это просто создает новый. Но он делает это очень эффективно, принимая O(log(min(k,k-n)) где n-длина последовательности, а k-индекс, который вы изменяете.

вы можете легко сделать это с помощью Vectors и Arrays. Они могут быть изменен но это реальная императивная модификация, и поэтому не может быть сделано в обычном коде Haskell. Это означает операции в Vector пакет, который делает изменения, как snoc и cons должны скопировать весь вектор, так что возьмите O(n) времени. Единственным исключением из этого является то, что вы можете использовать изменяемые версии (Vector.Mutable) внутри ST монады (или IO) и сделать все ваши изменения так же, как и в императивных языках. Когда вы закончите, вы" заморозите " свой вектор, чтобы превратиться в неизменяемую структуру, которую вы хотите использовать с чистым кодом.

я чувствую, что вы должны по умолчанию использовать Data.Sequence если список не подходит. Используйте Data.Vector только если ваш шаблон использования не предполагает внесение многих изменений, или если вам нужна чрезвычайно высокая производительность в монадах ST/IO.

если все это говорить о ST монада оставляет вас в замешательстве: тем больше причин придерживаться чистого быстрого и красивого Data.Sequence.