Haskell "коллекции" языковой дизайн

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

Например, я знаю, что Data.Sequence является более эффективным с большей частью операций с списками (кроме операции cons) и используется много; синтаксически, однако, он "вряд ли поддерживается". Haskell приложил много усилий к функциональным абстракциям, таким как класс Functor и Foldable, но их синтаксис несовместим с их списком по умолчанию.

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

Итак, я думаю, что мое удивление можно сделать конкретным в таких вопросах, как:

Почему тип map не равен (Functor f) => (a -> b) -> f a -> f b?
Почему функции [] и (:) не могут использоваться, например, для типа Data.Sequence?

Я действительно надеюсь, что для этого есть какое-то объяснение, которое не включает слова "обратная совместимость" или "это просто так росло", хотя, если вы считаете, что этого не происходит, сообщите мне. Любые соответствующие языковые расширения также приветствуются.

Ответ 1

Прежде чем вникать в почему, вот резюме проблемы и что вы можете с этим поделать. Конструкторы [] и (:) зарезервированы для списков и не могут быть переопределены. Если вы планируете использовать один и тот же код с несколькими типами данных, определите или выберите класс типа, представляющий интерфейс, который вы хотите поддерживать, и используйте методы из этого класса. Вот некоторые обобщенные функции, которые работают как по спискам, так и по последовательностям. Я не знаю об обобщении (:), но вы можете написать свой собственный.

fmap вместо map
mempty вместо []
mappend вместо (++)

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

-- For now, use lists
type List a = [a]
nil = []
cons x xs = x : xs

{- Switch to Seq in the future
-- type List a = Seq a
-- nil = empty
-- cons x xs = x <| xs
-}

Обратите внимание, что [] и (:) являются конструкторами: вы также можете использовать их для сопоставления шаблонов. Согласование шаблонов относится к одному конструктору типа, поэтому вы не можете расширять шаблон для работы с новым типом данных без перезаписи кода сопоставления шаблонов.

Почему в Haskell очень много элементов списка

Списки обычно используются для представления последовательных вычислений, а не данных. На императивном языке вы можете создать набор с циклом, который создает элементы и вставляет их в набор по одному. В Haskell вы делаете то же самое, создавая список, а затем передавая список в Set.fromList. Поскольку списки так близко соответствуют этой абстракции вычислений, у них есть место, которое вряд ли когда-либо будет заменено другой структурой данных.

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

Существует несколько классов, которые являются полезными обобщениями списков:

Functor поставляет fmap, обобщение map.
Моноид предоставляет методы, полезные для коллекций со структурой списка. Пустой список [] обобщается на другие контейнеры с помощью mempty, а конкатенация списка (++) обобщается на другие контейнеры на mappend.
Applicative и Monad, которые полезны для интерпретации коллекций как вычислений.
Traversable и Складные поставляют полезные методы для выполнения вычислений по коллекциям.

Из них только Functor и Monad находились в влиятельной спецификации Haskell 98, поэтому другие в библиотеках часто игнорировались в зависимости от того, когда была написана библиотека и насколько активно она поддерживалась. Основные библиотеки хорошо поддерживают новые интерфейсы.

Ответ 2

Я помню, как где-то читал, что map для списков по умолчанию, так как новички в Haskell будут отложены, если они совершили ошибку и увидели сложную ошибку о "Фунтерах", о которой они понятия не имеют. Поэтому они имеют как map, так и fmap вместо map.

РЕДАКТИРОВАТЬ: "где-то" - это проблема чтения моноды 13, стр. 20, сноска 3:

3Вы можете спросить, почему нам нужна отдельная функция отображения. Почему бы просто не покончить с текущим отображение только списка, а вместо этого переименовать fmap? Ну, это хороший вопрос. обычный аргумент состоит в том, что кто-то, просто изучая Haskell, неправильно использует карту, скорее посмотрите ошибку о списках, чем о функторах.

Для (:) функция (<|) кажется заменой. Я понятия не имею о [].

Ответ 3

A nitpick, Data.Sequence не более эффективен для "операций с списками", он более эффективен для операций последовательности. Тем не менее, многие функции в Data.List - это действительно операции последовательности. Дерево пальцев внутри Data.Sequence должно сделать немного больше работы для cons (< |), эквивалентного списку (:), а его представление памяти также несколько больше, чем список, поскольку он сделан из двух типов данных a FingerTree и Deep.

Дополнительный синтаксис для списков в порядке, он попадает в сладкое пятно в том, что списки хороши - минусы (:) и сопоставление образцов слева. Независимо от того, нужны ли последовательности в дополнительном синтаксисе, дальнейшая дискуссия, но поскольку вы можете получить очень длинный путь со списками, а списки по сути просты, наличие хорошего синтаксиса является обязательным.

Список не является идеальным представлением для строк - макет памяти неэффективен, так как каждый Char обернут конструктором. Вот почему ByteStrings были введены. Хотя они выложены как массив ByteStrings, необходимо выполнить небольшую административную работу - [Char] все еще может быть конкурентоспособным, если вы используете короткие строки. В GHC существуют языковые расширения, чтобы дать ByteStrings более строковый синтаксис.

Другой основной ленивый функционал Clean всегда представлял строки как массивы байтов, но его система типов сделала это более практичным - я полагаю, что библиотека ByteString использует небезопасныйPerfomIO под капотом.

Ответ 4

С версией 7.8 ghc поддерживает перегрузку литералов, сравнивает руководство. Например, с учетом соответствующих экземпляров IsList вы можете написать

['0' .. '9']             :: Set Char
[1 .. 10]                :: Vector Int
[("default",0), (k1,v1)] :: Map String Int
['a' .. 'z']             :: Text

(цитируется в документации).

Ответ 5

Я уверен, что это не будет ответом на ваш вопрос, но все же.

Я хочу, чтобы у Haskell были более либеральные имена функций (mixfix!) a la Agda. Тогда синтаксис конструкторов списков (:, []) не был бы волшебным; позволяя нам как минимум скрыть тип списка и использовать те же токены для наших собственных типов.

Количество изменений кода при миграции между списком и пользовательскими типами последовательностей будет минимальным.

О map, вам немного повезло. Вы всегда можете скрыть карту и установить ее равной fmap самостоятельно.

import Prelude hiding(map)

map :: (Functor f) => (a -> b) -> f a -> f b
map = fmap

Прелюдия велик, но это не лучшая часть Haskell.