types - 设计模块时如何决定是在类型级别还是模块级别进行参数化？

Question

我正在努力深入了解 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模块提供
必须受限于仿函数中提供的类型的函数
参数，但通过相同的参数化，它们能够
包含有关内部结构和关系的特定信息
他们的目标类型。

很容易想象我们想要设计一个替代家庭的情况
列表模块，使用仿函数将类型和其他值参数化为
提供具有更复杂结构的类似列表的数据类型:例如，指定
有序列表的数据类型，或使用自平衡二进制表示列表
搜索树。

创建模块时，我认为也很容易识别何时会
能够提供多态函数以及何时需要参数化
在某些类型上。对我来说，更困难的是弄清楚哪种
在处理更下游的事情时应该依赖的模块。

一般而言，我的问题是:当我设计一个系统时
各种相关的模块，我如何确定是否围绕模块进行设计
提供使用仿函数生成的多态函数或模块
在类型和值上参数化？

我希望通过下面的例子来说明这个困境以及为什么它很重要，
取自我正在做的一个玩具项目。

我有一个 functor PostFix (ST:STACK) : CALCULATOR_SYNTAX .这需要一个
堆栈数据结构的实现并产生一个解析器，读取
将具体的后缀(“反向抛光”)符号转换为抽象语法(要
由下游的计算器模块评估)，反之亦然。现在，我已经
使用提供多态堆栈类型的标准堆栈接口(interface)和
对其进行操作的函数数:

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 ?

一般来说，有没有办法思考两者之间的关系
可以帮助我在 future 捕捉/预测这种事情的模块？

(如果你已经读到这里了。非常感谢!)

Answer 1

正如您所发现的，SML 和 OCaml 中的参数多态性和仿函数/模块之间存在紧张关系。这主要是由于模块的“两种语言”性质以及缺乏特别的多态性。 1ML和 modular implicits两者都为该问题提供了不同的解决方案。第一个是通过统一两种参数化，第二个是在需要时允许一些特殊的多态性。

回到实际考虑。使用仿函数，对给定的数据结构进行单态化相当容易(但冗长/烦人)。这是一个示例(在 OCaml 中)。有了这个，您仍然可以编写通用实现并在以后专门化它们(通过提供打印功能)。

module type POLYSTACK = 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
  val toString : ('a -> string) -> 'a stack -> string
end

module type STACK = sig
  type elt
  type t
  exception EmptyStack

  val empty : t
  val isEmpty : t -> bool

  val push : (elt * t) -> t
  val pop  : t -> t
  val top  : t -> elt
  val popTop : t -> t * elt
  val toString : t -> string
end

module type PRINTABLE = sig
  type t
  val toString : t -> string
end

module Make (E : PRINTABLE) (S : POLYSTACK)
  : STACK with type elt = E.t and type t = E.t S.stack
= struct
  type elt = E.t
  type t = E.t S.stack
  include S
  let toString = S.toString E.toString
end

module AddLogging (S : STACK)
  : STACK with type elt = S.elt and type t = S.t
= struct
  include S
  let push (x, s) =
    let s' = S.push (x, s) in print_string (toString s') ; s'
end