Почему мгновенно добавляется список?

Я иду через Haskell учебник о списках, и он утверждает:Почему мгновенно добавляется список?

упускает при повторном использовании оператора ++ на длинных строках ... Haskell должен пройти через весь список на левой стороне ++. ... Однако размещение чего-то в начале списка с использованием оператора: (также называемого оператором cons) мгновенно.

Но, на мой взгляд, все должно быть наоборот.

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

Любая помощь в понимании этого утверждения?

источник

2015-11-13 Sung Won Cho

Похоже, вы просто смешиваете массивы со списками. – 31eee384

Это может быть реализовано с помощью связанного списка, не удерживая указатель до конца. – usr2564301

Список в Haskell - это всего лишь отдельный список. Список, скажем, Char, либо [], либо пустой список, либо c : cs, где c - это Char и cs - это список Char. Для получения c : cs, приведенного c и cs, все, что необходимо выполнить, это выделить запись с тегом, указывающим (:), и копиями указателей c и cs. Это очень дешево.

источник

2015-11-13 23:27:53 dfeuer

Так что я догадался, правильно :) Любая ссылка для этого? Может ли это считаться «частью Haskell», или могут быть реализованы в противном случае? – usr2564301

@Jongware Я полагаю, что если вы догадались, что связанные списки реализованы с использованием связанных списков, вы догадались, что правильно. Я был бы удивлен, если бы реализация использовала нечто, отличное от связанного списка, для реализации связанного списка. –

@ DanielLyons: но я не знаю Haskell, и вопрос не вызывает их * связанных * списков. Списки могут быть реализованы различными способами - и все они будут немного отличаться от операций, описанных в OP. Из наблюдаемого поведения я понял, что списки должны быть реализованы как связанные списки. – usr2564301

Почему мгновенно добавляется список?

ответ

Смежные вопросы