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

Question

Сегодня я начал изучать 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 [] 

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

Однако имейте в виду, что структуры данных 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, которые более подходят как для доступа на передней, так и задней панели.

Answer 2

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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