描述Haskell中一般图的类型类

Question

我正在尝试为图形编写类型类.基本上,类型类看起来像:

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 { ... }

但是这需要gin 而不是class Graph g那种,以至于我无法在哪里显示依赖.** -> *ng

那我该怎么办呢？谢谢.

Answer 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

如果你考虑它,这是有道理的:图形需要顶点的概念.