Список

Помните, в одной из предыдущих глав я говорил, что познакомлю вас ещё с несколькими стандартными типами данных в Haskell? Пришло время узнать о списках.

Список (англ. list) — это стандартный тип, характеризующий уже не просто данные, но структуру данных (англ. data structure). Эта структура представляет собой набор данных одного типа, и едва ли хоть одна реальная Haskell-программа может обойтись без списков.

Структуры, содержащие данные одного типа, называют ещё гомогенными (в переводе с греческого: «одного рода»).

Вот список из трёх целых чисел:

[1, 2, 3]

Квадратные скобки и значения, разделённые запятыми. Вот так выглядит список из двух значений типа Double:

[1.3, 45.7899]

а вот и список из одного-единственного символа:

['H']

или вот из четырёх строк, отражающих имена протоколов транспортного уровня OSI-модели:

["TCP", "UDP", "DCCP", "SCTP"]

Если у вас есть опыт разработки на языке C, вы можете подумать, что список похож на массив. Однако, хотя сходства имеются, я намеренно избегаю слова «массив», потому что в Haskell существуют массивы (англ. array), это несколько иная структура данных.

Список — это тоже выражение, поэтому можно легко создать список списков произвольной вложенности. Вот так будет выглядеть список из ряда протоколов трёх уровней OSI-модели:

[ ["DHCP", "FTP", "HTTP"]
, ["TCP", "UDP", "DCCP", "SCTP"]
, ["ARP", "NDP", "OSPF"]
]

Это список списков строк. Форматирование в отношении квадратных скобок весьма вольное, при желании можно и так написать:

[["DHCP", "FTP", "HTTP"        ],
 ["TCP",  "UDP", "DCCP", "SCTP"],
 ["ARP",  "NDP", "OSPF"        ]]

Список может быть и пустым, то есть не содержать в себе никаких данных:

[]

Тип списка

Раз список представляет собой структуру, содержащую данные некоторого типа, каков же тип самого списка? Вот:

[Int]     -- Список целых чисел
[Char]    -- Список символов
[String]  -- Список строк

То есть тип списка так и указывается, в квадратных скобках. Упомянутый ранее список списков строк имеет такой тип:

[[String]]  -- Список списков строк

Модель очень проста:

[   [String]    ]

   │  Тип   │
   └ данных ┘

│     Тип       │
│    списка     │
└─ этих данных ─┘

Хранить данные разных типов в стандартном списке невозможно. Однако вскоре мы познакомимся с другой стандартной структурой данных, которая позволяет это.

Действия над списками

Если списки создаются — значит это кому-нибудь нужно. Со списком можно делать очень много всего. В стандартной Haskell-библиотеке существует отдельный модуль Data.List, включающий широкий набор функций, работающих со списком. Откроем модуль Main и импортируем в него модуль Data.List:

module Main where

-- Стандартный модуль для работы со списками.
import Data.List

main :: IO ()
main = putStrLn (head ["Vim", "Emacs", "Atom"])

Функция head возвращает голову списка, то есть его первый элемент. При запуске этой программы на выходе получим:

Vim

Модель такая:

["Vim"  ,  "Emacs", "Atom"]

 голова    └─── хвост ───┘

Эдакая гусеница получается: первый элемент — голова, а всё остальное — хвост. Функция tail возвращает хвост:

main :: IO ()
main = print (tail ["Vim", "Emacs", "Atom"])

Вот результат:

["Emacs", "Atom"]

Функция tail формирует другой список, представляющий собою всё от первоначального списка, кроме головы. Обратите внимание на новую функцию print. В данном случае мы не могли бы использовать нашу знакомую putStrLn, ведь она применяется к значению типа String, в то время как функция tail вернёт нам значение типа [String]. Мы ведь помним про строгость компилятора: что ожидаем, то и получить должны. Функция print предназначена для «стрингификации» значения: она берёт значение некоторого типа и выводит это значение на консоль уже в виде строки.

Внимательный читатель спросит, каким же образом функция 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]. Скажу более: String — это даже не самостоятельный тип, это всего лишь псевдоним для типа [Char], и вот как он задан:

type String = [Char]

Ключевое слово type вводит синоним для уже существующего типа (англ. type synonym). Иногда его называют «псевдонимом типа». Читается это так:

type  String  =      [Char]

тип   этот    равен  тому

Таким образом, объявление функции handleTableRow можно было бы переписать так:

handleTableRow :: [Char] -> [Char]

При работе со списками мы можем использовать уже знакомые промежуточные выражения, например:

handleTableRow :: String -> String
handleTableRow row
  | size == 2 = composeTwoOptionsFrom row
  | size == 3 = composeThreeOptionsFrom row
  | otherwise = invalidRow row
  where size = length row

А можно и так:

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 неизменны, как Египетские пирамиды. Списки — не исключение: мы не можем изменить существующий список, мы можем лишь создать на его основе новый список. Например:

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"]

Результат этой программы таков:

["124.67.54.90","45.67.78.89","123.45.65.54"]

Рассмотрим определение функции addTo:

addTo newHost hosts = newHost : hosts

Стандартный оператор : добавляет значение, являющееся левым операндом, в начало списка, являющегося правым операндом. Читается это так:

newHost   :         hosts

          этот
          оператор

берёт
это
значение
                    и добавляет
                    его в начало
                    этого списка

Естественно, тип значения слева обязан совпадать с типом значений, содержащихся в списке справа.

С концептуальной точки зрения функция addTo добавила новый IP-адрес в начало списка hosts. В действительности же никакого добавления не произошло, ибо списки неизменны. Оператор : взял значение newHost и список hosts и создал на их основе новый список, содержащий в себе уже три IP-адреса вместо двух.

Перечисление

Допустим, понадобился нам список целых чисел от одного до десяти. Пишем:

main :: IO ()
main = print tenNumbers
  where tenNumbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Неплохо, но избыточно, ведь чисел могло быть и сто, и тысяча. Есть лучший путь:

main :: IO ()
main = print tenNumbers
  where tenNumbers = [1..10]

Красиво, не правда ли? Выражение в квадратных скобках называется перечислением (англ. enumeration или сокращённо enum). Иногда её именуют также арифметической последовательностью. Идея предельно проста: зачем указывать содержимое списка целиком в той ситуации, когда можно указать лишь диапазон значений? Это мы и сделали:

[1..10] = [1,2,3,4,5,6,7,8,9,10]

Значение слева от .. — это начало диапазона, а значение справа — его конец. Компилятор сам догадается, что шаг между числами в данной последовательности равен 1. Вот ещё пример:

[3..17] = [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]

 _         _

    ==                                        ==

Мы можем задать шаг и явно:

[2,4..10] = [2,4,6,8,10]

Получили только чётные значения. Схема проста:

[2,      4      .. 10]

 первый            конец
         второй

 │  разница   │
 └─ даёт шаг ─┘

Вот ещё пример:

[3,9..28] = [3,9,15,21,27]

Можно задать и нисходящий диапазон:

[9,8..1] = [9,8,7,6,5,4,3,2,1]

Или так:

[-9, -8.. -1] = [-9,-8,-7,-6,-5,-4,-3,-2,-1]

Да, отрицательные числа тоже работают. Можно взять также и числа с плавающей точкой:

[1.02,1.04..1.16] = [1.02,1.04,1.06,1.08,1.1,1.12,1.14,1.16]

В общем, идея ясна. Но что это мы всё с числами да с числами! Возьмём символы:

['a'..'z'] = "abcdefghijklmnopqrstuvwxyz"

Диапазон от 'a' до 'z' — получили английский алфавит в виде [Char] или, как мы уже знаем, просто String. При большом желании явно задать шаг можно и здесь:

['a','c'..'z'] = "acegikmoqsuwy"

Вот такая красота.

Теперь, после знакомства со списком, мы будем использовать их постоянно.

Для любопытных

В разделе про диапазоны для списка мы оперировали значениями типа Int, Double и Char. Возникает вопрос: а можно ли использовать значения каких-нибудь других типов? Отвечаю: можно, но с оговоркой. Попробуем проделать это со строкой:

main :: IO ()
main = print ["a","aa".."aaaaaa"]  -- Ну-ну...

При попытке скомпилировать такой код увидим ошибку:

No instance for (Enum [Char])
  arising from the arithmetic sequence ‘"a", "aa" .. "aaaaaa"’

И удивляться тут нечему: шаг между строками абсурден, и компилятор в замешательстве. Не все типы подходят для перечислений в силу своей природы, однако в будущем, когда мы научимся создавать наши собственные типы, мы узнаем, что их вполне можно использовать в диапазонах. Наберитесь терпения.

Приоткрою секрет: этот странный пример с шагом между строками теоретически можно-таки заставить работать, но о том, как это сделать, мы узнаем во время знакомства с Третьим Китом Haskell.