Не могли бы вы объяснить мне функторы OCaml?

Если вы пришли из вселенной ООП, то, вероятно, полезно думать о модуле как о аналоге статического класса. Подобно статическим классам .NET, модуль OCaml имеет конструкторы; В отличие от .NET, модули OCaml могут принимать параметры в своих конструкторах. Функтор - это пугающее название для объекта, который вы передаете в конструктор модуля.

Итак, используя канонический пример двоичного дерева, мы обычно пишем его на F # следующим образом:

type 'a tree =
    | Nil
    | Node of 'a tree * 'a * 'a tree

module Tree =
    let rec insert v = function
        | Nil -> Node(Nil, v, Nil)
        | Node(l, x, r) ->
            if v < x then Node(insert v l, x, r)
            elif v > x then Node(l, x, insert v r)
            else Node(l, x, r)

Прекрасно и стильно. Но как F # знает, как сравнивать два объекта типа 'a с помощью операторов < и >?

За кулисами он делает что-то вроде этого:

> let gt x y = x > y;;

val gt : 'a -> 'a -> bool when 'a : comparison

Хорошо, а что, если у вас есть объект типа Person, который не реализует этот конкретный интерфейс? Что, если вы хотите определить функцию сортировки на лету? Один из подходов - просто передать компаратор следующим образом:

    let rec insert comparer v = function
        | Nil -> Node(Nil, v, Nil)
        | Node(l, x, r) ->
            if comparer v x = 1 then Node(insert v l, x, r)
            elif comparer v x = -1 then Node(l, x, insert v r)
            else Node(l, x, r)

Это работает, но если вы пишете модуль для операций с деревом со вставкой, поиском, удалением и т. Д., Вам нужно, чтобы клиенты передавали функцию упорядочивания каждый раз, когда они что-либо вызывают.

Если F # поддерживает функторы, его гипотетический синтаксис может выглядеть следующим образом:

type 'a Comparer =
    abstract Gt : 'a -> 'a -> bool
    abstract Lt : 'a -> 'a -> bool
    abstract Eq : 'a -> 'a -> bool

module Tree (comparer : 'a Comparer) =
    let rec insert v = function
        | Nil -> Node(Nil, v, Nil)
        | Node(l, x, r) ->
            if comparer.Lt v x then Node(insert v l, x, r)
            elif comparer.Gt v x then Node(l, x, insert v r)
            else Node(l, x, r)

По-прежнему в гипотетическом синтаксисе вы должны создать свой модуль как таковой:

module PersonTree = Tree (new Comparer<Person>
    {
        member this.Lt x y = x.LastName < y.LastName
        member this.Gt x y = x.LastName > y.LastName
        member this.Eq x y = x.LastName = y.LastName
    })

let people = PersonTree.insert 1 Nil

К сожалению, F # не поддерживает функторы, поэтому вам придется прибегнуть к некоторым беспорядочным обходным путям. В приведенном выше сценарии я почти всегда сохранял «функтор» в своей структуре данных с некоторыми вспомогательными вспомогательными функциями, чтобы убедиться, что он правильно копируется:

type 'a Tree =
    | Nil of 'a -> 'a -> int
    | Node of 'a -> 'a -> int * 'a tree * 'a * 'a tree

module Tree =
    let comparer = function
        | Nil(f) -> f
        | Node(f, _, _, _) -> f

    let empty f = Nil(f)

    let make (l, x, r) =
        let f = comparer l
        Node(f, l, x, r)

    let rec insert v = function
        | Nil(_) -> make(Nil, v, Nil)
        | Node(f, l, x, r) ->
            if f v x = -1 then make(insert v l, x, r)
            elif f v x = 1 then make(l, x, insert v r)
            else make(l, x, r)

let people = Tree.empty (function x y -> x.LastName.CompareTo(y.LastName))

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

См. Также ocaml-tutorial по модулям.

Примеры в руководстве также полезны.

Ознакомьтесь с этими структурами данных в курсе ocaml:

http://www.cs.cornell.edu/Courses/cs3110/2009fa/lecturenotes.asp

лекция по функтору: http://www.cs.cornell.edu/Courses/cs3110/2009fa/lectures/lec10.html

и реализация расширяемого дерева с использованием функтора: http://www.cs.cornell.edu/Courses/cs3110/2009fa/recitations/rec-splay.html