Динамическая отправка в Haskell

Программы, написанные, например, на Java, во многом зависят от динамической отправки.

Как такие программы выражаются на функциональных языках, таких как Haskell?

Другими словами, как Хаскель может выразить идею под "динамическим распределением"?

Ответ 1

Ответ обманчиво прост: функции высшего порядка. Объект с виртуальными методами на языке ОО представляет собой не что иное, как прославленную запись функций вместе с некоторым локальным состоянием. В Haskell вы можете напрямую использовать записи функций и сохранять локальные состояния в их замыканиях.

Более конкретно, объект OO состоит из:

Указатель (vptr) на vtable (таблица виртуальных методов), которая содержит реализации для виртуальных методов класса объекта. Другими словами, набор функциональных указателей; запись функций. В частности, каждая функция имеет скрытый параметр, который является самим объектом, который передается неявно.
Данные членов объекта (локальное состояние)

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

Например, рассмотрим интерфейс Java Comparator:

public interface Comparator<T> {
    int compare(T o1, T o2); // virtual (per default)
}

И предположим, что вы хотите использовать его для сортировки списка строк по N-ным символам строк (предположим, что они достаточно длинные). Вы бы определили класс:

public class MyComparator implements Comparator<String> {
    private final int _n;

    MyComparator(int n) {
        _n = n;
    }

    int compare(String s1, String s2) {
        return s1.charAt(_n) - s2.charAt(_n);
    }
}

А потом вы используете его:

Collections.sort(myList, new MyComparator(5));

В Haskell вы бы сделали это так:

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

myComparator :: Int -> (String -> String -> Ordering)
myComparator n = \s1 s2 -> (s1 !! n) 'compare' (s2 !! n)
-- n is implicitly stored in the closure of the function we return

foo = sortBy (myComparator 5) myList

Если вы не знакомы с Haskell, вот как это будет выглядеть в псевдо-Java: (Я собираюсь сделать это только один раз)

public void <T> sortBy(List<T> list, Ordering FUNCTION(T, T) comparator) { ... }

public (Ordering FUNCTION(String, String)) myComparator(int n) {
    return FUNCTION(String s1, String s2) {
        return s1[n].compare(s2[n]);
    }
}

public void foo() {
    sortBy(myList, myComparator(5));
}

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

Рассмотрим более сложный пример виджета с обработчиками событий:

public class Widget {
    public void onMouseClick(int x, int y) { }
    public void onKeyPress(Key key) { }
    public void paint() { }
    ...
}

public class MyWidget extends Widget {
    private Foo _foo;
    private Bar _bar;
    MyWidget(...) {
        _foo = something;
        _bar = something; 
    }
    public void onMouseClick(int x, int y) {
        ...do stuff with _foo and _bar...
    }
}

В Haskell вы можете сделать это следующим образом:

data Widget = Widget {
    onMouseClick :: Int -> Int -> IO (),
    onKeyPress   :: Key -> IO (),
    paint        :: IO (),
    ...
}

constructMyWidget :: ... -> IO Widget
constructMyWidget = do
    foo <- newIORef someFoo
    bar <- newIORef someBar
    return $ Widget {
        onMouseClick = \x y -> do
            ... do stuff with foo and bar ...,
        onKeyPress = \key -> do ...,
        paint = do ...
    }

Еще раз отметим, что после начального Widget мы не определяли никаких типов. Мы только написали функцию для создания записи функций и хранения вещей в их замыканиях. Что, в большинстве случаев, также является единственной причиной для определения подкласса в ОО-языке. Единственное отличие от нашего предыдущего примера состоит в том, что вместо одной функции существует множественное число, которое в случае Java кодируется простым помещением в интерфейс нескольких функций (и его реализаций), а в Haskell - передачей записи функций вместо единственная функция. (Мы могли бы передать запись, содержащую одну функцию в предыдущем примере, но нам это не нравилось.)

(Стоит отметить, что в большинстве случаев вам не требуется динамическая диспетчеризация. Если вы просто хотите отсортировать список на основе порядка по умолчанию для типа, то вы просто использовали бы sort :: Ord a => [a] -> [a], который использует Ord экземпляр, определенный для данного типа a, который выбирается статически.)

Динамическая отправка на основе типов

Одно из различий между подходом Java и подходом Haskell, описанным выше, состоит в том, что в подходе Java поведение объекта (за исключением его локального состояния) определяется его типом (или, мягко говоря, для каждой реализации требуется новый тип). В Haskell мы делаем записи функций так, как нам нравится. В большинстве случаев это чистый выигрыш (гибкость достигнута, ничего не потеряно), но предположим, что по какой-то причине мы хотим, чтобы это был способ Java. В этом случае путь, о котором говорилось в других ответах, - это классы типов и экзистенциалы.

Чтобы продолжить наш пример Widget, предположим, что мы хотим, чтобы реализация Widget следовала из его типа (чтобы требовался новый тип для каждой реализации). Мы определяем класс типа для сопоставления типа с его реализацией:

-- the same record as before, we just gave it a different name
data WidgetImpl = WidgetImpl {
    onMouseClick :: Int -> Int -> IO (),
    onKeyPress   :: Key -> IO (),
    paint        :: IO (),
    ...
}

class IsWidget a where
    widgetImpl :: a -> WidgetImpl

data Widget = forall a. IsWidget a => Widget a

sendClick :: Int -> Int -> Widget -> IO ()
sendClick x y (Widget a) = onMouseClick (widgetImpl a) x y

data MyWidget = MyWidget {
    foo :: IORef Foo,
    bar :: IORef Bar
}

constructMyWidget :: ... -> IO MyWidget
constructMyWidget = do
    foo_ <- newIORef someFoo
    bar_ <- newIORef someBar
    return $ MyWidget {
        foo = foo_,
        bar = bar_
    }

instance IsWidget MyWidget where
    widgetImpl myWidget = WidgetImpl {
            onMouseClick = \x y -> do
                ... do stuff with (foo myWidget) and (bar myWidget) ...,
            onKeyPress = \key -> do ...,
            paint = do ...
        }

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

class IsWidget a where
    onMouseClick :: Int -> Int -> a -> IO ()
    onKeyPress   :: Key -> a -> IO ()
    paint        :: a -> IO ()
    ...

instance IsWidget MyWidget where
    onMouseClick x y myWidget = ... do stuff with (foo myWidget) and (bar myWidget) ...
    onKeyPress key myWidget = ...
    paint myWidget = ...

sendClick :: Int -> Int -> Widget -> IO ()
sendClick x y (Widget a) = onMouseClick x y a

-- the rest is unchanged from above

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

Одно преимущество, о котором я могу подумать, состоит в том, что, хотя у Haskell нет подтипов, у него есть "подклассы" (вероятно, лучше называть суб-интерфейсом или суб-ограничением). Например, вы можете сделать:

class IsWidget a => IsWidgetExtra a where
    ...additional methods to implement...

и затем с любым типом, для которого у вас есть IsWidgetExtra, вы также можете легко использовать методы IsWidget. Единственная альтернатива в подходе на основе записей заключается в том, чтобы иметь записи внутри записей, что включает в себя ручную упаковку и развертывание внутренних записей. Но это было бы выгодно только в том случае, если вы хотите явно эмулировать глубокую иерархию классов языка OO, что, в свою очередь, вы бы сделали, только если бы вы хотели усложнить себе жизнь. (Также обратите внимание, что в Haskell нет встроенного способа динамического приведения вниз с IsWidget до IsWidgetExtra. Но есть ifcxt)

(Как насчет преимуществ подхода, основанного на записях? Помимо того, что нет необходимости определять новый тип каждый раз, когда вы хотите создать что-то новое, записи - это простые вещи на уровне значений, и значениями гораздо проще манипулировать, чем типами. Вы могли бы Например, напишите функцию, которая принимает Widget в качестве аргумента и создает на его основе новый Widget, в котором некоторые вещи различаются, а другие остаются неизменными. Это похоже на подклассы из параметра шаблона в C++, только менее запутанно.)

Глоссарий

Функция высшего порядка: функция, которая принимает другие функции в качестве аргументов (или возвращает их в качестве результатов)
Запись: struct (класс с открытыми членами данных и ничего больше). Также известен как словарь.
Закрытие: функциональные языки (и многие другие) позволяют вам определять локальные функции (функции в функциях, лямбда-выражения), которые ссылаются на объекты в области видимости на сайте определения (например, аргументы внешней функции), которые вы обычно не ожидаете храниться, но есть в функции "замыкание". В качестве альтернативы, если у вас есть такая функция, как plus, которая принимает два целых числа и возвращает целое число, вы можете применить ее только к одному аргументу, скажем, 5, и результатом будет функция, которая принимает целое число и возвращает целое число, добавив к нему 5 - в этом случае 5 также сохраняется в результирующем закрытии функции. (В других контекстах "замыкание" также иногда используется для обозначения "функции с замыканием".)
Тип class: не то же самое, что класс в языке OO. Вроде как интерфейс, но тоже очень разные. Смотрите здесь.

ОБНОВЛЕНИЕ 29-11-14: Хотя я думаю, что ядро этого ответа по-прежнему в основном верно (HOF в Хаскеле соответствуют виртуальным методам в ООП), мои оценочные суждения выросли с некоторой нюансом с тех пор, как я его написал. В частности, сейчас я думаю, что ни подход к Haskell, ни к ООП не является строго "более фундаментальным", чем другой. Смотрите этот комментарий Reddit.

Ответ 2

Удивительно, как часто вам не нужна динамическая отправка, просто полиморфизм.

Например, если вы собираетесь написать функцию, которая сортирует все данные в списке, вы хотите, чтобы она была полиморфной. (I.e., вы не хотите, чтобы вручную реализовать эту функцию для каждого отдельного типа, это было бы плохо.) Но на самом деле вам не нужна динамика; вы знаете во время компиляции, что на самом деле в списке или списках, которые вы хотите отсортировать. Таким образом, вам вообще не нужен поиск типа во время выполнения.

В Haskell, если вы просто хотите переместить вещи вокруг, и вам не нужно знать или заботиться о том, какой тип он есть, вы можете использовать так называемый "параметрический полиморфизм", который примерно похож на Java-дженерики или шаблоны С++, Если вам нужно применить функцию к данным (например, для сортировки данных вам понадобятся сравнения заказов), вы можете передать функцию для этого в качестве аргумента. В качестве альтернативы, у Haskell есть нечто, что немного похоже на интерфейс Java, и вы можете сказать, что "эта функция сортировки принимает любые типы данных, которые реализуют этот интерфейс".

Пока, динамическая отправка вообще не статична. Обратите также внимание на то, что, поскольку вы можете передавать функции в качестве аргументов, вы можете вручную "отгружать" вручную.

Если вам действительно нужна фактическая динамическая отправка, вы можете использовать "экзистенциальные типы", или вы можете использовать библиотеку Data.Dynamic и подобные трюки.

Ответ 3

Ad-hoc полиморфизм выполняется через typeclasses. Более OOP-подобный DD эмулируется с экзистенциальными типами.

Ответ 4

Возможно, вам нужен сопоставление образцов ADT plus?

data Animal = Dog {dogName :: String}
            | Cat {catName :: String}
            | Unicorn

say :: Animal -> String
say (Dog {dogName = name}) = "Woof Woof, my name is " ++ name
say (Cat {catName = name}) = "Meow meow, my name is " ++ name
say Unicorn = "Unicorns do not talk"