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

Question

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

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

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

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

Возьмите, например, эту часть кода, разработанного для добавления элемента в индексе 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 функция, я думаю, особенно уродливый, но действительно ли возможно обойтись без?)

Не смущайтесь исправлять меня, если что-нибудь, что я сказал, неправильно, и спасибо в течение Вашего времени.

14

list haskell linked-list types abstract-data-type

задан CharlieP 21 December 2009 в 19:51

6 ответов

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

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

Вы можете думать о них, определенными таким образом:

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

что в точности соответствует тому, как связаны список определен - элемент заголовка и (указатель на) остальное.

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

8

ответ дан 1 December 2019 в 08:52

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

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

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

HTH

3

ответ дан 1 December 2019 в 08:52

Ваш код может работать, но он определенно не оптимален. Возьмем случай, когда вы хотите вставить элемент с индексом 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 неизменяемы, никто (даже среда выполнения) не изменяет указатели в связанном списке. Вот почему, например, дешево добавить элемент в начало списка, но дорого добавить элемент в конец списка. Когда вы добавляете элемент в начало списка, вы можете повторно использовать весь существующий список. Но когда вы добавляете элемент в конец, он должен создать совершенно новый связанный список. Неизменность данных требуется для того, чтобы операции в начале списка были дешевыми.

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

4

ответ дан 1 December 2019 в 08:52

В Хаскелле "тип данных" и "абстрактный тип" являются терминами искусства:

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

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

.

5

ответ дан 1 December 2019 в 08:52

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

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

.

1

ответ дан 1 December 2019 в 08:52

Другие вопросы по тегам:

list haskell linked-list types abstract-data-type

Похожие вопросы:

score 10 · Accepted Answer

Вы путаете изменчивость со структурой данных . Это правильный список, но его нельзя изменять. 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 это определено как (голова. Хвост) , где голова - это значение, а хвост - ссылка на следующий элемент.

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

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