Описание класса типов для общих графов в Haskell

Я пытаюсь написать класс типов для графов. В принципе, класс typeclass выглядит следующим образом: 

class Graph g where
  adjacentNodes :: g n -> n -> [n]

, в котором я использую n для представления типа узлов.

Тогда у меня есть следующее Graph, определенное следующим образом: 

data FiniteGraph n = FiniteGraph { runFiniteGraph :: Array n [n] }

, где Array принимается из стандартного контейнера Data.Array, структура должна представлять конечный граф таким образом, чтобы каждый узел отображался на соседние узлы.

Здесь возникает проблема, когда я пытаюсь сделать FiniteGraph экземпляр Graph.

instance Graph FiniteGraph where
  adjacentNodes g n = (runFiniteGraph g) ! n

К сожалению, это не работает, потому что оператор ! требует ограничения Ix n, но я не нахожу, где его объявить.

Я ожидаю, что объявление экземпляра будет примерно таким: 

instance (Ix n) => Graph (FiniteGraph n) where { ... }
Но для этого требуется, чтобы g в class Graph g имел вид * вместо * -> *, такой, что у меня не было бы места, где показать, что n зависит от g.

Так что я могу с этим сделать? Спасибо.

1 4
haskell typeclass polymorphism

1 ответ:

Это можно сделать после добавления второго парама в класс Graph.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
import Data.Array

class Graph g n | n -> g where
  adjacentNodes :: g n -> n -> [n]

data FiniteGraph n = FiniteGraph { runFiniteGraph :: Array n [n] }

instance Ix n => Graph FiniteGraph n where
  adjacentNodes g n = (runFiniteGraph g) ! n

Это имеет смысл, если подумать: граф требует понятия вершины.

5