Реструктуризация типа данных ООП типа Haskell

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

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

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

data Polygon
= Quad Point Point
| Triangle Point Point Point
| RegularNGon Int Radius
| ...

Но это теряет часть структуры и может быть действительно удовлетворительно выполнено только для одного уровня иерархии. Typeclasses можно использовать для реализации формы наследования и подструктуры в том, что класс Polygon может быть подклассом Shape, и, возможно, все экземпляры Polygon имеют реализации для centroid :: Point, а также vertices :: [Point], но это кажется неудовлетворительным. Что было бы хорошим способом захвата структуры картины в Haskell?

Ответ 1

Вы можете использовать типы сумм для представления всей иерархии без потери структуры. Что-то вроде этого сделало бы это:

data Shape = IsPoint Point
           | IsLine Line 
           | IsPolygon Polygon

data Point = Point { x :: Int, y :: Int }

data Line = Line { a :: Point, b :: Point }

data Polygon = IsTriangle Triangle
             | IsQuad Quad
             | ...

И так далее. Основной шаблон состоит в том, что вы переводите каждый абстрактный класс OO в тип суммы Haskell, причем каждый из его непосредственных подклассов OO (которые могут быть абстрактными) в качестве вариантов типа суммы. Конкретные классы - это типы продуктов/записей с фактическими элементами данных в них. ¹

То, что вы теряете по сравнению с ООП, к которому вы привыкли, моделируя вещи таким образом, - это не способность представлять вашу иерархию, а способность расширять ее, не касаясь существующего кода. Типы сумм "закрыты", где наследование ОО "открыто". Если позже вы решите, что хотите Circle для Shape, вы должны добавить его в Shape, а затем добавить для него случаи, когда вы сопоставляете шаблоны с Shape.

Однако такая иерархия, вероятно, требует довольно либерального понижения в OO. Например, если вам нужна функция, которая может определить, пересекаются ли две формы, что, вероятно, является абстрактным методом на Shape, например Shape.intersects(Shape other), поэтому каждый подтип получает возможность писать свою собственную реализацию. Но когда я пишу Rectangle.intersects(Shape other), это в принципе невозможно в общем, не зная, какие другие подклассы Shape находятся там. Мне нужно будет использовать isinstance проверки, чтобы увидеть, что на самом деле other. Но это на самом деле означает, что я, вероятно, не могу просто добавить мой новый подкласс Circle, не пересматривая существующий код; иерархия OO, где необходимы проверки состояния, де-факто так же "закрыта", как иерархия типов сумм Haskell. В основном сопоставление шаблонов на одном из типов сумм, генерируемых при применении этого шаблона, эквивалентно isinstancing и downcasting в версии OO. Только потому, что типы сумм исчерпывающе известны компилятору (возможно только , потому что они закрыты), если я добавлю случай Circle к Shape, компилятор сможет рассказать мне обо всех места, которые мне нужно пересмотреть, чтобы обработать этот случай. ²

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

Но мой "реальный" ответ на "как я представляю иерархии типов OO в Haskell", к сожалению, является банальным: я этого не делаю. Я проектирую по-разному в Haskell, чем в языках OO ⁴ и на практике это просто не огромная проблема. Но, чтобы сказать, как я буду дизайн этого случая по-другому, мне нужно будет узнать больше о том, для чего вы их используете. Например, вы можете сделать что-то вроде представления формы как функции Point -> Bool (которая говорит вам, присутствует ли какая-либо данная точка внутри формы) и имеет такие вещи, как circle :: Point -> Int -> (Point -> Bool) для генерации таких функций, соответствующих нормальным формам; это представление является удивительным для формирования составных форм пересечения/объединения, ничего не зная о них (intersect shapeA shapeB = \point -> shapeA point && shapeB point), но ужасно для вычисления таких вещей, как области и окружности.

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

² Если вы используете шаблоны catch-all, это предупреждение может быть не исчерпывающим, поэтому оно не всегда является доказательством пули, но насколько доказательством этого является то, как вы кодируете.

³Если вы не выбираете информацию типа времени выполнения с таким решением, как Typeable, но это не невидимое изменение; ваши звонящие также должны выбрать в нем.

⁴ На самом деле я, вероятно, не буду создавать такую иерархию, как это даже в языках OO. Я считаю, что это не так полезно, как вы думаете в реальных программах, поэтому совет "предпочтение композиции над наследованием".

Ответ 2

Возможно, вы ищете эквивалент Haskell динамическую рассылку, чтобы вы могли хранить неоднородный список значений, поддерживающих различные реализации общего Shape.

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

{-# LANGUAGE ExistentialQuantification #-}
...
class Shape a where
    bounds :: a -> AABB
    draw   :: a -> IO ()

data AnyShape = forall a. Shape a => AnyShape a

Это позволяет объявлять экземпляры в стиле с открытым концом:

data Line = Line Point Point
instance Shape Line where ...

data Circle= Circle {center :: Point, radius :: Double}
instance Shape Circle where ...

...

Затем вы можете создать свой гетерогенный список:

shapes = [AnyShape(Line a b),
          AnyShape(Circle a 3.0),
          AnyShape(Circle b 1.8)]

и использовать его в едином виде:

drawIn box xs = sequence_ [draw s | AnyShape s <- xs, bounds s `hits` box]

Обратите внимание, что вам необходимо развернуть свой AnyShape, чтобы использовать функции интерфейса class Shape. Также обратите внимание, что вы должны использовать функции класса для доступа к своим гетерогенным данным - нет другого способа "понизить" развернутое экзистенциальное значение s! Его тип имеет смысл только в пределах локальной области, поэтому компилятор не позволит ему сбежать.

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