'How to use higher order functors properly?' 或 'How to have serious fun with funsigs?'

Question

动机

对于我的生活，我无法弄清楚如何在 SML/NJ 到任何实际目的。

根据 SML/NJ docs on the implementation's special features, 应该可以通过使用将一个函子指定为另一个函子的参数 funsig 关键字。因此，给定一个签名

signature SIG = sig ... end

我们应该能够指定一个仿函数来生成满足以下要求的模块 SIG，当应用于满足某些签名的结构时 SIG'。例如，

funsig Fn (S:SIG') = SIG

以这种方式声明 Fn 后，我们应该（能够定义另一个以 this 仿函数作为参数的仿函数。即，我们可以定义一个模块在另一个参数化模块上进行参数化，并且大概使用后者在前者之中；因此：

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

理论上一切看起来都不错，但我不知道如何实际利用这种模式。

示例问题

这是我尝试使用此模式的两个实例，结果却发现这不切实际：

第一次尝试

对于我的第一次尝试，只是玩玩，我试图制作一个仿函数采用实现有序集的仿函数，并生成用于处理的模块使用整数集（不是很有用，但它可以让你参数化集不同集合实现上的给定类型）。我可以定义以下结构，他们将编译（使用新泽西州的标准机器学习 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_FN funsig，它只是不解析：

- 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

第二次尝试

我的第二次尝试在两个方面都失败了。

我已经定义了嵌套模块的结构，实现了多态和单态堆栈（the source file，出于好奇）。到实现单态堆栈，你做

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

等等。到目前为止它似乎工作正常。现在，我想定义一个模块参数化这个函子。所以我为 Collect.Stack.Mono 仿函数（可以在我的仓库中看到）。然后，按照上面指出的模式，我尝试定义以下测试模块：

(* 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

我很迷茫。

问题

我有三个相关问题：

有没有高阶函子的基本原理SML/NJ我是缺少，或者它只是一个不完整的、笨拙的实现功能语言？
如果是后者的话，哪里找更优雅实用的高阶仿函数？（希望是 SML，但如有必要，我会深入研究 OCaml。）
也许我应该采取不同的方法来实现这些类型一起避免高阶仿函数的效果？

非常感谢任何答案、提示或后续问题！

Answer 1

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

structure IntSet = IntSetFn (functor SetFn = ListSetFn)

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

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

这应该可以修复语法错误。

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

funsig MONO_STACK (E:ELEM) = MONO_STACK

这只是说它 returns a MONO_STACK 结构，具有完全抽象的 elem 类型。它并没有说它的 elem 类型将与 E.elem 相同。据此，我可以传入一个像

这样的仿函数

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

给你的仿函数 T。因此，在 T 内部，类型系统不允许假定类型 S.elem = int，因此你会得到一个类型错误。

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

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

这应该可以消除类型错误。

[编辑]

关于您的问题：

高阶仿函数在 SML/NJ 中在语法上有点笨拙，因为它试图与普通 SML 保持 100% 兼容，后者将仿函数的名称空间与结构的名称空间分开。如果不是这种情况，那么也不需要将 funsigs 作为一个单独的命名空间（以及其他句法巴洛克风格），并且可以简单地扩展签名语言以包括仿函数类型。
Moscow ML 是另一种 SML 方言，具有更高阶的模块扩展，更优雅地解决了兼容性问题（并且更具表现力）。还有（现在几乎已经死了）ALice ML，这是另一种带有高阶函子的 SML 方言，它只是放弃了笨拙的命名空间分离。 OCaml当然一开始就没有这个约束，所以它的高阶模块在句法上也比较规则。
这个方法看起来不错。

'How to use higher order functors properly?' 或 'How to have serious fun with funsigs?'

'How to use higher order functors properly?' or 'How to have serious fun with funsigs?'

module

ocaml

sml

smlnj

ml

动机

示例问题

第一次尝试

第二次尝试

问题