Haskell Language
Списки

Синтаксис

1. пустой конструктор списка

   [] :: [a]

2. конструктор непустого списка

   (:) :: a -> [a] -> [a]

3. head - возвращает первое значение списка

   head :: [a] -> a

4. last - возвращает последнее значение списка

   last :: [a] -> a

5. tail - возвращает список без первого элемента

   tail :: [a] -> [a]

6. init - возвращает список без последнего элемента

   init :: [a] -> [a]

7. xs !! i - вернуть элемент по индексу i в списке xs

   (!!) :: Int -> [a] -> a

8. взять n xs - вернуть новый список, содержащий n первых элементов списка xs

   take :: Int -> [a] -> [a]

9. map :: (a -> b) -> [a] -> [b]

10. filter :: (a -> Bool) -> [a] -> [a]

11. (++) :: [a] -> [a]

12. concat :: [[a]] -> [a]

замечания

Список литературы

emptyList     = []

singletonList = [0]               -- = 0 : []

listOfNums    = [1, 2, 3]         -- = 1 : 2 : [3]

listOfStrings = ["A", "B", "C"]

Конкатенация списка

listA      = [1, 2, 3]

listB      = [4, 5, 6]

listAThenB = listA ++ listB       -- [1, 2, 3, 4, 5, 6]

(++) xs     [] = xs
(++) []     ys = ys
(++) (x:xs) ys = x : (xs ++ ys)

Основы списка

Конструктор типов для списков в Haskell Prelude - [] . Объявление типа для списка, содержащего значения типа Int , записывается следующим образом:

xs :: [Int]    -- or equivalently, but less conveniently,
xs :: [] Int

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

[1,2,3]   :: [Int]
[1,2,3,4] :: [Int]

Списки создаются с использованием двух конструкторов :

• [] создает пустой список.

• (:) , произносится как «cons», добавляет элементы в список. Заканчивая x (значение типа a ) на xs (список значений одного и того же типа a ) создает новый список, голова которого (первый элемент) равна x , а хвост (остальные элементы) - xs .

Мы можем определить простые списки следующим образом:

ys :: [a]
ys = []

xs :: [Int]
xs = 12 : (99 : (37 : []))   
-- or  = 12 : 99 : 37 : []     -- ((:) is right-associative)
-- or  = [12, 99, 37]          -- (syntactic sugar for lists)

Обратите внимание: (++) , который может использоваться для построения списков, определяется рекурсивно в терминах (:) и [] .

Списки обработки

Для обработки списков мы можем просто сопоставить шаблон конструкторам типа списка:

listSum :: [Int] -> Int
listSum []          = 0
listSum (x:xs) = x + listSum xs

Мы можем сопоставить больше значений, указав более сложный шаблон:

sumTwoPer :: [Int] -> Int
sumTwoPer [] = 0
sumTwoPer (x1:x2:xs) = x1 + x2 + sumTwoPer xs
sumTwoPer (x:xs) = x + sumTwoPer xs

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

Haskell Prelude определяет множество встроенных модулей для обработки списков, таких как map , filter и т. Д. По возможности, вы должны использовать их вместо написания собственных рекурсивных функций.

Доступ к элементам в списках

Доступ к n- му элементу списка (с нулевым основанием):

list = [1 .. 10]

firstElement = list !! 0           -- 1

Обратите внимание, что !! является частичной функцией, поэтому определенные входы создают ошибки:

list !! (-1)     -- *** Exception: Prelude.!!: negative index  

list !! 1000     -- *** Exception: Prelude.!!: index too large

Там также Data.List.genericIndex , перегруженная версия !! , который принимает любое Integral значение как индекс.

import Data.List (genericIndex)

list `genericIndex` 4              -- 5

Когда они выполняются в виде односвязных списков, эти операции занимают время O (n) . Если вы часто Data.Vector к элементам по индексу, вероятно, лучше использовать Data.Vector (из векторного пакета) или другие структуры данных.

Изменяется

Создание списка с 1 по 10 прост с использованием нотации диапазона:

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

Чтобы указать шаг, добавьте запятую и следующий элемент после элемента start:

[1,3..10]  -- [1,3,5,7,9]

Обратите внимание, что Haskell всегда делает шаг как арифметическую разницу между терминами и что вы не можете указать больше, чем первые два элемента и верхнюю границу:

[1,3,5..10] -- error
[1,3,9..20] -- error

Чтобы создать диапазон в порядке убывания, всегда указывайте отрицательный шаг:

[5..1]     -- []

[5,4..1]   -- [5,4,3,2,1]

Поскольку Haskell не является строгим, элементы списка оцениваются только в том случае, если они необходимы, что позволяет нам использовать бесконечные списки. [1..] - это бесконечный список, начинающийся с 1. Этот список может быть привязан к переменной или передан как аргумент функции:

take 5 [1..]   -- returns [1,2,3,4,5] even though [1..] is infinite

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

[1.0,1.5..2.4]    -- [1.0,1.5,2.0,2.5] , though 2.5 > 2.4

[1.0,1.1..1.2]    -- [1.0,1.1,1.2000000000000002] , though 1.2000000000000002 > 1.2

Диапазоны работают не только с числами, но и с любым типом, который реализует класс Enum . Учитывая некоторые перечислимые переменные a , b , c , синтаксис диапазона эквивалентен вызову этих методов Enum :

[a..]    == enumFrom a
[a..c]   == enumFromTo a c
[a,b..]  == enumFromThen a b
[a,b..c] == enumFromThenTo a b c

Например, с Bool это

 [False ..]      -- [False,True]

Обратите внимание на пробел после False , чтобы это не анализировалось как квалификация имени модуля (т.е. False.. будет анализироваться как . Из модуля False ).

Основные функции в списках

head [1..10]       --    1

last [1..20]       --    20

tail [1..5]        --    [2, 3, 4, 5]

init [1..5]        --    [1, 2, 3, 4]

length [1 .. 10]   --    10

reverse [1 .. 10]  --    [10, 9 .. 1]

take 5 [1, 2 .. ]  --    [1, 2, 3, 4, 5]

drop 5 [1 .. 10]   --    [6, 7, 8, 9, 10]

concat [[1,2], [], [4]]   --    [1,2,4]

foldl

Так реализуется левая складка. Обратите внимание, как порядок аргументов в шаговой функции перевернут по сравнению с foldr (правая сфера):

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc []     =  acc
foldl f acc (x:xs) =  foldl f (f acc x) xs         -- = foldl f (acc `f` x) xs  

Левая складка, foldl , ассоциируется слева. То есть:

foldl (+) 0 [1, 2, 3]     -- is equivalent to ((0 + 1) + 2) + 3

Причина в том, что foldl оценивается следующим образом (посмотрите на индуктивный шаг foldl ):

foldl (+) 0 [1, 2, 3]                        --  foldl (+)    0   [ 1,   2,   3 ]
foldl (+) ((+) 0 1) [2, 3]                   --  foldl (+)   (0 + 1)   [ 2,   3 ]
foldl (+) ((+) ((+) 0 1) 2) [3]              --  foldl (+)  ((0 + 1) + 2)   [ 3 ]
foldl (+) ((+) ((+) ((+) 0 1) 2) 3) []       --  foldl (+) (((0 + 1) + 2) + 3) []
((+) ((+) ((+) 0 1) 2) 3)                    --            (((0 + 1) + 2) + 3)

Последняя строка эквивалентна ((0 + 1) + 2) + 3 . Это потому, что (fab) совпадает с (a `f` b) вообще, и поэтому ((+) 0 1) в (a `f` b) совпадает с (0 + 1) .

foldr

Так реализуется правильная складка:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)              -- = x `f` foldr f z xs

Правая складка, foldr , ассоциируется справа. То есть:

foldr (+) 0 [1, 2, 3]      -- is equivalent to 1 + (2 + (3 + 0))

Причина в том, что foldr оценивается следующим образом (посмотрите на индуктивный шаг foldr ):

foldr (+) 0 [1, 2, 3]                        --          foldr (+) 0  [1,2,3]
(+) 1 (foldr (+) 0 [2, 3])                   -- 1 +        foldr (+) 0  [2,3]
(+) 1 ((+) 2 (foldr (+) 0 [3]))              -- 1 + (2 +     foldr (+) 0  [3])
(+) 1 ((+) 2 ((+) 3 (foldr (+) 0 [])))       -- 1 + (2 + (3 +  foldr (+) 0 []))
(+) 1 ((+) 2 ((+) 3 0))                      -- 1 + (2 + (3 +            0   ))

Последняя строка эквивалентна 1 + (2 + (3 + 0)) , так как ((+) 3 0) совпадает с (3 + 0) .

Преобразование с помощью `map`

Часто мы хотим преобразовать или преобразовать содержимое коллекции (список или что-то проходящее). В Haskell мы используем map :

 -- Simple add 1
 map (+ 1) [1,2,3]
 [2,3,4]
 
 map odd [1,2,3]
 [True,False,True]
 
 data Gender = Male | Female deriving Show
 data Person = Person String Gender Int deriving Show

 -- Extract just the age from a list of people
 map (\(Person n g a) -> a) [(Person "Alex" Male 31),(Person "Ellie" Female 29)]
 [31,29]

Фильтрация с помощью `filter`

Учитывая список:

 li = [1,2,3,4,5]

мы можем отфильтровать список с предикатом, используя filter :: (a -> Bool) -> [a] -> [a] :

 filter (== 1) li       -- [1]
 
 filter (even) li       -- [2,4]
 
 filter (odd) li        -- [1,3,5]
 
 -- Something slightly more complicated
 comfy i = notTooLarge && isEven
   where 
      notTooLarge = (i + 1) < 5
      isEven = even i
 
 filter comfy li        -- [2]

Конечно, речь идет не только о цифрах:

 data Gender = Male | Female deriving Show
 data Person = Person String Gender Int deriving Show
 
 onlyLadies :: [Person] -> Person
 onlyLadies x = filter isFemale x
   where 
     isFemale (Person _ Female _) = True
     isFemale _ = False
 
 onlyLadies [(Person "Alex" Male 31),(Person "Ellie" Female 29)]
 -- [Person "Ellie" Female 29]

Распаковка и распаковка списков

zip принимает два списка и возвращает список соответствующих пар:

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

> zip [1,3,5] [2,4,6]
> [(1,2),(3,4),(5,6)]

Закрепление двух списков функцией:

zipWith f  []     _      = []
zipWith f  _      []     = []
zipWith f  (a:as) (b:bs) = f a b : zipWith f as bs

> zipWith (+) [1,3,5] [2,4,6]
> [3,7,11]

Распаковка списка:

unzip = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])

> unzip [(1,2),(3,4),(5,6)]
> ([1,3,5],[2,4,6])