标准ML的函数器范例

Question

Standard ML中的Functor与模块系统相关，可以基于其他结构生成结构。下面是一个生成不同类型列表组合器的functor示例，但该示例存在问题：

各种类型的列表都有其优点--例如，惰性列表可以是无限长的，而连接列表具有O(1)的连接操作符。但当所有这些列表类型都符合相同的签名时，functor只能使用它们的普遍属性。

因此，我的问题是：有什么好的例子说明functor何时有用，而生成的各种结构不会失去其特殊能力？

signature MYLIST =
sig
  type 'a t
  val null : 'a t -> bool
  val empty : 'a t
  val cons : 'a * 'a t -> 'a t
  val hd : 'a t -> 'a
  val tl : 'a t -> 'a t
end

structure RegularList : MYLIST =
struct
  type 'a t = 'a list
  val null = List.null
  val empty = []
  val cons = op::
  val hd = List.hd
  val tl = List.tl
end

structure LazyList : MYLIST =
struct
  datatype 'a t = Nil | Cons of 'a * (unit -> 'a t)
   val empty = Nil
   fun null Nil = true
    | null _ = false
   fun cons (x, xs) = Cons (x, fn () => xs)
   fun hd Nil = raise Empty
    | hd (Cons (x, _)) = x
   fun tl Nil = raise Empty
    | tl (Cons (_, f)) = f ()
end

structure ConcatList : MYLIST =
struct
  datatype 'a t = Nil | Singleton of 'a | Concat of 'a t * 'a t
  val empty = Nil
  fun null Nil = true
    | null (Singleton _) = false
    | null (Concat (xs, ys)) = null xs andalso null ys
  fun cons (x, xs) = Concat (Singleton x, xs)
  fun hd Nil = raise Empty
    | hd (Singleton x) = x
    | hd (Concat (xs, ys)) = hd xs
  fun tl Nil = raise Empty
    | tl (Singleton x) = Nil
    | tl (Concat (xs, ys)) = (* exercise *)
end

signature MYLISTCOMB =
sig
  type 'a t
  val length : 'a liste -> int
  val map : ('a -> 'b) -> 'a liste -> 'b liste
  val foldl : ('a * 'b -> 'b) -> 'b -> 'a liste -> 'b
  val append : 'a liste * 'a liste -> 'a liste
  val concat : 'a liste liste -> 'a liste
  val sort : ('a * 'a -> order) -> 'a t -> 'a t
end

functor ListComb (X : MYLIST) : MYLISTCOMB =
struct
  type 'a t = 'a X.t
  open X

  fun length xs =
      if null xs then 0
      else 1 + length (tl xs)

  fun map f xs =
      if null xs then empty
      else cons(f (hd xs), map f (tl xs))

  fun foldl f e xs =
      if null xs then e
      else foldl f (f (hd xs, e)) (tl xs)

  fun append (xs, ys) =
      if null xs then ys
      else cons (hd xs, append (tl xs, ys))

  fun concat xs =
      if null xs then empty
      else append (hd xs, concat (tl xs))

  fun sort cmp xs = (* exercise *)
end

structure RegularListComb = ListComb (RegularList)
structure LazyListComb = ListComb (LazyList)
structure ConcatListComb = ListComb (ConcatList)

- sshine

---

我有点困惑。在SML中，functor缺乏特定实现功能的可见性是其本质之一。你是在寻求某种行为保持保证吗？ - Gian

@Gian：他正在寻找一些好的例子，以向学生展示函数对象在介绍性SML课程中的实用性。 - Sebastian Paaske Tørholm

在这种情况下，请查看CMlib：https://github.com/standardml/cmlib--特别是像“streamable”这样的东西。 - Gian

Answer 1

我不确定我完全理解你的问题。显然，函数对象对于定义模块化抽象非常有用，这些抽象具有以下特点：(1)是多态的，(2)需要一整套操作来操作它们的类型参数，(3)提供类型作为其结果的一部分（特别是抽象类型），以及(4)提供整个一套操作。请注意，你的示例没有使用(3)，这可能是函数对象最有趣的方面。例如，想象一下实现一个抽象矩阵类型，你希望将其参数化为基于的向量类型。

ML函子的一个特点，以及核心语言多态函数的一个特点是它们是参数化的。参数性是一种语义属性，表示（多态代码）的评估对其实例化的具体类型视而不见。这是一个重要的属性，因为它意味着各种语义好处。特别是，它提供了非常强大的抽象和推理原则（例如，请参阅Wadler的“"Theorem's for free!"”，或我在回答另一个问题中给出的简要解释）。它还是类型擦除编译的基础（即，在运行时不需要类型）。

参数性意味着一个单独的函子不能有不同的实现来处理不同的类型 - 这似乎是你所问的。但当然，您可以自由地编写多个函子，使其对其参数做出不同的语义/复杂性假设。

希望这种回答能够回答您的问题。

- Andreas Rossberg

Answer 2

以下是一些有用的SML函子示例。它们的基础理念是：如果您可以完成一组任务，则可以使用它来完成另一组任务。

一个用于集合的函子：如果您可以比较元素，则可以使用平衡数据结构（例如二叉搜索树或其他类型的树）创建集合。

signature SET =
sig
    type elem
    type set
    val empty : set
    val singleton : elem -> set
    val union : set -> set -> set
    val intersect : set -> set -> set
end

signature ORD =
sig
    type t
    val compare : t * t -> order
end

functor BalancedSetFunctor(structure Cmp : ORD) :> SET =
struct
    type elem = Cmp.t
    type set = ...

    val empty = ...
    fun singleton x = ...
    fun union s1 s2 = ...
    fun intersect s1 s2 = ...
end

迭代的函数对象: 对于任何类型的事物集合（如列表），如果你能够对它们进行迭代，那么你就可以自动折叠它们。你还可以为同一数据类型创建不同的结构以便按不同方式折叠（例如树的前序、中序和后序遍历）。

signature ITERABLE =
sig
    type elem
    type collection
    val next : collection -> (elem * collection) option
end

signature FOLD =
sig
    type elem
    type collection
    val fold : (elem * 'b -> 'b) -> 'b -> collection -> 'b
end

functor FoldFunctor(Iter : ITERABLE) :> FOLD =
struct
    type elem = Iter.elem
    type collection = Iter.collection

    fun fold f e xs =
        case Iter.next xs of
            NONE => e
          | SOME (x, xs') => fold f (f (x, e)) xs'
end

- sshine

Answer 3

Functors是“举升器” - 它们通过给定一组类型和值，让您在它们的基础上创建一组新的类型和值。符合所需模块接口的所有模块都可以“受益”于functor，但如果您指的是实现特定的优势，则它们不会失去其特殊功能。

例如，您的示例非常适合证明我的观点：连接列表具有非常快速的concat操作符，就像您写的那样，在使用functor时，这种“能力”并没有消失。它仍然存在，甚至可能被functor代码使用。因此，在这个例子中，functor代码实际上从列表实现中受益，而无需知道它。这是一个非常强大的概念。

另一方面，由于模块在被functor提升时必须适合接口，因此在该过程中会丢失多余的值和类型，这可能很烦人。尽管如此，根据ML方言的不同，这种限制可能会稍微放松。

- didierc

---

另一方面，由于模块在被函子提升时必须适应一个接口，所以多余的值和类型将会在此过程中丢失。但不一定如此，因为对签名的归属可能是透明的（除非我没有理解到重点）。顺便问一下，您知道其他函数式编程术语（例如“lift”）得到解释的在线词典吗？ - Hibou57