Сохранение нулевого значения в кортежей списка в sml

Question

Я хочу создать структуру данных типа карты, используя список, имеющий спецификацию: (строка * int), где первый элемент является ключевым, а второй - значением. Первоначально, когда я создаю эту карту, я просто хочу дать ключ без значения. Как я могу передать значение NULL в этом случае? Например, мне нужно что-то вроде этого при инициализации:

val gamma = [("a",_),("b",_),("c",_)] :(string*int) list 

Конечно, я должен быть в состоянии изменить значение, соответствующее определенному ключу. Например, я должен быть в состоянии изменить

[("a",_),("b",_),("c",_)] 

, скажу что-то вроде:

[("a",20),("b",30),("c",40)] 

Answer 1

Если все в списке действительного ints строго положительно, вы можете использовать 0 как нулевое значение, или, возможно, ~1, если 0 действителен, но негативов нет. В противном случае вы можете использовать int option. Что-то вроде:

fun set key value [] = [] 
| set key value ((k,v)::pairs) = 
     if k = key then (k, SOME value) :: pairs 
     else (k,v) :: (set key value pairs) 

fun lookup key ((k,v)::pairs) = 
     if k = key then v else lookup key pairs 

fun initDict keys = map (fn k => (k,NONE)) keys; 

Тогда, например:

- val gamma = initDict ["a","b","c"]: (string * int option) list; 
val gamma = [("a",NONE),("b",NONE),("c",NONE)] : (string * int option) list 

Вы можете "изменить" значения, как таким образом:

= set "b" 30 gamma; 
[("a",NONE),("b",SOME 30),("c",NONE)] : (string * int option) list 

Значения можно читать, как это:

- lookup "a" gamma; 
val it = NONE : int option 
- lookup "b" gamma; 
val it = SOME 30 : int option 

Отметьте, что lookup thr ows ошибка, если ключ не находится в словаре. Поскольку мы используем NONE как нулевое значение для записей, он не может также функционировать как флаг для отсутствия ключа.

Фактические значения могут быть извлечены из вариантов с использованием valOf оператора:

- valOf (lookup "b" gamma); 
val it = 30 : int 

пугают кавычки «изменение» выше были, потому что при таком подходе set строит новый список и связывает его с именем gamma вместо изменения gamma на месте. Если этот список вообще большой, это (а также постоянный линейный поиск по списку) станет довольно неэффективным. На каком-то этапе вы можете начать использовать изменяемые структуры данных (например, отсортированные массивы refs).