Списковый тип данных представляет из себя простое перечисление значений,
элементов списка. Например, ["b", "a", "c"]. Удобно отдельно рассматривать
пустой список, то есть список без значений, обозначаемый, например, как []
или nil.
Формирование списка выглядит как постепенное прибавление новых элементов к уже
существующему списку. Операцию добавление элемента к списку обычно обозначают
символом :: или cons. Левый операнд операции это новый элемент, а правый --
список, к которому его добавляют. Например, "d" :: l или cons "d" l. Список
из одного элемента можно получить из пустого списка, прибавив к нему данный
элемент: "c" :: [], получим ["c"]. Список из двух элементов можно получить
из списка из одного элемента или, даже, из пустого списка, например,
"a" :: ["c"] или "a" :: "c" :: []. Таким образом, имея набор значений, можно
получить список из этих значений путём постепенного прибавления к нему этих
значений. Например, наш первый пример списка может быть получен так:
"b" :: "a" :: "c" :: []. По сути, форма представления списка ["b", "a", "c"]
это просто синтаксический сахар для списков.
Структурно в списке выделяют голову и хвост. Голова списка это его первый
элемент, элемент списка, к которому легче всего получить доступ. Хвост списка
это та же последовательность за исключением её первого элемента. Для получения
головы списка реализуется операция head, для получения хвоста tail.
Длиной списка называют количество его элементов. Операцию получения длины
обычно обозначают length. Реализовать получение длины списка можно легко с
помощью рекурсии. Очевидно, что длина пустого списка ноль. Длина же
произвольного списка это длина его хвоста плюс 1. Вот пример на языке Elm:
length xs =
if xs == []
then 0
else 1 + length (tail xs)Новые списки можно получать объединением двух списков. Эту операцию обычно
обозначают символом ++ или concat. Объединение легко реализовать через
рекурсию. Очевидно, что объединение пустого списка с любым другим даст тот же
самый список. Объединение же непустых списков можно совершить посредством
следующий тривиальных действий: выделить голову первого списка, объединить
хвост первого списка со вторым списком, прибавить голову к получившемуся списку.
Вот пример реализации на языке Elm:
concat xs ys =
if xs == []
then ys
else (head xs) :: (concat (tail xs) ys)В отличие от массивов у списков отсутствует операция прямого получения его элемента по индексу (номеру). Однако эту операцию легко реализовать посредством рекурсии.
nth xs n =
if n == 0
then head xs
else nth (tail xs) (n - 1)(Для пустого списка операция не имеет смысла, также как не имеет смысла для списков с меньшим числом элементов чем требуется для данного индекса. Пример кода выше это не учитывает.)
Приведённые выше примеры показывают как можно обрабатывать списки. Вот ещё пара простых примеров.
Пусть дан список чисел. Нужно посчитать сумму его элементов. Положим, что сумма значений пустого списка равна нулю. Сумма же элементов непустого списка очевидно считается как сумма головы списка и суммы его хвоста. Запишем это на языке Elm.
sum xs =
if xs == []
then 0
else (head xs) + (sum (tail xs))Другой пример. Пусть дан список булевых значений. Нужно получит список инвертированных значений исходного списка. Положим для пустого списка ответом пустой список. Для непустого списка ответ будет состоять из инвертированной головы исходного списка и инвертированного его хвоста. Код на языке Elm:
inv xs =
if xs == []
then []
else (not (head xs)) :: (inv (tail xs))Приведённые выше примеры являются частными случаями операций reduce и map, которые будут рассмотрены отдельно.
© Евгений А. Симоненко, 2017