В функции
fun exists dict key =
case dict of
[] => []
| (k, _ )::rep => if k = key
then true
else exists rep key
Я обнаружил две проблемы:
- Невозможно вернуть
[] в одном месте и trueв другом. - Вместо
if P then true else Q напишите P orelse Q.
Вы используете :>, что означает, что модуль непрозрачен ,так что вы можете получить доступ только к тем вещам, которые указаны в подписи.Внутреннее представление списка не упоминается в подписи, поэтому вы не можете ссылаться на dict как список, даже если вы знаете, что это так.Это особенность.
Я бы, вероятно, назвал exists для member, поскольку List.exists является предикатом высшего порядка, например, List.exists (fn x => x > 5) [3, 6, 9].Вы также можете отклониться от любого стандартного наименования библиотеки и сказать containsKey и containsValue, или что-то в этом роде.
Помимо функции insert, которую предложил molbdnilo, вы можете захотеть иметь функцию fromList.
Вот измененная версия (комментарии для краткости опущены, но я думаю, что ваши комментарии хороши!):
signature DICTIONARY =
sig
type (''key, 'value) dict
val empty: (''key, 'value) dict
val member: ''key -> (''key, 'value) dict -> bool
val insert: (''key * 'value) -> (''key, 'value) dict -> (''key, 'value) dict
val fromList: (''key * 'value) list -> (''key, 'value) dict
end
structure Dictionary :> DICTIONARY =
struct
type (''key, 'value) dict = (''key * 'value) list
val empty = []
fun member key [] = false
| member key ((key2, _)::dict) =
key = key2 orelse member key dict
fun insert (key, value) [] = [(key, value)]
| insert (key, value) ((key2, value2)::dict) =
if key = key2
then (key, value) :: dict
else (key2, value2) :: insert (key, value) dict
fun fromList pairs = foldl (fn (pair, dict) => insert pair dict) empty pairs
end
Но поскольку вы создаете модуль словаря,две вещи, которые вы хотите рассмотреть:
- Позволяют использовать какое-то двоичное дерево в качестве внутреннего представления, требуя, чтобы ключи были упорядочены , а не по сравнениюна равенство .
- Поскольку Standard ML не имеет специального синтаксиса, такого как
''key, для выражения того, что что-то можно заказать (Хаскелл обобщает это как классы типов , но Standard ML имееттолько специальный синтаксис ''key), это хороший случай для использования функторов , которое является именем модулей более высокого порядка, также называемых параметризованными модулями.
HeВот пример подписи, функтора и структуры, которые вы можете заполнить:
signature ORD = sig
type t
val compare : t * t -> order
end
signature DICT = sig
type key
type 'value dict
val empty: 'value dict
val member: key -> 'value dict -> bool
val insert: key * 'value -> 'value dict -> 'value dict
val fromList: (key * 'value) list -> 'value dict
end
functor Dict (Ord : ORD) :> DICT = struct
type key = Ord.t
type 'value dict = (key * 'value) list
val empty = ...
fun member _ _ = raise Fail "not implemented"
fun insert _ _ = raise Fail "not implemented"
fun fromList _ = raise Fail "not implemented"
end
На этом этапе вы можете изменить type 'value dict на использование двоичного дерева, и когда вам нужно решить, идти ли налево или направов этом двоичном дереве вы можете написать:
case Ord.compare (key1, key2) of
LESS => ...
| EQUAL => ...
| GREATER => ...
И когда вам нужен словарь, в котором ключ имеет определенный тип или тип , вы можете создать модуль с помощью этого функтора:
structure IntDict = Dict(struct
type t = int
val compare = Int.compare
end)
structure StringDict = Dict(struct
type t = string
val compare = String.compare
end)
См. Также Примеры стандартных функторов ML для дополнительных примеров.