# Глава 9. Список Помните, в одной из предыдущих глав я говорил, что познакомлю вас ещё с несколькими стандартными типами данных в 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 [] ``` Для доступа к элементу списка по индексу используется оператор `!!`. Так выглядит доступ к элементу `'D'` списка: ```haskell ['U', 'D', 'P'] !! 1 ``` ``` 'D' ``` В теле функции `main` примените функцию `print` к списку списков `l` так, чтобы в консоль вывелся элемент `"DCCP"`. {.task_text} Для этого используйте обращение по индексу. {.task_text} ```haskell {.task_source #haskell_chapter_0090_task_0010} module Main where main :: IO () main = -- Your code here where l = [["DHCP", "FTP", "HTTP" ], ["TCP", "UDP", "DCCP", "SCTP"], ["ARP", "NDP", "OSPF" ]] ``` `l` является списком списков. Соответственно для обращения к списку `["TCP", "UDP", "DCCP", "SCTP"]`, содержащему искомый элемент, требуется индекс 1. А для обращения к элементу `"DCCP"` внутри этого списка требуется индекс 2. {.task_hint} ```haskell {.task_answer} module Main where main :: IO () main = print (l !! 1 !! 2) where l = [["DHCP", "FTP", "HTTP" ], ["TCP", "UDP", "DCCP", "SCTP"], ["ARP", "NDP", "OSPF" ]] ``` ## Тип списка Раз список представляет собой структуру, содержащую данные некоторого типа, каков же тип самого списка? Вот: ```haskell [Int] -- Список целых чисел [Char] -- Список символов [String] -- Список строк ``` То есть тип списка так и указывается, в квадратных скобках. Упомянутый ранее список списков строк имеет такой тип: ```haskell [[String]] -- Список списков строк ``` Модель очень проста: ``` [ [String] ] │ Тип │ └ данных ┘ │ Тип │ │ списка │ └─ этих данных ─┘ ``` Хранить данные разных типов в стандартном списке невозможно. Однако вскоре мы познакомимся с другой стандартной структурой данных, которая позволяет это. ## Действия над списками Если списки создаются — значит это кому-нибудь нужно. Со списком можно делать очень много всего. В стандартной Haskell-библиотеке существует модуль `Prelude`, включающий широкий набор функций, работающих со списком. Откроем модуль `Main` и применим функцию `head`, возвращающую голову списка (то есть его первый элемент): ```haskell {.example_for_playground} module Main where main :: IO () main = putStrLn (head ["Vim", "Emacs", "Atom"]) ``` При запуске этой программы на выходе получим: ``` Vim ``` Модель такая: ``` ["Vim" , "Emacs", "Atom"] голова └─── хвост ───┘ ``` Эдакая гусеница получается: первый элемент — голова, а всё остальное — хвост. Функция `tail` возвращает хвост: ```haskell {.example_for_playground} main :: IO () main = print (tail ["Vim", "Emacs", "Atom"]) ``` Вот результат: ``` ["Emacs", "Atom"] ``` Функция `tail` формирует другой список, представляющий собою всё от первоначального списка, кроме головы. Обратите внимание на функцию `print`. В данном случае мы не могли бы использовать `putStrLn` как в предыдущем примере, ведь она применяется к значению типа `String`, в то время как функция `tail` вернёт нам значение типа `[String]`. Мы ведь помним про строгость компилятора: что ожидаем, то и получить должны. А функция `print`, как вы помните, предназначена для «стрингификации» значения: она берёт значение некоторого типа и выводит это значение на консоль уже в виде строки. Можно получить длину списка: ```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]`. {#block-string} Напишите функцию `extract`, которая принимает список целых чисел `l` и строку `from`: {.task_text} - Если `l` не пуст, а `from` равен `"head"`, верните новый список, состоящий из головы `l`. - Если `l` не пуст, а `from` равен `"tail"`, верните хвост `l`. - В любом другом случае верните список с единственным элементом: нулем. {.task_text} Определение списка с нулем и проверку длины списка вынесите в конструкцию `let-in`. {.task_text} ```haskell {.task_source #haskell_chapter_0090_task_0020} module Main where -- Your code here main :: IO () main = do print (extract [] "head") print (extract [] "tail") print (extract [1, 2] "head") print (extract [1, 2] "tail") print (extract [1, 2] "random") ``` Функция должна принимать два аргумента типов `[Int]` и `String`. Внутри функции после `let-in` воспользуйтесь multiway-if для возврата `[head l]`, `tail l` либо `fallbackLst`, в `let-in` объявленный равным `[0]`. {.task_hint} ```haskell {.task_answer} {-# LANGUAGE MultiWayIf #-} module Main where extract :: [Int] -> String -> [Int] extract l from = let notEmpty = length l > 0 fallbackLst = [0] in if | notEmpty && from == "head" -> [head l] | notEmpty && from == "tail" -> tail l | otherwise -> fallbackLst main :: IO () main = do print (extract [] "head") print (extract [] "tail") print (extract [1, 2] "head") print (extract [1, 2] "tail") print (extract [1, 2] "random") ``` Вернемся к идее о том, что строка в Haskell эквивалентна списку `Char`. Скажу более: `String` — это даже не самостоятельный тип, это всего лишь псевдоним для типа `[Char]`, и вот как он задан: ```haskell type String = [Char] ``` Ключевое слово `type` вводит синоним для уже существующего типа (англ. type synonym). Иногда его называют «псевдонимом типа». Читается это так: тип `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` с числом. Помимо обращения к элементу списка по индексу через `!!` также полезны операторы: - `:` — добавляет левый операнд к списку — правому операнду. Подробнее о `:` в конце главы. - `++` — конкатенирует списки или строки. - `>`, `>=`, `<`, `<=` — сравнивают списки между собой. А у функций `head` и `tail` есть зеркальные отражения: - `init` возвращает список без последнего элемента (как `tail`, но с начала списка). - `last` возвращает последний элемент списка (как `head`, но с конца). Но будьте осторожны: функции `head`, `tail`, `init` и `last` генерируют исключение при обработке пустого списка! ```haskell init [] ``` ``` ... Exception: Prelude.head: empty list ``` Помимо всего вышеприведенного могут пригодиться функции: {#block-useful-functions} - `null lst` проверяет, пуст ли список `lst`. - `elem item lst` проверяет, содержится ли элемент `item` в `lst`. - `reverse lst` переворачивает список `lst`. - `take n lst` возвращает список, состоящий из первых `n` элементов `lst`. - `drop n lst` возвращает список из элементов `lst` без первых `n` штук. - `minimum lst`, `maximum lst` возвращают минимальный и максимальный элементы в списке. - `sum lst`, `product lst` считают сумму и произведение элементов списка. Напишите функцию `takeTail`, которая принимает число `n` и список целых чисел `lst`. Функция должна вернуть список из последних `n` элементов `lst`. {.task_text} Все, что нужно для реализации функции — воспользоваться парой функций из перечисленных выше. {.task_text} ```haskell {.task_source #haskell_chapter_0090_task_0030} module Main where -- Your code here main :: IO () main = do print (takeTail 0 [1, 2, 3]) print (takeTail 2 [1, 2, 3]) print (takeTail 1 [1, 2, 3, 4]) print (takeTail 2 [1, 2, 3, 4]) print (takeTail 3 [1, 2, 3, 4]) print (takeTail 4 [1, 2, 3, 4]) ``` Рассмотрим возможное решение на примере `n`, равного 3, и списка `[1, 2, 3, 4]`. Если перевернуть список, мы получим `[4, 3, 2, 1]`. Если взять первые 3 элемента этого списка, мы получим новый список `[4, 3, 2]`. Если перевернуть его, то мы получим то, что возвращает функция `takeTail`. {.task_hint} ```haskell {.task_answer} module Main where takeTail :: Int -> [Int] -> [Int] takeTail n lst = reverse (take n (reverse lst)) main :: IO () main = do print (takeTail 0 [1, 2, 3]) print (takeTail 2 [1, 2, 3]) print (takeTail 1 [1, 2, 3, 4]) print (takeTail 2 [1, 2, 3, 4]) print (takeTail 3 [1, 2, 3, 4]) print (takeTail 4 [1, 2, 3, 4]) ``` ## Неизменность списка Как вы уже знаете, все данные в Haskell неизменны, как Египетские пирамиды. Списки — не исключение: мы не можем изменить существующий список, мы можем лишь создать на его основе новый список. Например: {#block-immutability} ```haskell {.example_for_playground} 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 ``` Стандартный оператор `:` добавляет значение, являющееся левым операндом, в начало списка, являющегося правым операндом. {#block-cons} Естественно, тип значения слева обязан совпадать с типом значений, содержащихся в списке справа. С концептуальной точки зрения функция `addTo` добавила новый IP-адрес в начало списка `hosts`. В действительности же никакого добавления не произошло, ибо списки неизменны. Оператор `:` взял значение `newHost` и список `hosts` и создал на их основе новый список, содержащий в себе уже три IP-адреса вместо двух. Оператор `:` также называется **cons** (сокращение от слова construct, то есть строить). В главе про рекурсию вы [узнаете](/courses/haskell/chapters/haskell_chapter_0160#block-list) об истинном устройстве списка и и том, какую роль в нем играет cons. Что выведет этот код? В случае ошибки напишите `error`. {.task_text} ```haskell {.example_for_playground} module Main where main :: IO () main = print (sum (tail (drop 2 (1:2:3:4:[])))) ``` ```consoleoutput {.task_source #haskell_chapter_0090_task_0040} ``` Запись `1:2:3:4:[]` эквивалентна записи `[1, 2, 3, 4]`. Применение `drop 2 [1, 2, 3, 4]` создает список `[3, 4]`. А хвост списка `[3, 4]` равен `[4]`. Сумма элементов этого списка равна 4. {.task_hint} ```haskell {.task_answer} 4 ```