Достижение полиморфизма в функциональном программировании

Question

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

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

В ООП, которая может быть относительно хорошо обработана с использованием полиморфизма: либо с помощью композиции + наследования, либо с использованием подхода на основе прототипов.

В FP я немного застрял между:

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

Каковы рекомендуемые функциональные подходы для такой ситуации? Есть ли другие хорошие альтернативы?

Answer 1

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

Если вы хотите решить проблему с помощью виртуальных методов, это вполне разумный подход. Что касается отделения функций от данных, то для начала это явно не функциональное понятие. Я считаю, что основополагающим принципом функционального программирования является то, что функции являются данными. А что касается вашего ощущения, что вы моделируете виртуальную функцию, я бы сказал, что это вовсе не симуляция. Это виртуальная таблица функций, и это совершенно нормально.

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

Полиморфизм в ООП во многом похож на «экзистенциальную квантификацию» в логике - полиморфное значение имеет НЕКОТОРЫЙ тип времени выполнения, но вы не знаете, что это такое. Во многих функциональных языках программирования полиморфизм больше похож на «универсальную квантификацию» - полиморфное значение может быть создано для ЛЮБОГО совместимого типа, который хочет пользователь. Это две стороны одной и той же монеты (в частности, они меняются местами в зависимости от того, смотрите ли вы на функцию «изнутри» или «снаружи»), но при разработке язык, чтобы "сделать монету честной", особенно при наличии других языковых особенностей, таких как субтипирование или полиморфизм с более высоким родом (полиморфизм над полиморфными типами).

Если это поможет, вы можете подумать о полиморфизме в функциональных языках как о чем-то очень похожем на «дженерики» в C # или Java, потому что это именно тот тип полиморфизма, который предпочитают, например, ML и Haskell.

Answer 2

Ну, в Haskell вы всегда можете создать класс типов для достижения своего рода полиморфизма.По сути, это определение функций, которые обрабатываются для разных типов.Примерами являются классы Eq и Show:

data Foo = Bar | Baz

instance Show Foo where
    show Bar = 'bar'
    show Baz = 'baz'

main = putStrLn $ show Bar

Функция show :: (Show a) => a -> String определена для каждого типа данных, который создает класс типов Show.Компилятор находит для вас правильную функцию, в зависимости от типа.

Это позволяет определять функции более широко, например:

compare a b = a < b

будет работать с любым типом класса типов Ord.Это не совсем то же самое, что ООП, но вы даже можете наследовать классы типов следующим образом:

class (Show a) => Combinator a where
    combine :: a -> a -> String

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

Это не завершено, и, насколько я знаю, многие языки FP не имеют классов типов.OCaml этого не делает, он толкает это к своей ООП-части.И Схема не имеет никаких типов.Но в Haskell это мощный способ достичь своего рода полиморфизма в определенных пределах.

Чтобы пойти еще дальше, более новые расширения стандарта 2010 позволяют семейства типов и тому подобное.

Надеюсь, это помоглоВы немного.

Answer 3

Кто сказал,

определение чистых функций отдельно от данных

- это лучшая практика?

Если вам нужны полиморфные объекты, вам нужны объекты.На функциональном языке объекты могут быть созданы путем склеивания набора «чистых данных» с набором «чистых функций», работающих с этими данными.Это работает даже без концепции класса.В этом смысле класс - это не что иное, как кусок кода, который создает объекты с таким же набором связанных «чистых функций».

И полиморфные объекты создаются путем замены некоторых из этих функций объекта различными функциями с одинаковой сигнатурой.

Если вы хотите узнать больше о том, как реализовать объекты на функциональном языке (как Схема), загляните в эту книгу:

Абельсон / Суссман: "Структура и Интерпретация компьютерных программ"

Answer 4

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

Причина, по которой схема не имеет встроенной системы, заключается в том, что использование неправильной объектной системы для проблемных отведенийко всем видам неприятностей, так что если вы дизайнер языка, какой выбрать?Одиночное наследование в одной посылке не справится с «множественными факторами, приводящими к полиморфному поведению, поэтому потенциально экспоненциально много разных комбинаций поведения».просто дает вам базовый инструментарий, из которого вы можете построить тот, который вам нужен.

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

В clojure у вас фактически есть встроенная система объектов / диспетчеризации, встроенная с помощью мультиметодов, и одним из ее преимуществ по сравнению с традиционным подходом является то, что он может выполнять диспетчеризацию по типам всех аргументов.Вы можете (по-видимому) также использовать систему иерархии для предоставления функций, подобных наследованию, хотя я никогда не использовал ее, поэтому вам следует взять это cum grano salis .

Но если вынужно что-то отличное от схемы объекта, выбранной разработчиком языка, вы можете просто сделать одну (или несколько) подходящую.

Это действительно то, что вы предлагаете выше.

Создайте то, что вам нужноПолучите все это, спрячьте детали с помощью макросов.

Аргумент между FP и OO не в том, плоха ли абстракция данных, а в том, является ли система абстракции данных местом, где нужно заполнить все отдельные проблемы:программа.

«Я считаю, что язык программирования должен позволять определять новые типы данных. Я не считаю, что программа должна состоять исключительно из определений новых типов данных».

Answer 5

http://www.haskell.org/haskellwiki/OOP_vs_type_classes#Everything_is_an_object.3F красиво обсуждает некоторые решения.