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

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

(Мне жаль, что я еще не знаю достаточно, чтобы поставить этот вопрос более кратко.)

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

Готовый пример этого различия можно найти в сравнении модулей, которые реализуютLIST подпись с теми, которые реализуютORD_SET, МодульList:LIST предоставляет множество полезных функций, параметризованных для любого типа. Как только мы определили или загрузилиList Модуль, мы можем легко применять любые функции, которые он предоставляет, чтобы создавать, манипулировать или проверять списки любого типа. Например, если мы работаем как со строками, так и с целыми числами, мы можем использовать один и тот же модуль для создания и манипулирования значениями обоих типов:

val strList = List.@ (["a","b"], ["c","d"])
val intList = List.@ ([1,2,3,4], [5,6,7,8])

С другой стороны, если мы хотим иметь дело с упорядоченными наборами, дело обстоит иначе: упорядоченные множества требуют, чтобы отношение упорядочения сохранялось над всеми их элементами, и не может быть единой конкретной функции.compare : 'a * 'a -> order производя это отношение для каждого типа. Следовательно, нам нужен другой модуль, удовлетворяющийORD_SET подпись для каждого типа мы хотим поместить в упорядоченные множества. Таким образом, чтобы создать или управлять упорядоченными наборами строк и целых чисел, мы должны реализовать различные модули для каждого типа [1]:

structure IntOrdSet = BinarySetFn ( type ord_key = int
                                    val compare = Int.compare )
structure StrOrdSet = BinarySetFn ( type ord_key = string
                                    val compare = String.compare )

И тогда мы должны использовать функцию подбора из соответствующего модуля, когда мы хотим работать с данным типом:

val strSet = StrOrdSet.fromList ["a","b","c"]
val intSet = IntOrdSet.fromList [1,2,3,4,5,6]

Здесь есть довольно простой компромисс:LIST модули предоставляют функции, которые варьируются в зависимости от любого типа, который вы пожелаете, но они не могут использовать какие-либо отношения между значениями какого-либо конкретного типа;ORD_SET Модули предоставляют функции, которые обязательно ограничены типом, указанным в параметре functors, но благодаря той же параметризации они способны включать в себя конкретную информацию о внутренней структуре и отношениях своих целевых типов.

Легко представить себе случаи, когда мы хотели бы разработать альтернативное семейство модулей списков, используя функторы для параметризации типов и других значений, чтобы обеспечить типы данных в виде списков с более сложной структурой: например, чтобы указать тип данных для упорядоченного списка или для представления списков с использованием самобалансирующихся бинарных деревьев поиска.

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

В общих чертах, мой вопрос заключается в следующем: когда я проектирую систему различных модулей, как я могу выяснить, следует ли проектировать модули, предоставляющие полиморфные функции или модули, созданные с использованием функторов, параметризованных по типам и значениям?

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

у меня естьfunctor PostFix (ST:STACK) : CALCULATOR_SYNTAX, Это берет реализацию структуры данных стека и создает синтаксический анализатор, который считывает конкретную нотацию постфикса («обратная полировка») в абстрактный синтаксис (который будет оценен модулем калькулятора в нисходящем направлении), и наоборот. Теперь я использовал стандартный интерфейс стека, который обеспечивает полиморфный тип стека и количество функций для работы с ним:

signature STACK =
sig
    type 'a stack
    exception EmptyStack

    val empty : 'a stack
    val isEmpty : 'a stack -> bool

    val push : ('a * 'a stack) -> 'a stack
    val pop  : 'a stack -> 'a stack
    val top  : 'a stack -> 'a
    val popTop : 'a stack -> 'a stack * 'a
end

Это прекрасно работает и дает мне некоторую гибкость, так как я могу использовать стек на основе списка, векторный стек или что-то еще. Но, скажем, я хочу добавить простую функцию регистрации в модуль стека, чтобы каждый раз, когда элемент помещался в стек или извлекался из него, он выводил текущее состояние стека. Теперь мне понадобитсяfun toString : 'a -> string для типа, собранного в стеке, и это, как я понимаю, не может быть включено вSTACK модуль. Теперь мне нужно запечатать тип в модуль и параметризовать модуль поверх типа, собранного в стеке, иtoString функция, которая позволит мне создать печатное представление собранного типа. Так что мне нужно что-то вроде

functor StackFn (type t
                 val toString: t -> string ) =
struct
   ...
end

и это будетне создать модуль, соответствующийSTACK подпись, так как она не обеспечивает полиморфный тип. Таким образом, я должен изменить подпись, необходимую дляPostFix функтор. Если у меня много других модулей, я должен также поменять их все. Это может быть неудобно, но реальная проблема заключается в том, что я больше не могу использовать мой простой список или векторSTACK модули вPostFix функтор, когда яне хочу войти. Теперь, похоже, мне нужно вернуться и переписать эти модули, чтобы они также были запечатаны.

Итак, чтобы вернуться, расширить и (к счастью) закончить мой вопрос:

Есть ли способ указать сигнатуру модулей, созданныхStackFn так что они в конечном итоге как "особые случаи"STACK?В качестве альтернативы, есть ли способ написания подписи дляPostFix модуль, который позволит как модули, произведенныеStackFn и те, которые удовлетворяютSTACK?Вообще говоря, есть ли способ размышления об отношениях между модулями, которые помогли бы мне уловить / предвидеть подобные вещи в будущем?

(Если вы читали это далеко. Большое спасибо!)