我正在努力深入理解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
。这采用了堆栈数据结构的实现,并生成了一个解析器,该解析器将具体的后缀(“反向修饰”)表示法读取为抽象语法(由下游的计算器模块评估),反之亦然。现在,我一直在使用一个标准的堆栈接口,该接口提供了一个多态堆栈类型和在其上进行操作的函数数量:
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
?(如果您已经阅读了本文,则非常感谢!)
正如您所发现的,在SML和OCaml中,参数多态与函子/模块之间存在紧张关系。这主要是由于模块的“两种语言”性质以及缺乏即席多态性所致。1ML和模块化隐式都为该问题提供了不同的解决方案。第一个通过统一两种参数,第二个通过在需要时激发一些特定的多态性。
回到实际考虑。使用函子,可以很容易地(但是冗长/讨厌)使给定的数据结构单一化。这是一个示例(在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
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句