标准ML仿函数的例子 [英] Standard ML functor examples

问题描述

标准ML中的函子与模块系统相关，可以基于其他结构生成结构。下面给出了一个用于各种类型列表的仿函数生成列表组合器的例子，但这个例子有一个问题：

各种类型的列表都有优点 - 对于例如，懒列表可以是无限长的，并且concantenation列表有一个O（1）concat操作符。但是，当所有这些列表类型符合相同的签名时，仿函数只能使用它们的一般属性。

因此，我的问题是：什么时候仿函数

 签名MYLIST = 
 sig $ b $是有用的，各种生成的结构不会失去它们的特殊能力吗？ b类型'在
 val null：'at  - > bool 
 val空：'a t 
 val缺点：'a *'a t  - > 'a t 
 val hd：'a t  - > 'a 
 val tl：'a t  - > 'at 
 end 
 
结构RegularList：MYLIST = 
 struct 
类型'at ='列表
 val null = List.null 
 val empty = [] 
 val cons = op :: 
 val hd = List.hd 
 val tl = List.tl 
 end 
 
结构LazyList ：MYLIST = 
 struct 
 datatype'at = Nil | 'a *（unit  - >'a t）
 val empty =无
 fun null缺点= true 
 | null _ = false 
 fun cons（x，xs）= Cons（x，fn（）=> xs）
 fun hd Nil = raise空
 | hd（Cons（x，_））= x 
 fun tl无= raise空
 | tl（Cons（_，f））= f（）
 end 
 
结构ConcatList：MYLIST = 
 struct 
 datatype'a t = Nil | 'a |的单身人士'a t *'a t 
 val的空心空=无
 fun null无= 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）=无
 | tl（Concat（xs，ys））=（* exercise *）
结束
 
签名MYLISTCOMB = 
 sig 
 type'at 
 val长度： 'a liste  - > int 
 val map：（'a  - >'b） - > 'a liste  - > 'b听
 val foldl：（'a *'b  - >'b） - > 'b  - > 'a liste  - > 'b 
 val append：'a liste *'a liste  - > 'a liste 
 val concat：'a liste liste  - > 'a听
 val排序：（'a *'a  - >顺序） - > 'a t  - > 'at 
 end 
 
 functor ListComb（X：MYLIST）：MYLISTCOMB = 
 struct 
 type'at ='a Xt 
 open X 
 
有趣的长度xs = 
如果null xs然后0 
 else 1 + length（tl xs）
 
 fun map f xs = 
 if null xs然后清空
 else cons（f（hd xs），map f（tl xs））
 
 fun fold x fe 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））
 
有趣的concat xs = 
如果为null xs则为空
 else append（hd xs，concat（tl xs））
 
 fun类型cmp xs =（* exercise *）
结束
 $ b $结构RegularListComb = ListComb（RegularList）
结构LazyListComb = ListComb（LazyList）
结构ConcatListComb = ListComb（ConcatList）
  

解决方案

不知道我完全理解你的问题。显然，函数对于定义（1）是多态的模块化抽象是有用的，（2）需要对它们的类​​型参数进行一整套操作，（3）提供类型作为它们结果的一部分（特别是 abstract 类型）和（4）提供一整套操作。

请注意，您的示例没有使用（3），这可能是函子最有趣的方面。想象一下，例如，实现一个抽象矩阵类型，您想要参数化它所基于的向量类型。

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

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

希望能够回答你的问题。 b $ b

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:

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)

解决方案

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.

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.

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屋！