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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ХТН

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

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