На этом шаге мы приведем несколько демонстрационных примеров использования созданной библиотеки.
Приведем текст описанной на предыдущем шаге библиотеки.
-- Библиотека функций для работы с ассоциативными списками, -- содержащими пары типа (Integer,Double). -- Допускаются пары с одинаковыми ключами, т.е. ассоциатив- -- ный список не является типом "отображение" (map). -- -- Авторы: И.А.Кудрявцева, М.В.Швецкий (24.05.2008, -- 10.07.2012) -- ************************************************ module AList (assoc, assoc_if, rassoc, rassoc_if, assFind, assFind', acons, acons1, acons2, pairlis, delpair, putassoc, rekey, redata, bubbleKey, bubbleDate, pKey, pDate) where -- ****************************************************** -- Функционал, выполняющий линейный поиск в ассоциативном -- списке alist пары, для которой при сравнении её fst- -- элемента с ключом key по тесту test результат не равен -- False. -- Если пара элементов, удовлетворяющая тесту, найдена, -- то возвращается список из этой пары; иначе возвращает- -- ся пустой список ------------------------------------- assoc:: Integer -> [(Integer,Double)] -> (Integer -> Integer -> Bool) -> [(Integer,Double)] assoc key alist test | null alist = [] | test (fst (head alist)) key = [head alist] | True = assoc key (tail alist) test --------------------------------------------------------------- -- Функционал, выполняющий линейный поиск в ассоциативном спис- -- ке alist пары, для которой при сравнении её fst-элемента -- по тесту test результат не равен False. -- Если пара элементов, удовлетворяющая тесту, найдена, то воз- -- вращается список из этой пары; иначе - пустой список ------------------------------------------------------- assoc_if:: [(Integer,Double)] -> (Integer -> Bool) -> [(Integer,Double)] assoc_if alist test | null alist = [] | test (fst (head alist)) = [head alist] | True = assoc_if (tail alist) test --------------------------------------------------------------- -- Функционал, выполняющий линейный поиск в ассоциативном спис- -- ке alist пары, для которой при сравнении её snd-элемента -- с ключом key по тесту test результат не равен False. -- Если пара элементов, удовлетворяющая тесту, найдена, то воз- -- вращается список из этой пары; иначе - пустой список ------------------------------------------------------- rassoc:: Double -> [(Integer,Double)] -> (Double -> Double -> Bool) -> [(Integer,Double)] rassoc key alist test | null alist = [] | test (snd (head alist)) key = [head alist] | True = rassoc key (tail alist) test ------------------------------------------------------------- -- Функционал, выполняющий линейный поиск в ассоциативном -- списке alist пары, для которой при сравнении её snd- -- элемента по тесту test результат не равен False. -- Если пара элементов, удовлетворяющая тесту, найдена, -- то возвращается список из этой пары; иначе - пустой -- список -------------------------------------------------- rassoc_if:: [(Integer,Double)] -> (Double -> Bool) -> [(Integer,Double)] rassoc_if alist test | null alist = [] | test (snd (head alist)) = [head alist] | True = rassoc_if (tail alist) test --------------------------------------------------------------- -- Функция возвращает True, если пара (key,date) содержится -- в ассоциативном списке alist -- (с использованием охран) --------------------------------------------------------- assFind:: Integer -> Double -> [(Integer,Double)] -> Bool assFind key date alist | null alist = False | key==fst (head alist)&& date==snd (head alist) = True | True = assFind key date (tail alist) ----------------------------------------------------------- -- Функция возвращает True, если пара (key,date) содержится -- в ассоциативном списке alist -- (с использованием образцов) ---------------------------------------------------------- assFind':: Integer -> Double -> [(Integer,Double)] -> Bool assFind' key date [] = False assFind' key date ((k,d):lst) = k==key && d==date || assFind' key date lst -- ****************************************************** -- Функция, добавляющая пару (x,y) в начало ассоциативно- -- го списка alist. -- В списке могут содержаться данные с тем же ключом x ------------------------------------------------------ acons:: Integer -> Double -> [(Integer,Double)] -> [(Integer,Double)] acons x y alist = (x,y) : alist ---------------------------------------------------------- -- Функция добавляет (без нарушения упорядоченности) новую -- пару (x,y) в числовой ассоциативный список alist, пары -- которого расположены в порядке возрастания ключей ---------------------------------------------------- acons1:: Integer -> Double -> [(Integer,Double)] -> [(Integer,Double)] acons1 x y alist | null alist = [(x,y)] | x>fst (head alist) = head alist : acons1 x y (tail alist) | True = (x,y) : alist ----------------------------------------------------------- -- Функция добавляет (без нарушения упорядоченности) число- -- вую пару (x,y) в ассоциативный список alist, пары кото- -- рого расположены в порядке убывания данных. -- Если пара (x,y) есть в списке, то она не добавляется ------------------------------------------------------- acons2:: Integer -> Double -> [(Integer,Double)] -> [(Integer,Double)] acons2 x y alist | null alist = [(x,y)] | y<snd (head alist) = head alist : acons2 x y (tail alist) | y>snd (head alist) = (x,y) : alist | x==fst (head alist) = acons2 x y (tail alist) | True = head alist : acons2 x y (tail alist) ----------------------------------------------------------- -- Функция конструирует ассоциативный список из списка клю- -- чей lkey и списка данных ldata путём добавления пар -- (head lkey,head ldata) в начало списка alist ----------------------------------------------------- pairlis:: [Integer] -> [Double] -> [(Integer,Double)] -> [(Integer,Double)] pairlis lkey ldata alist | null lkey || null ldata = alist | True = (head lkey,head ldata) : pairlis (tail lkey) (tail ldata) alist -- ********************************************************* -- Функция удаляет все пары с ключом key из -- ассоциативного списка alist ------------------------------------------------------------- delpair:: Integer -> [(Integer,Double)] -> [(Integer,Double)] delpair key alist | null alist = [] | fst (head alist)==key = delpair key (tail alist) | True = head alist : delpair key (tail alist) ------------------------------------------------------------ -- Функция заменяет в ассоциативном списке alist данные, со- -- ответствующие ключу key, на данные dta и возвращает изме- -- нённый ассоциативный список alist --------------------------------------------------- putassoc:: Integer -> Double -> [(Integer,Double)] -> [(Integer,Double)] putassoc key dta alist | null alist = [] | fst (head alist)/=key = head alist : putassoc key dta (tail alist) | True = (fst (head alist),dta) : putassoc key dta (tail alist) -- ************************************************** -- Функция возвращает список ключей по ассоциативному -- списку alist --------------------------------------- rekey:: [(Integer,Double)] -> [Integer] rekey aList = map (\(x,_) -> x) aList ----------------------------------------------------- -- Функция возвращает список данных по ассоциативному -- списку alist --------------------------------------- redata:: [(Integer,Double)] -> [Double] redata aList = map (\(_,y) -> y) aList -- ******************************************************* -- Функция сортирует методом простого обмена ассоциативный -- список aLst по возрастанию ключей ------------------------------------ bubbleKey aLst | null aLst = aLst | True = bubbleKey (reverse (tail (reverse (pKey aLst)))) ++ [head (reverse (pKey aLst))] --------------------------------------------------- -- Вспомогательная функция, реализующая один проход -- с обменами по списку ------------------------- pKey aLst | length aLst<2 = aLst | fst (head aLst)>fst (head (tail aLst)) = head (tail aLst) : pKey (head aLst : tail (tail aLst)) | True = head aLst : pKey (tail aLst) ---------------------------------------------------------- -- Функция сортирует методом простого обмена ассоциативный -- список aLst по возрастанию данных ------------------------------------ bubbleDate aLst | null aLst = aLst | True = bubbleDate (reverse (tail (reverse (pDate aLst)))) ++ [head (reverse (pDate aLst))] --------------------------------------------------- -- Вспомогательная функция, реализующая один проход -- с обменами по списку --------------------------------- pDate aLst | length aLst<2 = aLst | snd (head aLst)>snd (head (tail aLst)) = head (tail aLst) : pDate (head aLst : tail (tail aLst)) | True = head aLst : pDate (tail aLst)
Приведем несколько примеров использования этой библиотеки.
-- Тестирование функций библиотеки AList.hs, предназна- -- ченной для работы с ассоциативными списками, содер- -- жащими пары чисел типа (Integer,Double) -- *************************************** import AList ---------------------------------------------------- test = testAssoc && testAssoc_if && testRassoc && testRassoc_if && testassFind && testAcons && testPairlis && testAcons1 && testAcons2 && testDelpair && testPutassoc && testReKey && testReData && testbKey && testbDate ------------------------------------------ testAssoc = assoc 2 [(1,3.2)] (==) == [] && assoc 2 [(11,3.1),(-2,4.1),(1,2.2)] (<) == [(-2,4.1)] && assoc 2 [(1,3.0),(-2,4.0),(2,1.0)] (==) == [(2,1.0)] && assoc (-22) [(-22,4.0),(1,2.0)] (<=) == [(-22,4.0)] && assoc (-22) [(-22,4.0),(1,2.0),(2,1.0)] (>) == [(1,2.0)] ------------------------------------------------- testAssoc_if = assoc_if [(1,3.0)] (<0) == [] && assoc_if [(11,3.0),(-2,4.0)] (<0) == [(-2,4.0)] && assoc_if [(1,3.0),(-2,4.0),(2,1.0)] (==2) == [(2,1.0)] && assoc_if [(-22,4.0),(1,2.0)] odd == [(1,2.0)] && assoc_if [(-22,4.0),(2,1.0)] even == [(-22,4.0)] ------------------------------------------------------- testRassoc = rassoc 2.0 [(1,3.0)] (==) == [] && rassoc 2.0 [(11,3.0),(-2,-4.0),(1,2.0)] (<) == [(-2,-4.0)] && rassoc 1.0 [(1,3.0),(-2,4.0),(2,1.0)] (==) == [(2,1.0)] && rassoc (-22.0) [(22,-22.0),(1,2.0)] (<=) == [(22,-22.0)] && rassoc (-2.0) [(-2,-2.0),(1,2.0),(2,1.0)] (>) == [(1,2.0)] ----------------------------------------------------- testRassoc_if = rassoc_if [(1,3.0)] (<0.0) == [] && rassoc_if [(11,-3.0),(-2,4.0)] (>0.0) == [(-2,4.0)] && rassoc_if [(1,3.0),(-2,4.0),(2,1.0)] (==1.0) == [(2,1.0)] ----------------------------------------------------------- testassFind = assFind 3 33.0 [(3,33.0),(2,22.0),(4,11.0)] && assFind 2 22.0 [(3,33.0),(2,22.0),(4,11.0)] && assFind 2 22.0 [(2,22.0)] ---------------------------------------------------- -- Демонстрация особенностей вещественной арифметики ---------------------------------------------------- && not (assFind 3 3.0 [(3,7.0),(3,3.000001)]) && assFind 3 3.0 [(3,7.0),(3,3.0000001)] ---------------------------------------------------------- testAcons = acons (-1) (-2.0) [] == [(-1,-2.0)] && acons 1 2.0 [(1,3.0)] == [(1,2.0),(1,3.0)] && acons (-2) 4.0 [(1,3.0),(-2,4.0)] == [(-2,4.0),(1,3.0),(-2,4.0)] ----------------------------------------------------------------- testPairlis = pairlis [1,2,3,4] [11.0,22.0,33.0,44.0] [] == [(1,11.0),(2,22.0),(3,33.0),(4,44.0)] && pairlis [1,2,3] [11.0,22.0,33.0] [(5,55.0),(1,111.0),(3,333.0)] == [(1,11.0),(2,22.0),(3,33.0),(5,55.0), (1,111.0),(3,333.0)] ------------------------------------------------ testAcons1 = acons1 3 33.0 [(1,11.0),(2,22.0)] == [(1,11.0),(2,22.0),(3,33.0)] && acons1 3 33.0 [(1,11.0),(4,44.0)] == [(1,11.0),(3,33.0),(4,44.0)] && acons1 3 33.0 [(4,44.0)] == [(3,33.0),(4,44.0)] && acons1 3 33.0 [(3,1.0)] == [(3,33.0),(3,1.0)] ----------------------------------------------------- testAcons2 = acons2 3 33.0 [] == [(3,33.0)] && acons2 2 22.0 [(2,22.0)] == [(2,22.0)] && acons2 5 55.0 [(44,4.0),(45,3.0),(3,2.0)] == [(5,55.0),(44,4.0),(45,3.0),(3,2.0)] && acons2 3 5.0 [(2,22.0),(4,11.0)] == [(2,22.0),(4,11.0),(3,5.0)] && acons2 3 15.0 [(2,22.0), (4,11.0)] == [(2,22.0),(3,15.0),(4,11.0)] && acons2 3 33.0 [(3,33.0),(2,22.0),(4,11.0)] == [(3,33.0),(2,22.0),(4,11.0)] && acons2 2 22.0 [(3,33.0),(2,22.0),(4,11.0)] == [(3,33.0),(2,22.0),(4,11.0)] --------------------------------------------- && acons2 3 3.0 [(3,7.0),(3,5.0)] == [(3,7.0),(3,5.0),(3,3.0)] && acons2 3 3.0 [(3,7.0),(3,4.0), (3,1.0)] == [(3,7.0),(3,4.0),(3,3.0),(3,1.0)] && acons2 3 3.0 [(3,3.0),(3,3.0),(3,3.0)] == [(3,3.0)] ------------------------------------ -- Построение ассоциативного списка, -- упорядоченного по убыванию данных ------------------------------------ && acons2 1 1.0 (acons2 10 1.0 (acons2 10 2.0 (acons2 5 2.0 (acons2 4 1.0 (acons2 1 3.0 []))))) == [(1,3.0),(5,2.0),(10,2.0),(4,1.0),(10,1.0),(1,1.0)] ------------------------------------------------------------------ testDelpair = delpair 1 [(1,11.0)] == [] && delpair 3 [(1,11.0),(2,22.0),(3,33.0),(4,44.0)] == [(1,11.0),(2,22.0), (4,44.0)] && delpair 4 [(1,11.0),(2,22.0),(3,33.0),(4,44.0)] == [(1,11.0),(2,22.0),(3,33.0)] && delpair 5 [(1,11.0),(2,22.0),(3,33.0),(4,44.0)] == [(1,11.0),(2,22.0),(3,33.0),(4,44.0)] && delpair 5 [(5,11.0),(2,22.0),(5,33.0),(5,44.0)] == [ (2,22.0) ] ---------------------------------------------------------------- testPutassoc = putassoc 2 222.0 [(1,11.0),(2, 22.0),(3,33.0)] == [(1,11.0),(2,222.0),(3,33.0)] && putassoc 2 222.0 [(1,11.0),(3, 33.0),(4,44.0)] == [(1,11.0),(3, 33.0),(4,44.0)] && putassoc 2 10.0 [(1,11.0),(2, 9.0),(3,7.0),(4,5.0)] == [(1,11.0),(2,10.0),(3,7.0),(4,5.0)] && putassoc 4 5.0 [(1,11.0),(3,9.0),(4,7.0)] == [(1,11.0),(3,9.0),(4,5.0)] && putassoc 1 2.0 [(1,11.0)] == [(1,2.0)] --------------------------------------------------------- testReKey = rekey [(1,11.0),(2,22.0),(3,33.0),(4,44.0)] == [1,2,3,4] && rekey [(1,11.0)] == [1] && rekey [] == [] ----------------------------------------------------------- testReData = redata [(1,11.0),(2,22.0),(3,33.0),(4,44.0)] == [11.0,22.0,33.0,44.0] && redata [(1,11.0)] == [11.0] && redata [] == [] ---------------------------------------------------------- testbKey = bubbleKey [(3,0.5),(-1,0.1),(2,0.6),(-1,0.2)] == [(-1,0.1),(-1,0.2),(2,0.6),(3,0.5)] && bubbleKey [(7,-1.0),(6,-2.0),(5,-3.0),(3,-4.0)] == [(3,-4.0),(5,-3.0),(6,-2.0),(7,-1)] && bubbleKey [(7,-1.2),(7,3.4),(7,0.1),(3,10.0)] == [(3,10.0),(7,-1.2),(7,3.4),(7,0.1)] ---------------------------------------------------------- testbDate = bubbleDate [(3,5.5),(0,1.1),(2,6.6),(1,2.2)] == [(0,1.1),(1,2.2),(3,5.5),(2,6.6)] && bubbleDate [(80,0.7),(2,0.6),(-22,0.5),(12,-3.1)] == [(12,-3.1),(-22,0.5),(2,0.6),(80,0.7)]
Еще один демонстрационный пример.
-- Демонстрация использования библиотеки функций для работы -- с ассоциативными списками (файл AList.hs). -- Используется функция -- -- putStr:: String -> IO(), -- -- выводящая на экран заданную строку -- ********************************** import AList --------------------- lst1 = [1,-5,3,-5,10] lst2 = [1.0,15.0,2.0,13.0,11.0] ------------------------------- test = putStr ("Список lst1: " ++ show lst1 ++ "\n" ++ "Список lst2: " ++ show lst2 ++ "\n" ++ ------------------------------------------- "Построение ассоциативного списка aLst " ++ "из списков lst1 и lst2: \n" ++ "aLst=" ++ show aLst ++ "\n\n" ++ ----------------------------------------------------- "Проверка составных частей ассоциативного списка " ++ "aLst. \n" ++ "Список ключей aLst: " ++ show (rekey aLst) ++ "\nСписок данных aLst: " ++ show (redata aLst) ++ ------------------------------------------------------ "\n\nНайдём первый ключ, соответствующий данным 2.0: " ++ show (fst (head (rassoc 2.0 aLst (==)))) ++ -------------------------------------------------- "\nНайдём данные, соответствующие ключу (-5): " ++ show (find_dta (-5) aLst) ++ "\n\n" ++ ------------------------------------------------- "Добавим в начало ассоциативного списка aLst " ++ "пару (3,2.0): " ++ "\naLst1=" ++ let aLst1 = acons 3 2.0 aLst in show aLst1 ++ "\n\n" ++ --------------------------------------------------- "Изменим в ассоциативном списке aLst1 данные с " ++ "ключом (-5) на 0: " ++ "\naLst2=" ++ let aLst2 = putassoc (-5) 0.0 aLst1 in show aLst2 ++ "\n\n" ++ ---------------------------------------------------- "Удалим из ассоциативного списка aLst2 все пары " ++ "элементов c ключами -5 и 3: " ++ "\naLst3=" ++ let aLst3 = delpair 3 (delpair (-5) aLst2) in show aLst3 ++ "\n\n" ++ --------------------------------------------------- "Добавим в числовой ассоциативный список aLst3 " ++ "пару элементов (10,0.0)\nс сохранением порядка " ++ "возрастания ключей: \n" ++ show (acons1 10 0.0 aLst3)) --------------------------------- where aLst = pairlis lst1 lst2 [] ----------------------------------------------------- -- Нахождение данных, соответствующих заданному ключу ----------------------------------------------------- find_dta k l | null l || null (assoc k l (==)) = [] | True = snd (head (assoc k l (==))) : find_dta k (delpair1 k l) ----------------------------------------------- -- Удаление первого вхождения пары с ключом key -- в ассоциативный список alist --------------------------------------- delpair1 key alist | null alist = alist | fst (head alist)==key = tail alist | True = head alist : delpair1 key (tail alist)
На следующем шаге мы приведем перечень задач для самостоятельного решения.
