Haskell: доступ к спискам со спины

Question

Сегодня я начал изучать Haskell. Я немного знаком с функциональными языками, и мне очень нравится Haskell.

Однако у меня возник вопрос о его дизайне, который меня беспокоит: из того, что я понял до сих пор, похоже, что доступ к элементу в конце списка намного сложнее, чем доступ к элементу спереди (что-то как xs:x, где xs::[a] и x::a не представляется возможным).

(из того, что я понял), можно добавить список к другому (xs++[a]), но это будет стоить дороже во время выполнения (требуется обход всего списка), и его нельзя использовать для сопоставления с образцом .

Почему Haskell пропускает такую ​​операцию?

Answer 1

Тип данных списка

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

определяется как выше. Есть только два образца, которые вы можете сопоставить: [] и x : xs, где x - голова, а xs - хвост.

Добавление к списку

a = 1 : 2 : []
b = 0 : a

 (:) <-- b
 / \  
0  (:)  <-- a
   / \
  1  (:)
     / \
    2   []

просто добавляет новую ячейку cons и повторно использует исходный список как хвост.

Однако имейте в виду, что структуры данных Haskell являются неизменяемыми. Дополнение к концу списка

a = 1 : 2 : []
b = a ++ [3]

 (:) <-- a      (:) <-- b
 / \            / \
1  (:)         1  (:)
   / \            / \
  2   []         2  (:)
                    / \
                   3   []

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

На самом деле, рассмотрим

a = 0 : a
b = 0 : [ x+1 | x <- b ]

 (:) <-- a         (:) <-- b
 / \               / \
0  (:) <-- a      0  (:) <-- [ x+1 | x <- b ]
   / \               / \
  0  (:) <-- a      1  (:) <-- [ x+1 | x <- [ x+1 | x <- b ] ]
     ...               ...

Как бы вы получили последний элемент списка или добавили в конец?

Существуют и другие структуры данных, такие как dequeue s, которые больше подходят как для фронтального, так и для заднего доступа.

Answer 2

Тип данных списка в Haskell является связанным списком, поэтому поиск использует время O (n).Если вам нужен частый доступ к концу списка, вы можете взглянуть на Data.Sequence , в котором O (1) добавляет начало и конец.

Чтобы ответить, почему Haskellиспользует эту структуру данных в качестве «стандартного контейнера» (например, C и массивов), потому что Haskell является чисто функциональным языком и поэтому предпочитает чисто функциональные структуры данных (неизменяемые и постоянные). Для дальнейшего чтения смотрите эта вики-страница .Для использования нефункциональных структур данных в Haskell потребуется, чтобы он находился внутри монады IO или ST.

Answer 3

Это проблема чистой структуры данных List, а не самого haskell. Вы можете прочитать статью Purely Functional Data Structures , чтобы узнать больше о других чистых структурах данных, которые могут иметь лучшую производительность при таких операциях

Answer 4

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

Answer 5

Это не проблемы с языком, а только тип данных List, который имеет какой-то особый синтаксис, но в остальном не является «неотъемлемой частью Haskell».У вас та же проблема в C с односвязными списками, но, очевидно, это не проблема языка программирования C.

Если вам нужен двусвязный список с указателем хвоста, тогда создайте такой тип данных и используйте его!Возможно, вы захотите узнать больше типов данных (см. Примеры Containers , vector и dlist ).