10

標準 ML のファンクターは、モジュール システムに関連しており、他の構造に基づいて構造を生成できます。さまざまなタイプのリストのリスト コンビネータを生成するファンクタの例を以下に示しますが、この例には問題があります。

さまざまな種類のリストにはすべて利点があります。たとえば、遅延リストは無限に長くなる可能性があり、連結リストには O(1) 連結演算子があります。しかし、これらすべてのリスト タイプが同じシグネチャに準拠している場合、ファンクターはそれらの一般的なプロパティしか使用できません。

したがって、私の質問は次のとおりです。ファンクタが便利で、生成されたさまざまな構造が特殊な能力を失わない場合の良い例は何ですか?

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)
4

3 に答える 3

10

あなたの質問を完全に理解しているかどうかわかりません。明らかに、ファンクターは、(1) ポリモーフィックであり、(2) 型パラメーターに対する一連の操作全体が必要であり、(3) 結果の一部として型 (特に抽象型) を提供するモジュラー抽象化を定義するのに役立ちます。 (4) 一連の操作全体を提供します。

あなたの例では (3) を使用していないことに注意してください。これはおそらくファンクターの最も興味深い側面です。たとえば、ベースとなるベクトル型をパラメーター化する抽象行列型を実装することを想像してください。

ML ファンクタ (およびコア言語のポリモーフィック関数) の特定の特徴の 1 つは、それらがパラメトリックであることです。パラメトリック性は、(ポリモーフィック コードの) 評価が、それがインスタンス化される具体的な型に気付かないことを示すセマンティック プロパティです。これは、あらゆる種類のセマンティックの良さを暗示しているため、重要なプロパティです。特に、非常に強力な抽象化と推論の原則を提供します (たとえば、Wadler の「Theorem's for free!」または別の質問に対する簡単な説明を参照してください)。また、型消去コンパイルの基礎でもあります (つまり、実行時に型は必要ありません)。

パラメトリック性は、単一のファンクターが異なる型に対して異なる実装を持つことができないことを意味します-これはあなたが求めているもののようです. しかしもちろん、パラメーターについて異なるセマンティック/複雑さの仮定を行う複数のファンクターを自由に作成できます。

そのような答えがあなたの質問にあることを願っています。

于 2012-11-10T08:51:36.970 に答える
2

ファンクターは「リフター」です - 彼らは持ち上げます (この動詞は標準的な FP 用語です): 与えられた型と値のセットに対して、それらの上に新しい型と値のセットを作成できます。必要なモジュール インターフェイスに準拠するすべてのモジュールは、ファンクタから「利益を得る」ことができますが、実装固有の利点を意味する場合、特別な能力を失うことはありません。

たとえば、あなたのまさにその例は、私の要点を示すのにうまく機能します。concatあなたが書いたように、連結リストには非常に高速な演算子があり、ファンクターで持ち上げると、この「能力」は消えません。それはまだそこにあり、おそらくファンクター コードによって使用されることさえあります。したがって、この例では、ファンクターのコードは実際にはリストの実装の恩恵を受けていますが、それを認識していません。それは非常に強力な概念です。

一方、モジュールはファンクターによって持ち上げられるときにインターフェイスに適合する必要があるため、余分な値と型がその過程で失われ、煩わしい場合があります。それでも、ML 方言によっては、この制限が多少緩和される場合があります。

于 2012-11-12T01:18:16.423 に答える