Haskell не может соответствовать типу, утверждает жесткую переменную

Question

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

data Node = Node { label :: Char
                 , index :: Int
                 } deriving (Ord, Eq)
type Graph edgeType = ([Node], [edgeType])
data Edge = DirectedEdge   {h :: Node, t :: Node}
          | UndirectedEdge {a :: Node, b :: Node}
instance Show Node where
    show n = ['(', label n, ')']
instance Show Edge where
    show (DirectedEdge   h t) = show h ++ "->" ++ show t
    show (UndirectedEdge a b) = show a ++ "-"  ++ show b

Итак, я различаю направленные и ненаправленные края. Граф должен иметь только ребра любого типа. У меня также есть следующее:

nodes :: [Node]
nodes = zipWith Node ['a'..] [0..]

emptyGraph :: [Node] -> Graph edgeType
emptyGraph ns = (ns, [])

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

connect :: Graph edgeType -> Node -> Graph edgeType
connect (ns, es) n = (n:ns, e:es)
    where e = UndirectedEdge n (head ns)

Но это дает следующую ошибку:

Couldn't match type `edgeType' with `Edge'
  `edgeType' is a rigid type variable bound by
             the type signature for
               connect :: Graph edgeType -> Node -> Graph edgeType

Как лучше всего достичь того, чего я пытаюсь достичь?

Answer 1

Возможно, вы хотите иметь два отдельных типа ребер вместо Edge

newtype DirectedEdge = DirectedEdge { h :: Node, t :: Node}
newtype UndirectedEdge = UndirectedEdge { a :: Node, b :: Node}

И вам, вероятно, нужен какой-то класс типов, который возвращает вам (Node, Node) с произвольным преимуществом:

class HasNodeEndpoints a where
  endpoints :: a -> (Node, Node)

-- obvious instances for DirectedEdge and UndirectedEdge

Затем, когда вы захотите поговорить о произвольных графах, вы напишите функции, которые работают на Graph a и, вероятно, на HasNodeEndpoints a => Graph a. Алгоритмы, которые заботятся о виде графов, будут работать на Graph DirectedEdge и Graph UndirectedEdge для ориентированных и неориентированных графов соответственно.

Еще одно естественное расширение будет помечено направленными и ненаправленными ребрами.

class HasLabeled a where
  type Label a -- associated type synonym
  label :: a -> Label a
  updateLabel :: a -> (Label a -> Label a) -> a

-- now define data types and instances for labeled directed and undirected edges

Answer 2

Поскольку вы выбираете конкретный тип ребра, а именно Edge, когда вы используете UndirectedEdge, в результате ваш график больше не будет полиморфным по типу ребра. Он должен иметь тип:

connect :: Graph Edge -> Node -> Graph Edge
connect (ns, es) n = (n:ns, e:es)
    where e = UndirectedEdge n (head ns)

Так как нет другого типа, ваши ребра могут быть, если использовать UndirectedEdge.

.

---

Кроме того, я бы использовал аннотации строгости на узлах, просто как вопрос гигиены:

data Node = Node { label :: !Char
                 , index :: !Int
                 } deriving (Ord, Eq)