SML如何实现抽象？

Question

我是SML的新手,这是我第一次学习函数式语言.我想有SML的抽象.我还没有找到如何在SML中实现抽象的完美解释.有人可以提供解释吗？

Answer 1

一般来说,编程中至少有两种形式的"抽象":

• 抽象客户端(参数化)
• 摘要实现(封装)

(如果你关心,这些对应于逻辑和类型理论中的普遍和存在量化.)

在ML中,参数化可以在两个级别上完成.无论是小型,使用函数(对值的抽象)和多态(对类型的抽象).请特别注意,函数是一流的,因此您可以将一个函数参数化为另一个函数.例如:

fun map f []      = []
  | map f (x::xs) = f x :: map f xs

摘要转换函数f以及元素类型的列表转换.

在大型参数化中,可以使用模块系统完成参数化:仿函数将整个模块抽象到另一个模块上(即,在值和类型上).例如,您还可以将地图函数编写为仿函数:

functor Mapper(type t; type u; val f : t -> u) =
struct
  fun map []      = []
    | map (x::xs) = f x :: map xs
end

但通常你会使用仿函数来进行大规模抽象,也就是说,如果你需要参数化的函数不止一个.

通过使用模块也可以实现封装.具体而言,通过密封它们,即将其类型的细节隐藏在签名后面.例如,这是整数集的(天真)实现:

signature INT_SET =
sig
  type set
  val empty : set
  val add : int * set -> set
  val mem : int * set -> bool
end

structure IntSet :> INT_SET =  (* ':>' hides the implementation of type set *)
struct
  type set = int list
  val empty = []
  fun add(x, s) = x::s
  fun mem(x, s) = List.exists (fn y => y = x) s
end

在结构之外IntSet,它的类型set是完全抽象的,即它不能与列表互换.这就是所谓的模块密封操作器的目的:>.

两种形式的抽象可以一起发生.例如,在ML中,通常会将集合实现为仿函数:

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

signature SET =
sig
  type elem
  type set
  val empty : set
  val add : elem * set -> set
  val mem : elem * set -> bool
end

functor Set(Elem : ORD) :> SET where type elem = Elem.t =
struct
  type elem = Elem.t
  datatype set = Empty | Branch of set * elem * set

  val empty = Empty

  fun add(x, Empty) = Branch(Empty, x, Empty)
    | add(x, Branch(l, y, r)) =
      case Elem.compare(x, y) of
        LESS => Branch(add(x, l), y, r)
      | EQUAL => Branch(l, y, r)
      | GREATER => Branch(l, y, add(x, r))

  fun mem(x, Empty) = false
    | mem(x, Branch(l, y, r)) =
      case Elem.compare(x, y) of
        LESS => mem(x, l)
      | EQUAL => true
      | GREATER => mem(x, r)
end

该集合的实现适用于可以提供排序功能的任何类型.与之前的朴素实现不同,它还使用更高效的搜索树作为其实现.但是,这在外部是不可观察的,因为类型的实现再次被隐藏.