На этом шаге мы рассмотрим функции для работы с A-списками.

В работе с ассоциативными списками часто необходимо уметь:

(1) осуществлять поиск данных по ключу;
(2) обновлять данные.

В языке Haskell отсутствуют встроенные функции для обработки списка конструкции, названной нами ассоциативным списком.

Замечание. В версии muLISP85 языка LISP для работы с ассоциативными списками имеются специальные функции (ASSOC, ASSOC-IF, RASSOC, RASSOC-IF, ACONS).

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

1. Функция

   assoc key alist test

выполняет линейный поиск в ассоциативном списке alist пары элементов, для которой при сравнении её fst-элемента с ключом key по тесту test признак не равен False.

Если пара элементов, удовлетворяющая тесту, найдена, то эта пара возвращается в виде списка; в противном случае возвращается пустой список.

Например:

   > assoc 2 [(1,0.1),(2,0.6),(2,0.23)] (==)
   [(2,0.6)]

   > assoc 22 [(-1,3.0),(2,-4.0),(-2,6.0)] (==)
   []

   > assoc 22 [(-1,3.0),(23,-4.1),(-2,6.2)] (>=)
   [(23,-4.1)]

   > assoc 22 [(-1,3.3),(23,-4.4),(-2,6.6)] (<=)
   [(-1,3.3)]

2. Функция

   assoc_if alist test

ищет в ассоциативном списке alist пару, для которой признак проверки её fst-элемента по тесту test не есть False.

Если пара, удовлетворяющая тесту, найдена, то эта она возвращается в виде списка; в противном случае возвращается пустой список.

Например:

   > assoc_if [(1,3.0)] (<0)
   []

   > assoc_if [(-22,4.1),(1,2.25)] odd
   [(1,2.25)]

   > assoc_if [(-22,4.34),(2,1.23)] even
   [(-22,4.34)]

3. Функция

   rassoc key alist test

(rassoc - от англ. слов "Reverse" и "ASSOCiate") выполняет линейный поиск в ассоциативном списке alist пары, для которой при сравнении её snd-элемента с ключом key по тесту test признак не равен False.

Если пара, удовлетворяющая тесту, найдена, то она возвращается в виде списка; в противном случае возвращается пустой список.

Например:

   > rassoc 2.0 [(1,3.2)] (==)
   []

   > rassoc -2.0 [(11,3.0),(-3,-4.0),(1,2.0)] (<)
   [(-3,-4.0)]

   > rassoc (-22.0) [(22,-22.0),(1,2.0)] (<=)
   [(22,-22.0)]

4. Функция

   rassoc_if alist test

выполняет в ассоциативном списке alist поиск пары, для которой признак проверки её snd-элемента по тесту test не равен False.

Например:

   > rassoc_if [(1,3.2)] (<0)
   []

   > rassoc_if [(1,3.2),(-2,4.5),(2,1.0)] (==1.0)
   [(2,1.0)]

5. Функция

   acons x y alist

добавляет новую пару (x,y) в начало ассоциативного списка alist, при этом в списке уже могут быть данные с тем же ключом.

Эта функция позволяет обновлять и использовать ассоциативный список "в режиме стека".

Например:

   > acons (-1) (-2.3) []
   [(-1,-2.3)]

   > acons 1 2.1 [(1,3.0)]
   [(1,2.1),(1,3.0)]

   > acons (-2) 4.2 [(1,3.1),(-2,4.2)]
   [(-2,4.2),(1,3.1),(-2,4.2)]

6. Функция

   pairlis lkey ldata alist

позволяет сконструировать A-список из списка ключей lkey и списка данных ldata путём добавления новых пар в начало существующего ассоциативного списка alist.

Например:

   > 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)])

7. Функция

   rekey alist

возвращает список ключей по известному ассоциативному списку AList:

   AList=[(X₁, E₁),...,(X_k,E_k)] --> [X₁,...,X_k].

Например:

   > rekey [(1,11.1),(2,22.2),(3,33.3),(4,44.4)]
   [1,2,3,4]

   > rekey [(1,11.34)]
   [1]

   > rekey []
   []

8. Функция

   redata alist

возвращает список данных по известному ассоциативному списку AList:

   AList=[(X₁, E₁),...,(X_k,E_k)] --> [E₁,...,E_k].

Например:

   > redata [(1,0.11),(2,0.22),(3,0.33),(4,0.44)]
   [0.11,0.22,0.33,0.44]

   > redata [(1,11.2)]
   [11.2]

   > redata []
   []

9. Функция

   acons1 x y alist

позволяет добавить новую (!) пару элементов (x,y), где x и y - числа, в числовой ассоциативный список alist, пары элементов которого расположены в порядке возрастания значения их ключей.

Например:

   > acons1 3 33.0 [(1,11.0),(2,22.0)]   > acons1 3 0.33 [(4,0.44)]
   [(1,11.0),(2,22.0),(3,33.0)]          [(3,0.33),(4,0.44)]

   > acons1 3 3.3 [(1,1.1),(4,4.4)]      > acons1 3 3.3 [(3,1.9)]
   [(1,1.1),(3,3.3),(4,4.4)]             [(3,3.3),(3,1.9)]

10. Функция

   acons2 x y alist

позволяет добавить новую (!) пару элементов (x,y), где x и y - числа, в числовой ассоциативный список alist, пары элементов которого расположены в порядке убывания значения их данных.

Например:

   -- Добавление в начало
   > acons2 3 33.0 []
   [(3,33.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 15.2 [(2,22.1),(4,11.45)]
   [(2,22.1),(3,15.2),(4,11.45)]

   -- Добавление пары, которая уже есть в списке
   > acons2 2 22.0 [(3,33.0),(2,22.0),(4,11.0)]
   [(3,33.0),(2,22.0),(4,11.0)]

11. Функция

   delpair key alist

позволяет удалять пары элементов с заданным ключом key из ассоциативного списка alist.

Например:

   > delpair 1 [(1,11.1)]
   []

   > delpair 3 [(1,11.0),(2,-22.0),(3,33.0),(4,44.0)]
   [(1,11.0),(2,-22),(4,44.0)]

   > delpair 4 [(1,1.1),(4,2.2),(3,3.3),(4,4.4)]
   [(1,1.1),(3,3.3)]

   > delpair 5 [(1,0.11),(2,0.22),(3,0.33),(4,0.44)]
   [(1,0.11),(2,0.22),(3,0.33),(4,0.44)]

12. Функция

   putassoc1 key data alist

изменяет в ассоциативном списке alist данные, соответствующие ключу key, на данные data; возвращает измененный ассоциативный список alist.

Например:

   > putassoc1 2 222.2 [(1,1.1),(2,2.2),(3,3.3),(2,1.2)]
   [(1,1.1),(2,222.2),(3,3.3),(2.222.2)]

   > putassoc1 2 (-222.12) [(1,0.11),(3,0.33),(4,0.44)]
   [(1,0.11),(3,0.33),(4,0.44)]

13. Функция

   putassoc2 key data alist

изменяет в ассоциативном списке alist, упорядоченном по убыванию данных в парах элементов, данные, соответствующие ключу key, на данные data; возвращает измененный ассоциативный список alist.

Например:

   > putassoc2 2 (-10.0) [(1,11.1),(2,9.1),(3,7.1),(4,5.1)]
   [(1,11.1),(2,-10.0),(3,7.1),(4,5.1)]

   > putassoc2 4 5.2 [(1,11.0),(3,9.0),(4,7.0)]
   [(1,11.0),(3,9.0),(4,5.2)]

   > putassoc2 1 2.0 [(1,11.11)]
   [(1,2.0)]

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

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