Haskell/ListsAndTuples

В Haskell используются две фундаментальные структуры, предназначенные для работы с множественными значениями: списки и кортежи. И те, и другие собирают несколько значений в одно.

Списки

Создадим несколько списков в GHCI:

 ghci> let numbers = [1,2,3,4]
 ghci> let truths  = [True, False, False]
 ghci> let strings = ["here", "are", "some", "strings"]

Элементы списка записываются в квадратных скобках и разделяются запятыми. Единственное ограничение - все элементы списка должны быть одного типа. Попытка определить список с элементами различных типов приводит к ошибке типов:

 ghci> let mixed = [True, "bonjour"]

 <interactive>:1:19:
     Couldn't match `Bool' against `[Char]'
       Expected type: Bool
       Inferred type: [Char]
     In the list element: "bonjour"
     In the definition of `mixed': mixed = [True, "bonjour"]

Создание списков

Вдобавок к определению списка путём перечисления его элементов, вы можете построить список шаг за шагом при помощи оператора (:). Этот оператор называется "cons". Такое название он получил в наследство от LISP-программистов, назвавших этот оператор так от слова "constructor". Cons используется для того, чтобы присоединить к списку элемент:

 ghci> let numbers = [1,2,3,4]
 ghci> numbers
 [1,2,3,4]
 ghci> 0:numbers
 [0,1,2,3,4]

Когда вы присоединяете элемент к списку (something:someList), вы получаете новый список. Таким образом вы можете присоединить сколько угодно элементов. Обратите внимание, что элемент добавляется слева.

 ghci> 1:0:numbers
 [1,0,1,2,3,4]
 ghci> 2:1:0:numbers
 [2,1,0,1,2,3,4]
 ghci> 5:4:3:2:1:0:numbers
 [5,4,3,2,1,0,1,2,3,4]

На самом деле, в Haskell все списки строятся путём присоединения элементов к пустому списку, []. Запись с квадратными скобками и запятыми - всего лишь синтаксический сахар. Так что [1,2,3,4,5] - абсолютно то же самое, что 1:2:3:4:5:[]

Однако нужно принять во внимание следующее: тогда как True:False:[] - рабочий код, True:False вовсе не рабочий:

 ghci> True:False

 <interactive>:1:5:
     Couldn't match `[Bool]' against `Bool'
       Expected type: [Bool]
       Inferred type: Bool
     In the second argument of `(:)', namely `False'
     In the definition of `it': it = True : False

True:False приводит к знакомому сообщению об ошибке. в нём говорится, что оператор присоединения (:) (который на самом деле является всего лишь функцией) ожидает список в качестве второго аргумента, но вместо списка был получен Bool. (:) умеет присоединять значения к спискам, но не значения к значениям.

Строки

Ранее уже было коротко упомянуто, что строки в Haskell - всего лишь списки символов. Это означает, что со строками можно работать так же, как со списками. К примеру, вместо того, чтобы напрямую задать строку последовательностью символов в кавычках, мы также можем задать её с помощью последовательного присоединения символов, либо используя оператор (:) и завершая последовательность пустым списком, либо используя запись с квадратными скобками:

 ghci>"hey" == ['h','e','y']
 True
 ghci>"hey" == 'h':'e':'y':[]
 True

Кавычки - это тоже синтаксический сахар.

Списки списков

Списки могут содержать что угодно — если всё это что угодно одного и того же типа. Списки подходят под что угодно, так что они могут содержаться в списках. Попробуйте следующее в интерпретаторе:

 ghci> let listOfLists = [[1,2],[3,4],[5,6]]
 ghci> listOfLists
 [[1,2],[3,4],[5,6]]

Стоит отметить, что тип списка, к примеру, целых чисел отличен от типа целых чисел. То есть, Int и [Int] - это разные типы.

Списки различных типов не могут быть присоединены друг к другу, но пустой список можно присоединить к любому списку. Например, []:[[1, 2], [1, 2, 3]] даст [[], [1, 2], [1, 2, 3]], а [1]:[[1, 2], [1, 2, 3]] даст [[1], [1, 2], [1, 2, 3]], но ['a']:[[1, 2], [1, 2, 3]] уже вызовет сообщение об ошибке.

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

Кортежи

Другое представление множественности

Кортежи предлагают другой способ связать несколько значений в одно. У списков и кортежей есть несколько ключевых отличий:

• Кортежи имеют постоянное число элементов (неизменяемое); невозможно присоединить элемент к кортежу. Следовательно, имеет смысл использовать кортежи тогда, когда вы заранее знаете, сколько элементов нужно сохранить. К примеру, мы могли бы хранить координаты точек в двух измерениях. Мы точно знаем, сколько значений нам понадобится для каждой точки (два – координаты x и y), так что здесь применимы кортежи.

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

Элементы кортежа записываются в круглых скобках через запятые:

 (True, 1)
 ("Hello world", False)
 (4, 5, "Six", True, 'b')

Первый пример содержит два элемента: True и 1. Второй также содержит два элемента: "Hello world" и False. Третий содержит пять элементов: 4 (число), 5 (ещё число), "Six" (строка), True (логическое значение), и 'b' (символ).

Небольшое замечание о происхождении названия: в английском языке "n-tuple" означает то же, что в русском n-ка, в частности, четвёрка (элементов) переводится как "quadruple", пятёрка как "quintuple" и так далее.

Кортежи удобно использовать, когда необходимо написать функцию, возвращающую несколько значений. Во многих языках для таких случаев используется приём заворачивания нескольких значений в специальную структуру данных. В случае Haskell используется кортеж.

Кортежи внутри кортежей и другие комбинации

Мы можем думать о кортежах кортежей так же, как думали о списках списков. Кортежи могут хранить что угодно, даже другие кортежи, причём с произвольной степенью вложенности. Аналогично можно получить список кортежей, кортеж списков и другие подобные вещи.

 ((2,3), True)
 ((2,3), [2,3])
 [(1,2), (3,4), (5,6)]

Тип кортежей определяется не только их размером, но и типами содержащихся в них значений, как в случае со списками. К примеру, кортежи ("Hello",32) и (47,"World") фундаментально различны. Первый имеет тип (String,Int), тогда как другой (Int,String). Это важно учитывать при построении списков кортежей. Мы можем строить такие списки, как [("a",1),("b",9),("c",9)], но такие, как [("a",1),(2,"b"),(9,"c")] в Haskell недопустимы.

Извлечение значений

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

Начнём с пар, представляющих координаты точки (x, y). Положим, вы хотите определить конкретный квадрат на шахматном поле. Для этого пронумеруем строки и столбцы цифрами от 1 до 8. Тогда пара (2, 5) будет представлять квадрат во второй строке в пятом столбце. Положим, нужно получить все фигуры, расположенные в данном ряду. Мы можем взять координаты всех фигур и выделить из них те, ряд которых совпадает с искомым. Имея пару координат (x, y) фигуры, наша функция должна извлечь x (координату строки). Для таких целей предназначены готовые функции, fst и snd, возвращающие первый и второй элемент данной пары соответственно. Рассмотрим несколько примеров:

 ghci> fst (2, 5)
 2
 ghci> fst (True, "boo")
 True
 ghci> snd (5, "Hello")
 "Hello"