如何在标准 ML 中表示多态列表幺半群

Question

我最近在研究标准 ML 中的幺半群。签名好写：

signature MONOID =
sig
  type monoid
  val neutral : monoid
  val combine : monoid -> monoid -> monoid
end

简单的幺半群也是如此，例如整数加法幺半群：

structure IntSumMonoid : MONOID =
struct
  type monoid = int
  val neutral = 0
  fun combine a b = a + b
end

但我在为更高级类型定义幺半群时遇到了困难，例如 list。这当然不会编译：

structure ListMonoid : MONOID =
struct
  type monoid = 'a list
  val neutral = []
  fun combine a b = a @ b
end

经过一番搜索，我找到了以下基于仿函数的解决方案：

functor ListMonoid (type m) : MONOID =
struct
  type monoid = m list
  val neutral = []
  fun combine a b = a @ b
end

我的问题是是否存在声明通用列表幺半群的替代方法，理想情况下不需要 functor 声明。尝试声明一个列表幺半群时，显然没有必要知道列表包含的类型。

Answer 1

您可以在签名中参数化类型。但是组成幺半群就变得奇怪或不可能了。 Haskell 使用类型类解决了这个问题，您可以在 SML 中使用仿函数模拟它，但语法很繁琐（正如您所注意到的）。

signature MONOID =
sig
  type 'a monoid
  val neutral : 'a monoid
  val combine : 'a monoid -> 'a monoid -> 'a monoid
end

structure IntSumMonoid : MONOID =
struct
  type 'a monoid = int
  val neutral = 0
  fun combine a b = a + b
end

structure ListMonoid : MONOID =
struct
  type 'a monoid = 'a list
  val neutral = []
  fun combine a b = a @ b
end

描述翻译的论文是http://www.mpi-sws.org/~dreyer/papers/mtc/main-short.pdf

如何在标准 ML 中表示多态列表幺半群

How to represent a polymorphic list monoid in Standard ML

sml

ml

monoids