Вопрос о доступе к списку от программиста-новичка

Question

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

Answer 1

Потому что списки имеют линейную структуру.Это канонический рекурсивный тип данных, определяемый как:

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

То есть либо пустой список, либо узел cons, состоящий из элемента и хвоста, который также является списком.

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

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

Сводка : списки - это компьютерная наукаиндукция как рекурсивная структура данных.Это фундаментально, оно вам нужно, но оно не обеспечивает произвольный доступ.

Answer 2

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

Если вам нужен произвольный доступ, вам следует выбрать другой тип данных. Возможно из Data.Array или Data.IntMap.