Кортежи и списки в Haskell

Кортежи

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

Синтаксис

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

Prelude> (2,True)
(2,True)
Prelude> (2,True,'c')
(2,True,'c')

Альтернативный синтаксис (префиксный стиль конструирования):

Prelude> (True,3)
(True,3)
Prelude> (,) True 3
(True,3)
Prelude> (,,) True 3 'c'
(True,3,'c')

Двухэлементные кортежи

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

Prelude> fst (2,True)
2
Prelude> snd (2,True)
True

Зададим точки на плоскости парами типа (Double, Double). Функцию dist, возвращает расстояние между двумя точками, передаваемыми ей в качестве аргументов.

dist :: (Double, Double) -> (Double, Double) -> Double
dist p1 p2 = sqrt $ (fst p1 - fst p2) * (fst p1 - fst p2) + (snd p1 - snd p2) * (snd p1 - snd p2)

Тип кортежа

Тип кортежа устроен точно также как его значение.

Prelude> :t ('x',True)
('x',True) :: (Char, Bool)
Prelude> :t ('x',True,'s')
('x',True,'s') :: (Char, Bool, Char)

Единичный кортеж

В Haskell нет единичного кортежа. Выражение (3) представляет собой не кортеж, а просто тройку заключенную в скобки, которые в данном случае рассматриваются как лишний декоративный элемент возможно связанный с группировкой.

Prelude> (3)
3

Пустой кортеж

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

Prelude> ()
()
Prelude> :t ()
() :: ()

Полиморфизм кортежей

Кортежи тоже полиморфны. Более того степень полиморфизма кортежей даже выше чем степень полиморфизма списков.

Prelude> :t (,)
(,) :: a -> b -> (a, b)
Prelude> :t (,,)
(,,) :: a -> b -> c -> (a, b, c)
Prelude> :t (,) True 'c'
(,) True 'c' :: (Bool, Char)
Prelude> let dup x = (x,x)
Prelude> :t dup
dup :: t -> (t, t)
Prelude> :t fst
fst :: (a, b) -> a
Prelude> :t snd
snd :: (a, b) -> b

Можно реализовать 9 разных всегда завершающихся функций с типом a -> (a,b) -> a -> (b,a,a).
foo :: a -> (a,b) -> a -> (b,a,a)

1. let foo p1 p2 p3 = (snd p2, p1, p1)
2. let foo p1 p2 p3 = (snd p2, p1, fst p2)
3. let foo p1 p2 p3 = (snd p2, p1, p3)
4. let foo p1 p2 p3 = (snd p2, fst p2, p1)
5. let foo p1 p2 p3 = (snd p2, fst p2, fst p2)
6. let foo p1 p2 p3 = (snd p2, fst p2, p3)
7. let foo p1 p2 p3 = (snd p2, p3, p1)
8. let foo p1 p2 p3 = (snd p2, p3, fst p2)
9. let foo p1 p2 p3 = (snd p2, p3, p3)

Списки

Списки как и кортежи представляют собой контейнерный тип. Однако имеются два существенных отличия:

1. списки гомогенные (все элементы списка принадлежат к одному типу) в отличие от гетерогенных кортежей;
2. длина списка не фиксирована и неизвестна компилятору в отличие от кортежа.

Синтаксис

Элементы списка перечисляются через запятую, а сам список заключается в квадратный скобки.

Prelude> [1,2,3]
[1,2,3]
Prelude> [False,True]
[False,True]

Тип списков

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

Prelude> :t [False,True]
[False,True] :: [Bool]

Списки типа Char

Для списков типа Char имеется специальный синтаксис.

Prelude> ['H','i']
"Hi"
Prelude> :t ['H','i']
['H','i'] :: [Char]
Prelude> :t "Hi"
"Hi" :: [Char]
Prelude> "Hi" :: String
"Hi"

Для списков типа Char имеется стандартный синоним String, который может использоваться всюду, где используется список типа Char. Вместо списка типа Char можно писать String.

Операции над списками

Операция добавления элемента в голову списка:

Prelude> let str = 'H' : "ello"
Prelude> str
"Hello"

Оператор добавления элемента в голову списка это оператор двоеточие. Левым его аргументом служит элемент списка, а правым аргументом целый список.

Операция конкатенации двух списков:

Prelude> str ++ ", world!"
"Hello, world!"

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

Операторы (:) и (++) имеют одинаковую ассоциативность и приоритет.

Prelude> :info :
data [] a = ... | a : [a]  -- Defined in ‘GHC.Types’
infixr 5 :

data [] a = ... | a : [a]  -- Defined in ‘GHC.Types’
infixr 5 :
Prelude> :info ++
(++) :: [a] -> [a] -> [a]  -- Defined in ‘GHC.Base’
infixr 5 ++

Prelude> 1 : [2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> [1,2] ++ 3 : [4,5,6]
[1,2,3,4,5,6]
Prelude> [1,2] ++ (:) 3 [4,5,6]
[1,2,3,4,5,6]
Prelude> (:) 1 ((++) [2,3] [4,5,6])
[1,2,3,4,5,6]

Полиморфизм списков

Встроенные структуры такие как списки и кортежи тоже параметрически полиморфны. Списки имеют полиморфное поведение, в качестве элементов списка можно использовать любой тип. Списки полиморфны по типу элементов, которые хранятся в этом списке. Этот же полиморфизм присутствует и в стандартных функциях над списками.

Prelude> :t [True,False]
[True,False] :: [Bool]
Prelude> :t "Hello"
"Hello" :: [Char]
Prelude> :t []
[] :: [t]
Prelude> :t (++)
(++) :: [a] -> [a] -> [a]
Prelude> :t (:)
(:) :: a -> [a] -> [a]