标准ML仿函数示例

Question

标准ML中的函数与模块系统相关,并且可以基于其他结构生成结构.下面给出了为各种类型的列表生成列表组合器的仿函数的示例,但是此示例存在一个问题:

各种类型的列表都具有优势 - 例如,惰性列表可以无限长,并且concantenation列表具有O(1)concat运算符.但是当所有这些列表类型符合相同的签名时,仿函数只能使用它们的常规属性.

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

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)

Answer 1

不确定我完全理解你的问题.显然,仿函数是用于定义模块化抽象,(1)是多态是有用的,(2)需要一个整体的一组操作在他们的类型的参数,以及(3)提供类型作为其结果的一部分(特别是抽象类型),和(4)提供一整套操作.

请注意,您的示例不使用(3),这可能是仿函数最有趣的方面.例如,想象一下,实现一个抽象矩阵类型,您希望通过它所基于的矢量类型进行参数化.

ML仿函数的一个特定特征 - 以及核心语言多态函数 - 是它们是参数化的.Parametricity是一种语义属性,表示(多态代码)的评估对于它实例化的具体类型是遗忘的.这是一个重要的属性,因为它意味着各种语义上的善.特别是,它提供了非常有力的抽象和推理原则(见例如Wadler的"定理的自由!",或者我给在简短的解释回答另一个问题).它也是类型擦除编译的基础(即,在运行时不需要类型).

参数化意味着单个仿函数不能针对不同类型实现不同的实现 - 这似乎就是您所要求的.但是,当然,您可以自由编写多个函数,这些函数对其参数进行不同的语义/复杂性假设.

希望能回答你的问题.