Списки в Haskell: тип данных или абстрактный тип данных?

Из того, что я понимаю, тип списка в Haskell реализован внутренне с использованием связанного списка. Однако пользователь языка не видит деталей реализации и не имеет возможности изменять "ссылки", составляющие связанный список, чтобы он мог указывать на другой адрес памяти. Это, я полагаю, сделано внутренне.

Как тогда, может ли тип списка быть квалифицированным как в Haskell? Является ли это "типом данных" или "абстрактным типом данных"? А что из типа связанного списка реализации?

Кроме того, поскольку тип списка, предоставляемый прелюей, не является типом связанного списка, как можно реализовать основные функции связанных списков?

Возьмем, к примеру, эту часть кода, предназначенную для добавления элемента a в индекс n списка:

add [] acc _ _ = reverse acc
add (x:xs) acc 0 a = add xs (x:a:acc) (-1) a 
add (x:xs) acc n a = add xs (x:acc) (n-1) a

Используя "реальный" связанный список, добавление элемента будет состоять только в изменении указателя на адрес памяти. Это невозможно в Haskell (или это?), Поэтому вопрос: является ли моя реализация добавлением элемента в список наилучшим, или я чего-то не хватает (использование функции reverse есть, я думаю, особенно уродливые, но можно ли обойтись без?)

Пожалуйста, не стесняйтесь корректировать меня, если что-либо, что я сказал, неправильно, и спасибо за ваше время.

Ответы

Ответ 1

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

Вы можете определить эту функцию наиболее просто следующим образом:

add ls idx el = take idx ls ++ el : drop idx ls

Список el : drop idx ls повторно использует хвост исходного списка, поэтому вам нужно только создать новый список до idx (что делает функция take). Если вы хотите сделать это с помощью явной рекурсии, вы можете определить ее так:

add ls 0 el   = el : ls
add (x:xs) idx el
  | idx < 0   = error "Negative index for add"
  | otherwise = x : add xs (idx - 1) el
add [] _ el   = [el]

Это повторяет хвост списка таким же образом (что el : ls в первом случае).

Поскольку у вас, похоже, не получается увидеть, как это связанный список, дайте понять, что такое связанный список: это структура данных, состоящая из ячеек, где каждая ячейка имеет значение и ссылку на следующий элемент. В C он может быть определен как:

struct ListCell {
void *value; /* This is the head */
struct ListCell *next; /* This is the tail */
}

В Lisp он определяется как (head . tail), где head - это значение, а tail - ссылка на следующий элемент.

В Haskell он определяется как data [] a = [] | a : [a], где a - это значение, а [a] - ссылка на следующий элемент.

Как вы можете видеть, эти структуры данных эквивалентны. Единственное отличие состоит в том, что в C и Lisp, которые не являются чисто функциональными, значения головы и хвоста - это вещи, которые вы можете изменить. В Haskell вы не можете их изменить.

Ответ 2

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

Списки не являются абстрактными типами, это просто связанный список.

Вы можете думать о них так:

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

который является именно тем, как определен связанный список. Элемент head и (указатель на) остальных.

Обратите внимание, что это не является внутренним. Если вы хотите иметь более эффективные типы, используйте Sequence или Array. (Но поскольку никаких изменений не разрешено, вам не нужно фактически копировать списки, чтобы различать копии, что может быть усилением производительности, а не императивными языками).

Ответ 3

В Haskell "тип данных" и "абстрактный тип" - это термины:

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

Учитывая тип a, [a] (список a) - это тип данных, потому что вы можете сопоставлять шаблоны с видимыми конструкторами cons (записано :) и nil (написано []). Примером абстрактного типа будет IO a, который вы не можете деконструировать по шаблону.

Ответ 4

Ваш код может работать, но он определенно не оптимален. Возьмите случай, когда вы хотите вставить элемент в индекс 0. Пример:

add [200, 300, 400] [] 0 100

Если вы выполните вывод для этого, вы получите:

add [200, 300, 400] [] 0 100
add [300, 400] (200:100:[]) (-1) 100 
add [400] (300:[200, 100]) (-2) 300 
add [] (400:[300, 200, 100]) (-3) 400 
reverse [400, 300, 200, 100]
[100, 200, 300, 400]

Но мы добавляем только элемент в начало списка! Такая операция проста! Он (:)

add [200, 300, 400] [] 0 100
100:[200, 300, 400]
[100, 200, 300, 400]

Подумайте, сколько из списка действительно нужно обратить вспять.

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

Ответ 5

Re: добавив элемент в конец списка, я бы предложил использовать оператор (++) и splitAt:

add xs a n = beg ++ (a : end)
  where
    (beg, end) = splitAt n xs

List является связанным списком, но он доступен только для чтения. Вы не можете изменить List на месте - вместо этого вы создаете новую структуру List, в которой есть нужные элементы. Я не читал его, но эта книга, вероятно, попадает в ваш основной вопрос.

НТН

Ответ 6

Компилятор может выбрать любое внутреннее представление, которое он хочет для списка. И на практике это действительно меняется. Очевидно, что список "[1..]" не реализован как классическая серия cons-ячеек.

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