chapters/11-list.md
# Список
Помните, в одной из предыдущих глав я говорил, что познакомлю вас ещё с несколькими стандартными типами данных в Haskell? Пришло время узнать о списках.
Список (англ. list) — это стандартный тип, характеризующий уже не просто данные, но структуру данных (англ. data structure). Эта структура представляет собой набор данных одного типа, и едва ли хоть одна реальная Haskell-программа может обойтись без списков.
Структуры, содержащие данные одного типа, называют ещё гомогенными (в переводе с греческого: «одного рода»).
Вот список из трёх целых чисел:
```haskell
[1, 2, 3]
```
Квадратные скобки и значения, разделённые запятыми. Вот так выглядит список из двух значений типа `Double`:
```haskell
[1.3, 45.7899]
```
а вот и список из одного-единственного символа:
```haskell
['H']
```
или вот из четырёх строк, отражающих имена протоколов транспортного уровня OSI-модели:
```haskell
["TCP", "UDP", "DCCP", "SCTP"]
```
Если у вас есть опыт разработки на языке C, вы можете подумать, что список похож на массив. Однако, хотя сходства имеются, я намеренно избегаю слова «массив», потому что в Haskell существуют массивы (англ. array), это несколько иная структура данных.
Список — это тоже выражение, поэтому можно легко создать список списков произвольной вложенности. Вот так будет выглядеть список из ряда протоколов трёх уровней OSI-модели:
```haskell
[ ["DHCP", "FTP", "HTTP"]
, ["TCP", "UDP", "DCCP", "SCTP"]
, ["ARP", "NDP", "OSPF"]
]
```
Это список списков строк. Форматирование в отношении квадратных скобок весьма вольное, при желании можно и так написать:
```haskell
[["DHCP", "FTP", "HTTP" ],
["TCP", "UDP", "DCCP", "SCTP"],
["ARP", "NDP", "OSPF" ]]
```
Список может быть и пустым, то есть не содержать в себе никаких данных:
```haskell
[]
```
## Тип списка
Раз список представляет собой структуру, содержащую данные некоторого типа, каков же тип самого списка? Вот:
```haskell
[Int] -- Список целых чисел
[Char] -- Список символов
[String] -- Список строк
```
То есть тип списка так и указывается, в квадратных скобках. Упомянутый ранее список списков строк имеет такой тип:
```haskell
[[String]] -- Список списков строк
```
Модель очень проста:
```haskell
[ [String] ]
│ Тип │
└ данных ┘
│ Тип │
│ списка │
└─ этих данных ─┘
```
Хранить данные разных типов в стандартном списке невозможно. Однако вскоре мы познакомимся с другой стандартной структурой данных, которая позволяет это.
## Действия над списками
Если списки создаются — значит это кому-нибудь нужно. Со списком можно делать очень много всего. В стандартной Haskell-библиотеке существует отдельный модуль `Data.List`, включающий широкий набор функций, работающих со списком. Откроем модуль `Main` и импортируем в него модуль `Data.List`:
```haskell
module Main where
-- Стандартный модуль для работы со списками.
import Data.List
main :: IO ()
main = putStrLn (head ["Vim", "Emacs", "Atom"])
```
Функция `head` возвращает голову списка, то есть его первый элемент. При запуске этой программы на выходе получим:
```bash
Vim
```
Модель такая:
```haskell
["Vim" , "Emacs", "Atom"]
голова └─── хвост ───┘
```
Эдакая гусеница получается: первый элемент — голова, а всё остальное — хвост. Функция `tail` возвращает хвост:
```haskell
main :: IO ()
main = print (tail ["Vim", "Emacs", "Atom"])
```
Вот результат:
```bash
["Emacs", "Atom"]
```
Функция `tail` формирует другой список, представляющий собою всё от первоначального списка, кроме головы. Обратите внимание на новую функцию `print`. В данном случае мы не могли бы использовать нашу знакомую `putStrLn`, ведь она применяется к значению типа `String`, в то время как функция `tail` вернёт нам значение типа `[String]`. Мы ведь помним про строгость компилятора: что ожидаем, то и получить должны. Функция `print` предназначена для «стрингификации» значения: она берёт значение некоторого типа и выводит это значение на консоль уже в виде строки.
Внимательный читатель спросит, каким же образом функция `print` узнаёт, как именно отобразить конкретное значение в виде строки? О, это интереснейшая тема, но она относится к Третьему Киту Haskell, до знакомства с которым нам ещё далеко.
Можно получить длину списка:
```haskell
handleTableRow :: String -> String
handleTableRow row
| length row == 2 = composeTwoOptionsFrom row
| length row == 3 = composeThreeOptionsFrom row
| otherwise = invalidRow row
```
Это чуток видоизменённый кусочек одной моей программы, функция `handleTableRow` обрабатывает строку таблицы. Стандартная функция `length` даёт нам длину списка (число элементов в нём). В данном случае мы узнаём число элементов в строке таблицы `row`, и в зависимости от этой длины применяем к этой строке функцию `composeTwoOptionsFrom` или `composeThreeOptionsFrom`.
Но постойте, а где же тут список? Функция `handleTableRow` применяется к строке и вычисляет строку. А всё дело в том, что строка есть ни что иное, как список символов. То есть тип `String` эквивалентен типу `[Char]`. Скажу более: `String` — это даже не самостоятельный тип, это всего лишь псевдоним для типа `[Char]`, и вот как он задан:
```haskell
type String = [Char]
```
Ключевое слово `type` вводит синоним для уже существующего типа (англ. type synonym). Иногда его называют «псевдонимом типа». Читается это так:
```haskell
type String = [Char]
тип этот равен тому
```
Таким образом, объявление функции `handleTableRow` можно было бы переписать так:
```haskell
handleTableRow :: [Char] -> [Char]
```
При работе со списками мы можем использовать уже знакомые промежуточные выражения, например:
```haskell
handleTableRow :: String -> String
handleTableRow row
| size == 2 = composeTwoOptionsFrom row
| size == 3 = composeThreeOptionsFrom row
| otherwise = invalidRow row
where size = length row
```
А можно и так:
```haskell
handleTableRow :: String -> String
handleTableRow row
| twoOptions = composeTwoOptionsFrom row
| threeOptions = composeThreeOptionsFrom row
| otherwise = invalidRow row
where
size = length row -- Узнаём длину
twoOptions = size == 2 -- ... сравниваем
threeOptions = size == 3 -- ... и ещё раз
```
Здесь выражения `twoOptions` и `threeOptions` имеют уже знакомый нам стандартный тип `Bool`, ведь они равны результату сравнения значения `size` с числом.
## Неизменность списка
Как вы уже знаете, все данные в Haskell неизменны, как Египетские пирамиды. Списки — не исключение: мы не можем изменить существующий список, мы можем лишь создать на его основе новый список. Например:
```haskell
addTo :: String -> [String] -> [String]
addTo newHost hosts = newHost : hosts
main :: IO ()
main = print ("124.67.54.90" `addTo` hosts)
where hosts = ["45.67.78.89", "123.45.65.54"]
```
Результат этой программы таков:
```bash
["124.67.54.90","45.67.78.89","123.45.65.54"]
```
Рассмотрим определение функции `addTo`:
```haskell
addTo newHost hosts = newHost : hosts
```
Стандартный оператор `:` добавляет значение, являющееся левым операндом, в начало списка, являющегося правым операндом. Читается это так:
```haskell
newHost : hosts
этот
оператор
берёт
это
значение
и добавляет
его в начало
этого списка
```
Естественно, тип значения слева обязан совпадать с типом значений, содержащихся в списке справа.
С концептуальной точки зрения функция `addTo` добавила новый IP-адрес в начало списка `hosts`. В действительности же никакого добавления не произошло, ибо списки неизменны. Оператор `:` взял значение `newHost` и список `hosts` и создал на их основе новый список, содержащий в себе уже три IP-адреса вместо двух.
## Перечисление
Допустим, понадобился нам список целых чисел от одного до десяти. Пишем:
```haskell
main :: IO ()
main = print tenNumbers
where tenNumbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
```
Неплохо, но избыточно, ведь чисел могло быть и сто, и тысяча. Есть лучший путь:
```haskell
main :: IO ()
main = print tenNumbers
where tenNumbers = [1..10]
```
Красиво, не правда ли? Выражение в квадратных скобках называется перечислением (англ. enumeration или сокращённо enum). Иногда её именуют также арифметической последовательностью. Идея предельно проста: зачем указывать содержимое списка целиком в той ситуации, когда можно указать лишь диапазон значений? Это мы и сделали:
```haskell
[1..10] = [1,2,3,4,5,6,7,8,9,10]
```
Значение слева от `..` — это начало диапазона, а значение справа — его конец. Компилятор сам догадается, что шаг между числами в данной последовательности равен 1. Вот ещё пример:
```haskell
[3..17] = [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]
_ _
== ==
```
Мы можем задать шаг и явно:
```haskell
[2,4..10] = [2,4,6,8,10]
```
Получили только чётные значения. Схема проста:
```haskell
[2, 4 .. 10]
первый конец
второй
│ разница │
└─ даёт шаг ─┘
```
Вот ещё пример:
```haskell
[3,9..28] = [3,9,15,21,27]
```
Можно задать и нисходящий диапазон:
```haskell
[9,8..1] = [9,8,7,6,5,4,3,2,1]
```
Или так:
```haskell
[-9, -8.. -1] = [-9,-8,-7,-6,-5,-4,-3,-2,-1]
```
Да, отрицательные числа тоже работают. Можно взять также и числа с плавающей точкой:
```haskell
[1.02,1.04..1.16] = [1.02,1.04,1.06,1.08,1.1,1.12,1.14,1.16]
```
В общем, идея ясна. Но что это мы всё с числами да с числами! Возьмём символы:
```haskell
['a'..'z'] = "abcdefghijklmnopqrstuvwxyz"
```
Диапазон от `'a'` до `'z'` — получили английский алфавит в виде `[Char]` или, как мы уже знаем, просто `String`. При большом желании явно задать шаг можно и здесь:
```haskell
['a','c'..'z'] = "acegikmoqsuwy"
```
Вот такая красота.
Теперь, после знакомства со списком, мы будем использовать их постоянно.
## Для любопытных
В разделе про диапазоны для списка мы оперировали значениями типа `Int`, `Double` и `Char`. Возникает вопрос: а можно ли использовать значения каких-нибудь других типов? Отвечаю: можно, но с оговоркой. Попробуем проделать это со строкой:
```haskell
main :: IO ()
main = print ["a","aa".."aaaaaa"] -- Ну-ну...
```
При попытке скомпилировать такой код увидим ошибку:
```bash
No instance for (Enum [Char])
arising from the arithmetic sequence ‘"a", "aa" .. "aaaaaa"’
```
И удивляться тут нечему: шаг между строками абсурден, и компилятор в замешательстве. Не все типы подходят для перечислений в силу своей природы, однако в будущем, когда мы научимся создавать наши собственные типы, мы узнаем, что их вполне можно использовать в диапазонах. Наберитесь терпения.
Приоткрою секрет: этот странный пример с шагом между строками теоретически можно-таки заставить работать, но о том, как это сделать, мы узнаем во время знакомства с Третьим Китом Haskell.