Lists.md

Работа със списъци

Списъкът е основна структура данни във функционалните езици. Затова и съществуват множество функции, които правят работата с тях по-лесна. Познаването и използването на тези функции спомага за по-лесната взаимо-работа с други хора и по-малко време отделено в преоткриване на колелото.

Ще дефинираме следните функции върху списъци от числа, но алтернативи със същите имена се намират в пакета Data.List и работят върху списъци от произволен тип. Най-често ползваните от тях са налична дори без импортирането на Data.List, тъй като са толкова основни, че са включени в Prelude - модулът, предоставящ "вградените" типове и операции.

Документация на Data.List

Няколко думи за тестване

Тази задача има базови Unit tests. Те се намират в ListTests.hs и следват като конвенция името на фунцкията с добавено Test отзад.

Пр: null -> nullTest.

За да ги пуснете, заредете файла ListTests.hs в ghci и използвайте:

putStrLn (runTests [nullTest, lengthTest]) за да изпълните тестовете за null и length съответно.

putStrLn (runTests allTests) изпълнява всички тестове.

Основни Операции

head

head :: [Int] -> Int

Взима първия елемент на списъка. Ако списъкът е празен, хвърля грешка.

> head [1, 2, 3]
1

> head []
** Exception: empty list

tail

tail :: [Int] -> [Int]

Връща опашката на списъка. Ако списъкът е празен, хвърля грешка.

> tail [1, 2, 3]
[2, 3]

> tail []
** Exception: empty list

append

append :: [Int] -> [Int] -> [Int]

Слепва два списъка. Стандартната операция за append от Prelude е операторът ++.

> append [1, 2, 3] [4, 5, 6]
[1, 2, 3, 4, 5, 6]

> [1, 2, 3] ++ [4, 5, 6]
[1, 2, 3, 4, 5, 6]

elementAt

elementAt :: Int -> [Int] -> Int

Връща n-тия елемент от списък. Ако списъкът е по-къс или индексът е отрицателен, хвърля грешка. Стандартният оператор от Prelude е !!.

> elementAt 0 [1, 2, 3]
1

> elementAt 4 [1, 2, 3]
** Exception: index too large

> [1, 2, 3, 4] !! 1
2

null

null :: [Int] -> Bool

Проверява дали подаденият списък е празен.

> null [1, 2, 3]
False

> null []
True

length

length :: [Int] -> Int

Връща големината на списъка.

> length [1, 2, 3]
3

> length []
0

Подсписъци

take

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

Взима първите n елемента от списък. Ако n е отрицателно връща празен списък. Ако списъкът е по-къс, взима възможно най-голям брой елементи, без да хвърля грешки.

> take 2 [1, 2, 3]
[1, 2]

> take 5 []
[]

drop

drop :: Int -> [Int] -> [Int]

Премахва първите n елемента от списък. Ако n е отрицателно връща списъка непроменен. Ако списъкът е по-къс, премахва възможно най-голям брой елементи, без да хвърля грешки.

> drop 2 [1, 2, 3]
[3]

> drop 5 []
[]

Търсене на елемент в списък

elem

elem :: Int -> [Int] -> Bool

Проверява дали подаденият елемент е част от списъка. Връща True ако да.

> elem 2 [1, 2, 3]
True

> elem 5 []
False

Трансформации

reverse

reverse :: [Int] -> [Int]

Връща нов списък с елементите от първия в обратен ред.

> reverse [1, 2, 3]
[3, 2, 1]

concat

concat :: [[Int]] -> [Int]

"Опростява" списък от списъци до списък, като слепва вложените списъци.

> concat []
[]

> concat [[1, 2, 3], [4, 5, 6]]
[1, 2, 3, 4, 5, 6]

Други често използвани операции

replicate

replicate :: Int -> Int -> [Int]

Създава списък от даден елемент x повторен n пъти.

> replicate 1 5
[5]

> replicate 4 1
[1, 1, 1, 1]

interleave

interleave :: [Int] -> [Int] -> [Int]

Кръстосва два списъка. Резултатният списък взима елемент първо от първия, после от втория, докато не изчерпи елементите на по-късият списък.

> interleave [1, 2, 3] [4, 5, 6]
[1, 4, 2, 5, 3, 6]

> interleave [1, 2] [3, 4, 5]
[1, 3, 2, 4]

sum

sum :: [Int] -> Int

Връща сумата на числата в подадения списък.

> sum []
0

> sum [1, 2, 3]
6

maximum

maximum :: [Int] -> Int

Връща стойността на най-голямото число в списъка.

> maximum [1, 2, 3]
3

> maximum []
** Exception: empty list

Списъци като множества

nub

nub :: [Int] -> [Int]

Премахва повтарящите се елементи от подадения списък.

> Data.List.sort (nub [1, 2, 3, 2, 4])
[1, 2, 3, 4]

> Data.List.sort (nub [])
[]

delete

delete :: Int -> [Int] -> [Int]

Премахва първото срещане на подадения елемент от списъка.

> delete 2 [1, 2, 2, 3, 4]
[1, 2, 3, 4]

> delete 5 [1, 2, 3, 4]
[1, 2, 3, 4]

difference

difference :: [Int] -> [Int] -> [Int]

Връща всички елементи от първия списък xs, които не са налични във втория ys.

ВАЖНО: Двата списъка не са стриктно множества, a могат да имат и повтарящи се елементи. В такъв случай, ако елемента x се повтаря n пъти в xs, то в резултата x трябва да присъства n - m пъти, където m е срещанията на x в ys.

> difference [1, 2, 3] [1, 2]
[3]

> difference [1, 2, 2, 2, 3, 4] [1, 2, 2, 3, 3]
[2, 4]

union

union :: [Int] -> [Int] -> [Int]

Връща всички елементи на първия списък xs, като към тях са добавени и елементите на втория ys, които xs не съдържа.

ВАЖНО: Ако има повторения на елементи в xs, те присъстват в изхода непроменени. Ако има повторения в ys те се добавят еднократно към резултата.

> Data.List.sort (union [1, 2, 3] [1, 2, 3, 4])
[1, 2, 3, 4]

> Data.List.sort (union [1, 2, 2] [3, 3])
[1, 2, 2, 3]

intersect

intersect :: [Int] -> [Int] -> [Int]

Връща всички елементи от първия списък xs, които са налични и във втория ys.

ВАЖНО: Ако даден елемент в xs се повтаря и е също наличен в ys, то той се повтаря и в изхода.

> intersect [1, 2, 3] [1, 2, 3, 4]
[1, 2, 3]

> intersect [1, 2, 2] [2, 3]
[2, 2]