'如何正确使用高阶函子？' 或者"如何与funsigs一起享受真正的乐趣？"

Question

动机

对于我的生活,我无法弄清楚如何在SML/NJ中使用更高阶的仿函数到任何实际的目的.

根据 SML/NJ关于实现特殊功能的文档,应该可以通过使用funsig关键字将一个仿函数指定为另一个仿函数.因此,给予签名

signature SIG = sig ... end

SIG当应用于满足某些签名的结构时,我们应该能够指定一个生成满足模块的仿函数 SIG'.例如,

funsig Fn (S:SIG') = SIG

通过Fn这种方式声明,我们应该(能够定义另一个将该仿函数作为参数的仿函数.即,我们可以定义一个参数化在另一个参数化模块上的模块,并且可能在前者中使用后者;因此:

functor Fn' (functor Fn:SIG) =
struct
...
structure S' = Fn (S:SIG')
...
end

这在理论上看起来都不错,但我无法弄清楚如何实际使用这种模式.

示例问题

以下是我尝试使用此模式的两个实例,但却发现它不切实际:

第一次尝试

对于我的第一次尝试,只是玩游戏,我试图制作一个仿函数,它将实现一个有序集的仿函数,并生成一个处理整数集的模块(不是很有用,但它可以让你参数化一组给定的键入不同的集合实现).我可以定义以下结构,它们将编译(使用新泽西州标准ML v110.7):

structure IntOrdKey : ORD_KEY
= struct
    type ord_key = int
    val compare = Int.compare
end

funsig SET_FN (KEY:ORD_KEY) = ORD_SET

functor IntSetFn (functor SetFn:SET_FN) =
struct
    structure Set = SetFn (IntOrdKey)
end

但是当我真的尝试应用于IntSetFn一个应该满足 SET_FNfunsig的仿函数时,它只是不解析:

- structure IntSet = IntSetFn (functor ListSetFn);
= ;
= ;;
stdIn:18.1-24.2 Error: syntax error: deleting  RPAREN SEMICOLON SEMICOLON
- structure IntSet = IntSetFn (functor BinarySetFn) ;
= ;
= ;
stdIn:19.1-26.2 Error: syntax error: deleting  RPAREN SEMICOLON SEMICOLON

第二次尝试

我的第二次尝试以两种方式失败.

我已经定义了嵌套模块的结构,它实现了多态和单态堆栈(源文件,对于好奇的).要实现单态堆栈,可以

- structure IntStack = Collect.Stack.Mono (type elem = int);
structure IntStack : MONO_STACK?
- IntStack.push(1, IntStack.empty);
val it = - : IntStack.t

等等.到目前为止似乎工作正常.现在,我想定义一个参数化这个仿函数的模块.所以我为Collect.Stack.Monofunctor 定义了一个funsig (可以在我的repo中看到).然后,按照上面指出的模式,我尝试定义以下测试模块:

(* load my little utility library *)
CM.autoload("../../../utils/sources.cm");

functor T (functor StackFn:MONO_STACK) =
struct
    structure S = StackFn (type elem = int)
    val x = S.push (1, S.empty)
end

但这不会编译!我收到类型错误:

Error: operator and operand don't agree [overload conflict]
  operator domain: S.elem * S.t
  operand:         [int ty] * S.t
  in expression:
    S.push (1,S.empty)

uncaught exception Error
  raised at: ../compiler/TopLevel/interact/evalloop.sml:66.19-66.27
             ../compiler/TopLevel/interact/evalloop.sml:44.55
             ../compiler/TopLevel/interact/evalloop.sml:292.17-292.20

然而,在仿函数中T,我似乎使用完全相同的实例化模式,在顶层完美运行.我错过了什么？

不幸的是,这不是我意外的结束.现在,我删除导致类型错误的行,离开,

functor T (functor StackFn:MONO_STACK) =
struct
    structure S = StackFn (type elem = int)
end

编译好:

[scanning ../../../utils/sources.cm]
val it = true : bool
[autoloading]
[autoloading done]
functor T(<param>: sig functor StackFn : <fctsig> end) :
         sig
           structure S : <sig>
         end
val it = () : unit

但我实际上无法实例化模块!显然,高阶函子不支持路径访问语法？

- structure Test = T (functor Collect.Stack.Mono);
stdIn:43.36-43.43 Error: syntax error: deleting  DOT ID DOT

我迷路了.

问题

我有三个相关的问题:

1. 在SML/NJ中是否存在我缺少的高阶仿函数的基本原理,还是仅仅是该语言的一个不完整,笨拙实现的特性？
2. 如果是后者,我可以在哪里找到更优雅,更实用的高阶函子？(希望是一个SML,但如果有必要,我会深入到OCaml.)
3. 我是否应采取不同的方法来实现这些效果,避免高阶函子一起使用？

非常感谢任何答案,提示或后续问题!

Answer 1

关于您的第一次尝试,应用您的IntSetFn仿函数的正确语法是:

structure IntSet = IntSetFn (functor SetFn = ListSetFn)

这同样适用于您Test在第二次尝试中使用仿函数:

structure Test = T (functor StackFn = Collect.Stack.Mono)

这应该修复语法错误.

尝试在仿S函数中使用堆栈结构时遇到的类型错误T与您定义MONO_STACKfunsig 的方式有关:

funsig MONO_STACK (E:ELEM) = MONO_STACK

这只是说它返回一个完全抽象类型的 MONO_STACK结构elem.它并没有说它的elem类型会是一样的E.elem.根据这个,我可以通过一个仿函数

functor F (E : ELEM) = struct type elem = unit ... end

给你的算子T.因此,在内部T,类型系统不允许假设type S.elem= int,因此您会得到类型错误.

要解决此问题,您需要MONO_STACK按如下方式优化funsig:

funsig MONO_STACK (E:ELEM) = MONO_STACK where type elem = E.elem

这应该消除类型错误.

[编辑]

至于你的问题:

1. 高阶仿函数在SML/NJ中有点笨拙,因为它试图与普通SML保持100%兼容,它将仿函数的命名空间与结构的命名空间分开.如果情况并非如此,则不需要将funsigs作为单独的命名空间(和其他语法巴洛克式),并且签名语言可以简单地扩展为包含仿函数类型.

2. 莫斯科ML是另一种SML方言,具有更高阶的模块扩展,可以更优雅地解决兼容性问题(并且更具表现力).还有(现在大部分已经死了)ALice ML,还有另一个带有高阶函子的SML方言,只是简单地删除了尴尬的命名空间分离.OCaml当然首先没有这个约束,所以它的高阶模块在语法上也更规则.

3. 这种方法似乎很好.