Шаг 127.
Основы языка Haskell. Абстрактные типы данных (АТД). Ассоциативные списки на базе списка пар. Использование созданной библиотеки

    На этом шаге мы приведем несколько демонстрационных примеров использования созданной библиотеки.

    Приведем текст описанной на предыдущем шаге библиотеки.

   -- Библиотека функций для работы с ассоциативными списками,
   -- содержащими пары типа (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)
Файл с примерами можно взять здесь.

    На следующем шаге мы приведем перечень задач для самостоятельного решения.




Предыдущий шаг Содержание Следующий шаг