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

但这需要 g在 class Graph g有种 *而不是 * -> * ，这样我就无处可展示 n依赖 g .

那么我能用它做什么呢？谢谢。

Answer 1

可以在向 Graph 添加第二个参数后完成。类(class)。

{-# 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

如果您考虑一下，这是有道理的:图需要顶点的概念。