Использование класса типов для доступа к полям похожих типов данных в Haskell

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

data BasicEdge v w = BasicEdge { b_endpoints :: (v,v), b_weight :: w}
data ColoredEdge v w c = ColoredEdge { c_endpoints :: (v,v), c_weight :: w, color :: c}

class Edge e where
    endpoints :: e -> (v,v)
    weight :: e -> w

instance Edge (BasicEdge v w) where
    endpoints = b_endpoints
    weight = b_weight

instance Edge (ColoredEdge v w c) where
    endpoints = c_endpoints
    weight = c_weight

Проблема 1: v и w в BasicEdge являются переменными другого типа, чем v и w в ColoredEdge. Таким образом, попытка получить к ним доступ полиморфным образом нелепа.

Проблема 2: возвращаемые значения в определении класса Edge являются переменными свободного типа, поэтому их нельзя сопоставлять с возвращаемыми значениями b_endpoints и c_endpoints и т. д.

Мне нужны переменные типа - вершины могут быть символами, строками, целыми числами и т. д. Веса ребер могут быть любыми числами (поплавки полезны для некоторых проблем). Цвета могут быть даже сконструированным типом данных.

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

Заранее спасибо за вашу помощь, и, пожалуйста, поймите, что я провел последний день, пытаясь найти в Интернете руководство. Трудно структурировать поисковый запрос для этой проблемы.


graph polymorphism typeclass haskell
person Mortimer McMire    schedule 18.05.2015    source источник
comment
Спросите себя: как компилятор должен знать, что такое тип v?   -  person AJF    schedule 18.05.2015
comment
Я знаю, что это проблема - см. Проблема 1 и Проблема 2 в моем вопросе. Задача состояла в том, чтобы найти хорошее решение проблемы.   -  person Mortimer McMire    schedule 18.05.2015
comment
Таким образом, семейства типов были бы идеальными в этом случае. Посмотрите на класс IsList пакета GHC.Exts, если хотите понять, что я имею в виду.   -  person AJF    schedule 18.05.2015

Ответы (1)


arrow_upward
6
arrow_downward

Ваш класс типа можно исправить, включив параметры типа v и w в определение класса.

class Edge e where
    endpoints :: e v w -> (v,v)
    weight :: e v w -> w

Теперь e имеет тип * -> * -> *, что означает, что это должен быть тип, который принимает два дополнительных параметра типа, и эти параметры затем используются в endpoints и weight, чтобы фактически связать тип результата с типом ребра.

Однако вам нужно немного изменить тип ColoredEdge, чтобы v и w были двумя последними параметрами, поэтому

data BasicEdge v w = BasicEdge { b_endpoints :: (v,v), b_weight :: w}
data ColoredEdge c v w = ColoredEdge { c_endpoints :: (v,v), c_weight :: w, color :: c}

Теперь вы можете определить экземпляры как

instance Edge BasicEdge where
    endpoints = b_endpoints
    weight = b_weight

instance Edge (ColoredEdge c) where
    endpoints = c_endpoints
    weight = c_weight

Другой вариант — использовать расширение языка TypeFamilies и сделать типы вершин и весов синонимами ассоциированных типов в классе Edge. Таким образом, порядок ввода параметров в типы экземпляров становится неактуальным.

{-# LANGUAGE TypeFamilies #-}

class Edge e where
    type Vertex e
    type Weight e

    endpoints :: e -> (Vertex e, Vertex e)
    weight :: e -> Weight e

instance Edge (BasicEdge v w) where
    type Vertex (BasicEdge v w) = v
    type Weight (BasicEdge v w) = w

    endpoints = b_endpoints
    weight = b_weight

instance Edge (ColoredEdge v w c) where
    type Vertex (ColoredEdge v w c) = v
    type Weight (ColoredEdge v w c) = w

    endpoints = c_endpoints
    weight = c_weight

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

data Edge v w d = Edge { endpoints :: (v,v), weight :: w, edgeData :: d }

Теперь вы можете закрасить d или запись, содержащую несколько полей данных для ребра, и по-прежнему запрашивать форму графика в общем виде.

Ваши исходные типы ребер теперь могут быть представлены синонимами типов

type BasicEdge   v w   = Edge v w ()
type ColoredEdge v w c = Edge v w c
person shang    schedule 18.05.2015
comment
Я начал писать ответ и был так занят описанием fundeps и AT, что совершенно пропустил очевидное решение Haskell 2010. Отлично сработано! - person MathematicalOrchid; 18.05.2015
comment
Ух ты. Меня так расстроила мысль о неиспользуемой переменной типа к простому ребру, и мне почему-то не пришло в голову, что я могу просто скрыть это синонимом типа. Хотя ваш первый ответ имеет смысл, я бы предпочел пойти по минималистскому пути - как вы сказали, использование классов типов в этой ситуации кажется неправильным. Большое спасибо за Вашу помощь. - person Mortimer McMire; 18.05.2015
comment
Я очень люблю шрифтовые семейства. Отличный ответ, отличный пример. - person AJF; 18.05.2015