标准 ML 函子示例 [英] Standard ML functor examples

问题描述

Standard ML 中的Functor 与模块系统相关，可以根据其他结构生成结构.下面给出了一个为各种类型的列表生成列表组合子的函子的例子，但这个例子有一个问题:

Functors in Standard ML are related to the module system and can generate structures based on other structures. An example of a functor generating list combinators for various types of lists is given below, but this example has a problem:

各种类型的列表都有优点——例如，惰性列表可以无限长，连接列表有一个 O(1) 连接运算符.但是当所有这些列表类型都符合相同的签名时，函子只能使用它们的通用属性.

The various types of lists all have advantages -- for example, lazy lists can be infinitely long, and concantenation lists have a O(1) concat operator. But when all of these list types conform to the same signature, the functor can only use their general properties.

因此，我的问题是:当函子有用并且各种生成的结构不会失去它们的特殊能力时，什么是一个很好的例子?

My question is therefore: What is a good example of when functors are useful and the various generated structures don't lose their special abilities?

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)

推荐答案

不确定我是否完全理解您的问题.显然，函子可用于定义模块化抽象:(1) 是多态的，(2) 需要对其类型参数进行一整套操作，以及 (3) 提供类型作为其结果的一部分(特别是 abstract 类型)，以及 (4) 提供一整套操作.

Not sure I fully understand your question. Obviously, functors are useful for defining modular abstractions that (1) are polymorphic, (2) require a whole set of operations over their type parameters, and (3) provide types as part of their result (in particular, abstract types), and (4) provide an entire set of operations.

请注意，您的示例没有使用 (3)，这可能是函子最有趣的方面.想象一下，例如，实现一个抽象矩阵类型，您想对其基于的向量类型进行参数化.

Note that your example doesn't make use of (3), which probably is the most interesting aspect of functors. Imagine, for example, implementing an abstract matrix type that you want to parameterise over the vector type it is based on.

ML 函子的一个特定特征——以及核心语言多态函数——是它们参数化.参数化是一种语义属性，表示(多态代码的)评估忽略了它被实例化的具体类型.这是一个重要的属性，因为它暗示了各种语义善.特别是，它提供了非常强大的抽象和推理原则(参见例如 Wadler 的 定理是免费的！"，或者我在回答另一个问题中给出的简要解释).它也是类型擦除编译的基础(即在运行时不需要类型).

One specific characteristic of ML functors -- as well as of core-language polymorphic functions -- is that they are parametric. Parametricity is a semantic property saying that evaluation (of polymorphic code) is oblivious to the concrete type(s) it is instantiated with. That is an important property, as it implies all kinds of semantic goodness. In particular, it provides very strong abstraction and reasoning principles (see e.g. Wadler's "Theorem's for free!", or the brief explanation I gave in reply to another question). It also is the basis for type-erasing compilation (i.e., no types are needed at runtime).

参数意味着单个函子不能对不同的类型有不同的实现——这似乎是你要问的.但当然，您可以自由编写多个函子，对它们的参数做出不同的语义/复杂性假设.

Parametricity implies that a single functor cannot have different implementations for different types -- which seems to be what you are asking about. But of course, you are free to write multiple functors that make different semantic/complexity assumptions about their parameters.

希望这能回答您的问题.

Hope that kind of answers your question.

这篇关于标准 ML 函子示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！