помощь в использовании функциональных зависимостей

У меня вопрос о функциональных зависимостях. Насколько я понял, например, если я напишу class Graph g a b | g -> a, g -> b, то любой конкретный g может быть связан только с одним типом a и b. Действительно, попытка объявить два экземпляра с одинаковым g и разными a и b не работает.

Однако компилятор (ghc), похоже, не может использовать зависимость в следующем случае:

class (Eq a, Eq b) => Graph g a b | g -> a, g -> b where
    edges :: g -> [b]
    src :: g -> b -> a
    dst :: g -> b -> a

    vertices :: g -> [a]
    vertices g = List.nub $ map (src g) (edges g) ++ map (dst g) (edges g)

class Graph g a b => Subgraph g a b | g -> a, g -> b where
    extVertices :: g -> [b]

data Subgraph1 g where
    Subgraph1 :: Graph g a b => g -> [b] -> Subgraph1 g

instance Graph g a b => Graph (Subgraph1 g) a b where
    vertices (Subgraph1 g _) = vertices g
    edges (Subgraph1 g _) = edges g
    src (Subgraph1 g _) = src g
    dst (Subgraph1 g _) = dst g

Если я доработаю Subgraph1, добавив в сигнатуру типа параметры a и b, то все получится.

data Subgraph1 g a b where
    Subgraph1 :: Graph g a b => g -> [b] -> Subgraph1 g a b

functional-dependencies haskell
person gatoatigrado    schedule 23.07.2011    source источник
comment
Вам нужно использовать связанный тип, а не MPTC и fundep, чтобы избежать заражения типом края подписи вашего типа подграфа. Это одна маленькая часть того, почему они были изобретены.   -  person Edward KMETT    schedule 23.07.2011

Ответы (1)


arrow_upward
4
arrow_downward

Не используйте фундепсы, они слишком болезненные. Используйте связанные типы.

class (Eq (Vertex g), Eq (Edge g)) => Graph g where
  type Edge   g :: *
  type Vertex g :: *

  edges :: g -> [Edge g]
  src   :: g -> Edge g -> Vertex g
  dst   :: g -> Edge g -> Vertex g

  vertices :: g -> [Vertex g]
  vertices g = nub $ map (src g) (edges g) ++ map (dst g) (edges g)

class Graph g => Subgraph g where
  extVertices :: g -> [Edge g]

data Subgraph1 g where
    Subgraph1 :: Graph g => g -> [Edge g] -> Subgraph1 g

instance Graph g => Graph (Subgraph1 g) where
    type Edge (Subgraph1 g) = Edge g
    type Vertex (Subgraph1 g) = Vertex g
    vertices (Subgraph1 g _) = vertices g
    edges (Subgraph1 g _) = edges g
    src (Subgraph1 g _) = src g
    dst (Subgraph1 g _) = dst g

Это выглядит несколько более читабельно. Edge g — это тип ребер g и т. д.

Обратите внимание, что я механически перевел ваш код, не понимая, что делает Subgraph1. Зачем здесь нужен GADT и что означает второй аргумент конструктора данных? Он нигде не используется.

person n. 1.8e9-where's-my-share m.    schedule 23.07.2011
comment
Здорово, красиво смотрится! Я читал о них, но еще не использовал их. GADT использовался, чтобы сказать, что только типы g, которые являются графами, могут использоваться для построения Subgraph1. - person gatoatigrado; 23.07.2011