Стандартные примеры функторов ML

Question

Функторы в стандарте ML связаны с модульной системой и могут генерировать структуры на основе других структур. Ниже приводится пример комбинаторов списков, генерирующих функторы для различных типов списков, но в этом примере есть проблема:

Различные типы списков имеют свои преимущества - например, ленивые списки могут быть бесконечно длинными, а списки конкатенации имеют оператор concat 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)

Answer 1

Не уверен, что я полностью понимаю ваш вопрос. Очевидно, что функторы полезны для определения модульных абстракций, которые (1) являются полиморфными, (2) требуют полного набора операций над параметрами их типов, и (3) предоставляют типы как часть своего результата (в частности, абстрактные типы), и (4) обеспечить полный набор операций.

Обратите внимание, что в вашем примере не используется (3), что, вероятно, является наиболее интересным аспектом функторов. Представьте, например, реализацию абстрактного матричного типа, который вы хотите параметризовать поверх векторного типа, на котором он основан.

Одной из специфических характеристик функторов ML, а также полиморфных функций языка ядра является то, что они являются параметрическими. Параметричность - это семантическое свойство, говорящее о том, что оценка (полиморфного кода) не обращает внимания на конкретный тип (типы), с которым она создается. Это важное свойство, поскольку оно подразумевает все виды семантического совершенства. В частности, он обеспечивает очень сильные принципы абстракции и обоснования (см., Например, "Теорема Вадлера бесплатно!" Или краткое объяснение, которое я дал в ответ на другой вопрос). Это также является основой для компиляции с удалением типов (т.е. типы не требуются во время выполнения).

Параметричность подразумевает, что один функтор не может иметь разных реализаций для разных типов - что, кажется, является тем, о чем вы спрашиваете. Но, конечно, вы можете написать несколько функторов, которые делают различные предположения о семантике / сложности своих параметров.

Надеюсь, что такого рода ответы на ваш вопрос.

Answer 2

Вот несколько полезных примеров функторов SML. Они сделаны на следующей предпосылке: если вы можете делать один набор вещей, это позволяет вам делать другой набор вещей.

Функтор для наборов. Если вы можете сравнивать элементы, вы можете создавать наборы, используя сбалансированные структуры данных (например, деревья двоичного поиска или другие виды деревьев).

signature SET =
sig
    type elem
    type set
    val empty : set
    val singleton : elem -> set
    val union : set -> set -> set
    val intersect : set -> set -> set
end

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

functor BalancedSetFunctor(structure Cmp : ORD) :> SET =
struct
    type elem = Cmp.t
    type set = ...

    val empty = ...
    fun singleton x = ...
    fun union s1 s2 = ...
    fun intersect s1 s2 = ...
end

Функтор для итерации. Если вы можете выполнять итерацию в любом наборе вещей (например, списках), вы можете автоматически сложить их. Вы также можете создавать различные структуры для разных способов сворачивания одного и того же типа данных (например, предварительный порядок, порядок и порядок обхода деревьев).

signature ITERABLE =
sig
    type elem
    type collection
    val next : collection -> (elem * collection) option
end

signature FOLD =
sig
    type elem
    type collection
    val fold : (elem * 'b -> 'b) -> 'b -> collection -> 'b
end

functor FoldFunctor(Iter : ITERABLE) :> FOLD =
struct
    type elem = Iter.elem
    type collection = Iter.collection

    fun fold f e xs =
        case Iter.next xs of
            NONE => e
          | SOME (x, xs') => fold f (f (x, e)) xs'
end

Answer 3

Функторы - это "подъемники" - они поднимают (этот глагол является стандартной терминологией FP): для заданного набора типов и значений они позволяют создавать новый набор типов и значений поверх них. Все модули, соответствующие требуемому интерфейсу модулей, могут "извлекать выгоду" из функтора, но они не теряют своих особых способностей, если под способностями вы подразумеваете конкретные преимущества реализации.

Ваш пример, например, хорошо работает, чтобы продемонстрировать мою точку зрения: списки конкатенации очень быстро concat оператор, как вы написали, и при снятии с помощью функтора эта "способность" не исчезает. Он все еще там и, возможно, даже используется кодом функтора. Так что в этом примере код функтора фактически извлекает выгоду из реализации списка, не зная об этом. Это очень мощная концепция.

С другой стороны, поскольку модули должны соответствовать интерфейсу при поднятии функтором, лишние значения и типы теряются в процессе, что может раздражать. Тем не менее, в зависимости от диалекта ML, это ограничение может быть несколько смягчено.