Списки в Haskell: тип данных или абстрактный тип данных? - PullRequest
14 голосов
/ 21 декабря 2009

Насколько я понимаю, тип списка в Haskell реализован внутри, используя связанный список. Однако пользователь языка не может видеть детали реализации, а также не имеет возможности изменять «ссылки», составляющие связанный список, чтобы он мог указывать на другой адрес памяти. Полагаю, это делается внутренне.

Как тогда можно определить тип списка, как в Haskell? Это «тип данных» или «абстрактный тип данных»? А что за тип связанного списка реализации?

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

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

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

Ответы [ 6 ]

10 голосов
/ 21 декабря 2009

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

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

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

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

8 голосов
/ 21 декабря 2009

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

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

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

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

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

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

5 голосов
/ 22 декабря 2009

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

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

  • «Абстрактный тип» не имеет видимых конструкторов значений, поэтому вы не можете сопоставить шаблон с значениями типа.

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

4 голосов
/ 21 декабря 2009

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

3 голосов
/ 21 декабря 2009

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

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

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

НТН

1 голос
/ 22 декабря 2009

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

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

...