В OCaml, можно ли определить карту в терминах Set?

Question

Я реализовал представление наборов (сбалансированных деревьев поиска) в OCaml. Это на самом деле функтор Make подписи

module Make : 
    functor (T : ORDERED_TYPE) -> 
sig 
    type elt = T.t 
    type t 
    val empty : t 
    val cons : elt -> t -> t 
    val delete : elt -> t -> t 
    val mem : elt -> t -> bool 
    val cardinal : t -> int 
end 

где

module type ORDERED_TYPE = sig type t val compare : t -> t -> int end 

Теперь я хотел бы реализовать словарь как Map в стандартной библиотеке. Он должен иметь подпись, как

module Make: functor (T : ORDERED_TYPE) -> sig 
    type key = T.t 
    type +'a t 
    ... 
end 

t где тип словарей.

Реализация сбалансированных поисковых деревьев снова не изящна, поэтому я хочу определить словари в терминах множеств, реализованных как функтор выше. Я могу это сделать?

Answer 1

Кажется, что карта - это (частичная) функция, представляющая собой набор упорядоченных пар. Если вы правильно определите свою функцию сравнения, я думаю, что это можно сделать. Возможно, вам придется добавить функцию к интерфейсу Set для учета того факта, что два значения могут сравниваться как равные для целей членства, но фактически не равны. Невозможно определить функцию поиска для карты с текущим интерфейсом.

Answer 2

Как отметил Джеффри, интерфейс Set не достаточно экспрессивный, чтобы удобно реализовать Map поверх него. Было бы проще реализовать Set от Map, определяя наборы как карты от ключей до значения единицы.

Еще одна возможность, которую я бы рекомендовал, - сначала выставить модуль сбалансированных поисковых деревьев без инкапсуляции с единственной целью обеспечить эффективную структуру данных, которая полностью раскрывается интерфейсом. Затем вы можете повторно использовать его для любой структуры данных, какой вам нравится, в том числе Map и Set, без необходимости играть в игры, чтобы определить один в другой. Это может быть не очень важно в этом случае (определение Set от Map является разумным для большинства целей), но, на мой взгляд, это лучший дизайн в общем случае.

Вкратце: если вы хотите повторно использовать реализации, затем выведите «модули реализации» и определите свои «интерфейсные модули» поверх них.

Answer 3

Как другие уже отмечали, есть по крайней мере две причины, почему вы не можете реализовать запрашиваемую карту функтор на вершине данного набора:

1. набор сигнатур обеспечивает никакого способа не найти в " равный "в заданном множестве.
2. И даже если бы это произошло, вы не могли хранить значения там полиморфно, как требуется тип 'a map.

Вы уверены, что задача требует, чтобы вы реализовали карты поверх комплектов? Может быть, вы просто должны их реализовать как комплектов?

Answer 4

Ну, на самом деле ЯВЛЯЕТСЯ равно оператора там - сравнить функции от заказанного типа.

Так определить свой собственный модуль для типа ключ/значение, который принимает только в сравнении ключ-часть:

module Keyvalue = struct 
    type t = ('a * 'b) 
    let compare x y = Pervasives.compare (fst x) (fst y) 
end 

, и вы сделали. Проблема в том, что ваш Набор не позволяет вам получать его значения; нет получить или свернуть функция - это imho действительно ограничивает такую ​​структуру данных. Если разрешено шарить с реализации Set, вам нужно добавить функцию получить:

module Set = sig 
    ... 
    get : t -> elt -> elt 
end 

, который будет возвращать только попросил элемента. Если вы берете второй элемент возвращаемого кортежа, у вас есть значение с оригинала ключ/значение пара.