SML 不同结构的通用类型
SML Common type for different structures
我正在标准 ML 中实现集合。目前看起来像这样:
signature SET = sig
type t
type 'a set
...
val map : ('a -> t) -> 'a set -> t set
end
functor ListSetFn (EQ : sig type t val equal : t * t -> bool end)
:> SET where type t = EQ.t = struct
type t = EQ.t
type 'a set = 'a list
...
fun map f = fromList o (List.map f)
end
我希望 map
函数能够接受结构 SET
中的任何集合,理想情况下甚至不限于来自 ListSetFn
仿函数的集合。但是,在顶层,它只能对由单个结构创建的集合进行操作:调用它的结构,例如:
functor EqListSetFn(eqtype t) :> SET where type t = t = struct
structure T = ListSetFn(struct type t = t val equal = op= end)
open T
end
structure IntSet = EqListSetFn(type t = int)
IntSet.map : ('a -> IntSet.t) -> 'a IntSet.set -> IntSet.t IntSet.set
虽然我真的很喜欢
IntSet.map : ('a -> IntSet.t) -> 'a ArbitrarySet.set -> IntSet.t IntSet.set
有办法吗?我知道它可以在顶层声明,但我想隐藏内部实现并因此使用不透明签名
原则上,有两种方法可以执行这样的参数化:
将函数包装到它自己的函子中,将另一个结构作为参数。
使函数成为多态的,将相关函数作为单独的参数或作为参数记录传递给其他类型。
我们假设 SET
签名包含这些函数:
val empty : 'a set
val isEmpty : 'a set -> bool
val add : 'a * 'a set -> 'a set
val remove : 'a * 'a set -> 'a set
val pick : 'a set -> 'a
那么前一个解决方案将如下所示:
functor SetMap (structure S1 : SET; structure S2 : SET) =
struct
fun map f s =
if S1.isEmpty s then S2.empty else
let val x = S1.pick s
in S2.add (f x, map f (S2.remove (x, s)))
end
end
对于解决方案 2,您需要直接传递所有相关函数,例如作为记录:
fun map {isEmpty, pick, remove} {empty, add} f s =
let
fun iter s =
if isEmpty s then empty else
let val x = pick s
in add (f x, iter (remove (x, s)))
end
in iter s end
FWIW,使用 first-class 结构会更好,但 SML 没有将它们作为标准功能。
fun map (pack S1 : SET) (pack S2 : SET) f s =
let
fun iter s =
if S1.isEmpty s then S2.empty else
let val x = S1.pick s
in S2.add (f x, iter (S2.remove (x, s)))
end
in iter s end
我正在标准 ML 中实现集合。目前看起来像这样:
signature SET = sig
type t
type 'a set
...
val map : ('a -> t) -> 'a set -> t set
end
functor ListSetFn (EQ : sig type t val equal : t * t -> bool end)
:> SET where type t = EQ.t = struct
type t = EQ.t
type 'a set = 'a list
...
fun map f = fromList o (List.map f)
end
我希望 map
函数能够接受结构 SET
中的任何集合,理想情况下甚至不限于来自 ListSetFn
仿函数的集合。但是,在顶层,它只能对由单个结构创建的集合进行操作:调用它的结构,例如:
functor EqListSetFn(eqtype t) :> SET where type t = t = struct
structure T = ListSetFn(struct type t = t val equal = op= end)
open T
end
structure IntSet = EqListSetFn(type t = int)
IntSet.map : ('a -> IntSet.t) -> 'a IntSet.set -> IntSet.t IntSet.set
虽然我真的很喜欢
IntSet.map : ('a -> IntSet.t) -> 'a ArbitrarySet.set -> IntSet.t IntSet.set
有办法吗?我知道它可以在顶层声明,但我想隐藏内部实现并因此使用不透明签名
原则上,有两种方法可以执行这样的参数化:
将函数包装到它自己的函子中,将另一个结构作为参数。
使函数成为多态的,将相关函数作为单独的参数或作为参数记录传递给其他类型。
我们假设 SET
签名包含这些函数:
val empty : 'a set
val isEmpty : 'a set -> bool
val add : 'a * 'a set -> 'a set
val remove : 'a * 'a set -> 'a set
val pick : 'a set -> 'a
那么前一个解决方案将如下所示:
functor SetMap (structure S1 : SET; structure S2 : SET) =
struct
fun map f s =
if S1.isEmpty s then S2.empty else
let val x = S1.pick s
in S2.add (f x, map f (S2.remove (x, s)))
end
end
对于解决方案 2,您需要直接传递所有相关函数,例如作为记录:
fun map {isEmpty, pick, remove} {empty, add} f s =
let
fun iter s =
if isEmpty s then empty else
let val x = pick s
in add (f x, iter (remove (x, s)))
end
in iter s end
FWIW,使用 first-class 结构会更好,但 SML 没有将它们作为标准功能。
fun map (pack S1 : SET) (pack S2 : SET) f s =
let
fun iter s =
if S1.isEmpty s then S2.empty else
let val x = S1.pick s
in S2.add (f x, iter (S2.remove (x, s)))
end
in iter s end