Skip to content

Latest commit

 

History

History
401 lines (373 loc) · 21.6 KB

7. Списки, стандартные функции для работы с ними. Генерация (выделение) списков..md

File metadata and controls

401 lines (373 loc) · 21.6 KB
Raw

Списки, стандартные функции для работы с ними. Генерация (выделение) списков.

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

Базовые способы сконструировать список:
  1. Создать пустой список (это констрктор-константа)
[] :: [a]
  1. Взять существующий список и добавить в голову элемент (бинарный оператор :)
infixr 5 :          -- оператор добавления в список правоассоциативный
(:) :: a -> [a] -> [a]
let lst = 3 : 5 : [] --добавление двух элементов в голову по порядку

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

Также можно строить сечения оператора :

let const42 = (42 :)   -- добавляет  в голову списка элемент 42
Способы деконструирования списков:
  1. head - возвращает первый элемент списка
  2. tail - возвращает хвост списка (весь список, кроме первого элемента)
head :: [a] -> a
head (x:xs) = x
head [] = error "Prelude.head: empty list"
tail :: [a] -> [a]
tail (x:xs) = xs
tail [] = error "Prelude.tail: empty list"

Многие функции над списками используют сопоставление с двумя образцами: один для пустого списка [], другой для непустого (x:xs). При этом переменная x связывается с головой (первым элементом) непустого списка, а переменная xs — с его хвостом (остатком после отделения первого элемента). Две приведенные выше функции просто возвращают результаты этих связываний. Функции head и tail являются частичными (то есть определены не на всех возможных аргументах).

Функция, возвращающая второй элемент
second :: [a] -> a
second xs = head (tail xs)

А вот так в бесточечном стиле:

second :: [a] -> a
second = head . tail

Гораздо более мощным способом деконструкции списка является сопоставление с образцом (в качестве образцов используются конструкторы):

second (_ : x : _) = x  -- получение второго элемента списка

Стандартные функции

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

length :: [a] -> Int    -- длина списка
length [] = 0
length (_:xs) = 1 + length xs

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

infixr 5 ++
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys

Функция, обеспечивающая конкатенацию списка списков в список:

concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss

Функция, проверяющая, является ли список пустым:

null :: [a] -> Bool
null [] = True
null _ = False

Функция, проверяющая наличие элемента в списке:

infix 4 `elem`
elem :: (Eq a) => a -> [a] -> Bool
elem _ [] = False
elem x (y:ys) = x == y || elem x ys

Часто использутся инфиксно

GHCi> 'e' `elem` "Hello"
True
GHCi> 'i' `elem` "Hello"
False

Функция, осуществляющая поиск значения с заданным ключом в ассоциативном списке (то есть списке пар ключ-значение):

lookup :: Eq a => a -> [(a,b)] -> Maybe b
lookup _ [] = Nothing
lookup key ((k,v):kvs)
| key == k = Just v
| otherwise = lookup key kvs

Возвращаемым значением служит тип Maybe, поскольку поиск может завершится неудачей

GHCi> lookup 2 [(1,"Hello"),(3,"world")]
Nothing
GHCi> lookup 3 [(1,"Hello"),(3,"world")]
Just "world"

Оператор, возвращающий элемент списка с заданным индексом:

infixl 9 !!
(!!) :: [a] -> Int -> a
xs !! n | n < 0 = error "Prelude.!!: negative index"
[] !! _ = error "Prelude.!!: index too large"
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n-1)

Левая ассоциативность позволяет удобно обслуживать вложенные списки:

GHCi> ["Hello","world"] !! 0 !! 1
'e'
GHCi> ["Hello","world"] !! 1 !! 2
'r'

Функция, возвращающая последний элемент списка:

last :: [a] -> a
last (x:[]) = x
last (_:xs) = last xs

Функция, которая переворачивает список:

reverse :: [a] -> [a]
reverse l = rev l [] where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

Функция take получает целое число n и список и возвращает первые n элементов списка. Если элементов меньше, чем n, возвращается сколько есть. Если n не положительно, возвращается пустой список.

take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
GHCi> take 3 "ABCDE"
"ABC"
GHCi> take 10 "ABCDE"
"ABCDE"

Функция drop «дуальна» к take: она отбрасывает первые n элементов, возвращая то, что осталось.

drop :: Int -> [a] -> [a]
drop n xs | n <= 0 = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
Семейства zip и zipWith

Имеется набор стандартных функции, позволяющих соединить несколько списков в один. Мы уже обсуждали конкатенацию, когда один из списков присоединялся в голову другого. Другим способом соединения служит «зиппирование», от английского zipper (застежка-молния). Зубцы с двух сторон такой застежки сцепляются последовательно: первый с первым, второй со вторым и т.д. Именно так обрабатываются и элементы двух списков в функции zip: из элементов с одинаковыми индексами образуется пара, помещаемая в результирующий список с тем же индексом:

zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (a:as) (b:bs) = (a,b) : zip as bs

На самом деле имеется целое семейство функций, подобных zip: сама zip, zip3, zip4 и т.д. Результирующий список образуется конструированием кортежа подходящего размера из элементов списков-аргументов:

zip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
...

Функция zip задает стандартный для Haskell способ явного индексирования:

GHCi> zip [1,2,3,4] "ABC"
[(1,'A'),(2,'B'),(3,'C')]

Отметим, что длина самого короткого из списков определяет длину результата. Это означает, что при «зиппировании» мы можем потерять часть информации — в приведенном примере это число 4. Имеется семейство unzip, «обратное» zip:

unzip :: [(a,b)] -> ([a],[b])
unzip3 :: [(a,b,c)] -> ([a],[b],[c])
...

Более общим способом соединения двух списков служит замена в функциях семейства zip конструктора данных пары (тройки, четверки и т.п.) на произвольную функцию нужного числа аргументов, предоставляеную пользователем. Это порождает семейство функции высших порядков zipWith:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
...
Функции высших порядков

Функции высших порядков - это функции, которые принимают в качестве аргументов другие функции. В библиотеке Data.List много функций высших порядков. У следующих двух функций первый аргумент — функция типа a -> Bool, то есть унарный предикат.

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] = []
takeWhile p (x:xs)
| p x = x : t

Функция filter возвращает (сохраняя порядок) все те элементы списка, которые удовлетворяют предикату. Функция takeWhile возвращает наибольший префикс списка, все элементы которого удовлетворяют предикату.

GHCi> filter (<50) [2,12,85,0,6]
[2,12,0,6]
GHCi> takeWhile (<50) [2,12,85,0,6]
[2,12]
GHCi> dropWhile (<50) [2,12,85,0,6]
[85,0,6]

У функции высшего порядка map функциональный аргумент — произвольная функция:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

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

GHCi> map (+1) [1,2,3]
[2,3,4]
GHCi> map length ["Good","bye","world"]
[4,3,5]
GHCi> map (^2) . map length $ ["Good","bye","world"]
[16,9,25]

Функция all принимает в качестве аргумента унарный предикат и применяет его к элементам списка:

and, or :: [a] -> Bool

and [] = True
and (x:xs) = x && and xs

or [] = False
or (x:xs) = x || or xs

all :: (a -> Bool) -> [a] -> Bool
all p = and . map p

Пример вызова all для определения, являются все элементы списка нечетными:

GHCi> all odd [1, 3, 5]
True
GHCi> all odd [1, 2, 3]
False

Функция any проверяет, присутствует ли в списке хотя бы один элемент, удовлетворяющий условиям:

any :: (a -> Bool) -> [a] -> Bool
any p = or . map p

Способы генерации спсиков

Если определить рекурсивную функцию без терминирующего условия, то такая рекурсия во время исполнения приведет к расходимости.

GHCi> ones = 1 : ones
GHCi> :type ones
ones :: Num a => [a]
GHCi> ones
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,Interrupted.
GHCi> numsFrom n = n : numsFrom (n+1)
GHCi> :t numsFrom
numsFrom :: Num t => t -> [t]
GHCi> numsFrom 3
[3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,Interrupted.

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

GHCi> take 2 ones
[1,1]
GHCi> take 4 (numsFrom 3)
[3,4,5,6]

Каков механизм этой «внешней терминации»? Вспомнив реализацию

take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs

приведем шаги ленивого вычислителя:

take 2 ones → -- (1)
take 2 (1 : ones) → -- (2)
1 : take (2-1) ones) → -- (3)
1 : take 1 (1 : ones) → -- (4)
1 : 1 : take (1-1) ones) → -- (5)
1 : 1 : take 0 ones) → -- (6)
1 : 1 : []
  1. сопоставление с образцом форсирует вычисление ones до WHNF;
  2. подходит последнее уравнение в определении take, используем его;
  3. сопоставление с образцом форсирует вычисление до WHNF обоих аргументов take: первого, чтобы отвергнуть первое из уравнений в определении take, второго — чтобы отвергнуть второе;
  4. используем последнее уравнение в определении take;
  5. сопоставление с образцом форсирует вычисление до WHNF первого аргумента take;
  6. подходит первое уравнение в определении take, используем его

Таким образом мы можем эффективно работать с «бесконечными» списками. Более того, мы можем декларативно описывать преобразования бесконечных списков, порождая новые (бесконечные) списки. Функции работы со списками из Data.List реализованы так, чтобы способ обработки бесконечных списков ничем не отличается от конечных:

GHCi> squares = map (^2) (numsFrom 0)
GHCi> takeWhile (<=100) squares
[0,1,4,9,16,25,36,49,64,81,100]

Каноническим примером рекурсивного построения бесконечного списка служит бесконечный список чисел Фибоначчи

GHCi> fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)
GHCi> take 10 fibs
[0,1,1,2,3,5,8,13,21,34]

Имеется библиотечный аналог нашей пользовательской функции numsFrom. Он носит название enumFrom и имеет более общий тип, позволяющий работать не только с числами, но и с любыми перечислениями, то есть любыми представителями класса типов Enum.

GHCi> :t enumFrom
enumFrom :: Enum a => a -> [a]
GHCi> enumFrom False
[False,True]
GHCi> enumFrom ((maxBound::Int) - 2)
[9223372036854775805,9223372036854775806,9223372036854775807]

Заметим, что когда тип перечисления является ограниченным (то есть представителем класса типов Bounded), то список аккуратно терминируется. Для неограниченного типа Integer функция enumFrom порождает бесконечный список. Для функции enumFrom имеется удобный синтаксический сахар, задаваемый следующим правилом трансляции

[e1..] ≡ enumFrom e1

То есть предыдущие примеры могут быть записаны так

GHCi> [False ..]
[False,True]
GHCi> [(maxBound::Int) - 2 ..]
[9223372036854775805,9223372036854775806,9223372036854775807]

Класс типов Enum задает еще ряд полезных арифметических последовательностей, которые транслируются в функции, подобные enumFrom:

GHCi> [1..10]
[1,2,3,4,5,6,7,8,9,10]
GHCi> ['A'..'z']
"ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz"
GHCi> [1,3..17]
[1,3,5,7,9,11,13,15,17]
GHCi> [1,3..]
[1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,Interrupted.

Для формирования «нелинейных» последовательностей имеется другая техника, носящая название выделение списка (list comprehension)

GHCi> digits = [0..9]
GHCi> [ x^2 | x <- digits ]
[0,1,4,9,16,25,36,49,64,81]

Часть справа от вертикальной черты носит название генератора: элементы, связываемые с переменной x пробегают по всему списку digits. Слева от вертикальной черты находится выражение, в котором можно использовать x^30. При наличии нескольких генераторах чаще обновляется тот, что правее:

GHCi> [ [x,y] | x <- "ABC", y <- "de" ]
["Ad","Ae","Bd","Be","Cd","Ce"]

Генераторы могут ссылаться на значения из предыдущих генераторов; кроме того можно использовать предикаты над этими значениями для фильтрации результатов. Вот например, выделение пифагоровых троек (сторон прямоугольных треугольников с целыми длинами):

GHCi> ls = [1..19]
GHCi> [ (x,y,z) | x <- ls, y <- [1..x], z <- ls, x^2 + y^2 == z^2 ]
[(4,3,5),(8,6,10),(12,5,13),(12,9,15),(15,8,17)]

Для фильтрации можно использовать сопоставление с образцом в генераторе:

GHCi> tst = [Just 2,Nothing,Just 3]
GHCi> [ x | Just x <- tst ]
[2,3]

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