Почему Haskell по умолчанию использует строковый список связанных символов?

Тот факт, что реализация Haskell по умолчанию String неэффективна как с точки зрения скорости, так и с памятью, хорошо известна. Насколько мне известно, [] lists в целом реализованы в Haskell как односвязные списки и для большинства небольших/простых типов данных (например, Int), это не очень хорошая идея, но для String это похоже на полный перебор. Некоторые из мнений по этому вопросу включают:

Real World Haskell

В простых тестах, подобных этому, даже программы, написанные на интерпретируемых языках, таких как Python, могут превосходить код Haskell, который использует String на порядок.

Эффективная реализация строк в Haskell

Поскольку String является только [ Char], это связанный список Char, это означает, что Strings имеют плохую локальность ссылки и снова означает, что Strings довольно большие в памяти, как минимум, N * (21 бит + Мбит), где N - длина строки, а M - размер указателя (...). Строки гораздо реже могут быть оптимизированы для циклов и т.д. Компилятором.

Я знаю, что Haskell имеет ByteString (и Array s) в нескольких приятных вкусах и что они могут выполнять работу красиво, но я ожидал бы, что реализация по умолчанию будет самой эффективной.

TL; DR: Почему реализация Haskell по умолчанию String представляет собой односвязный список, хотя он ужасно неэффективен и редко используется для приложений реального мира (за исключением действительно простых)? Есть ли исторические причины? Легче ли реализовать?

Ответы

Ответ 1

Почему реализация Haskell по умолчанию для String представляет собой список, связанный со списком

Поскольку поддержка однопользовательских списков поддерживает:

  • индукция с помощью сопоставления с образцом
  • имеют полезные свойства, такие как Monad, Functor
  • являются корректно параметрически полиморфными
  • естественно ленивы

и поэтому String в качестве [Char] (точки юникода) означает тип строки, который соответствует языковым целям (начиная с 1990 года) и по существу "бесплатно" с библиотекой списков.

Таким образом, исторически разработчикам языка больше интересовали хорошо продуманные основные типы данных, чем современные проблемы обработки текста, поэтому у нас есть элегантный, простой в понимании, простой способ обучения String, который не является " t довольно юникодный текстовый фрагмент и не является плотным, упакованным строгим типом данных.

Ответ 2

Эффективность - это только одна ось для измерения абстракции. Хотя списки довольно неэффективны для операций text-y, они чертовски удобны в том, что существует множество операций с списками, реализованных полиморфно, которые имеют полезные интерпретации, когда они специализируются на [Char], поэтому вы получаете много повторного использования как в реализации библиотеки, так и в пользовательский мозг.

Неясно, был ли язык, который сегодня разрабатывался с нуля с нашим нынешним уровнем опыта, будет принято такое же решение; однако, не всегда возможно принимать решения в совершенстве до того, как станет доступен опыт.

Ответ 3

На данный момент это, вероятно, исторический: оптимизация, которая сделала такие вещи, как ByteString настолько эффективными, в последнее время, тогда как [Char] предшествует их всем годам.