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