Haskell 注意：“Edge”是一个非单射类型族

Question

我正在尝试编写我自己的图形库Haskell以供在代码出现时使用。我正在尝试对图表使用 class，并使用 Data.Map 进行具体实现。我正在尝试编写 Dijkstra 的算法，但我运行在类型族方面遇到了一些麻烦。我有以下typeclass和具体实现：

{-# LANGUAGE TypeFamilies, AllowAmbiguousTypes, ScopedTypeVariables, TypeFamilyDependencies #-}

class Graph g where
  type Node g
  type Edge g
  nodeSet :: g -> S.Set (Node g)
  neighbours :: g -> (Node g) -> Maybe [(Edge g, Node g)]

data MapGraph e n = MapGraph {mGraph :: M.Map n [(e,n)]} deriving Show
instance (Num e,Ord e,Ord n) => Graph (MapGraph e n) where
  type Node (MapGraph e n) = n
  type Edge (MapGraph e n) = e
  nodeSet mapGraph = S.fromList $ M.keys $ mGraph mapGraph
  neighbours mapGraph node = M.lookup node (mGraph mapGraph)

为了表示 Dijkstra 算法中未访问节点的 Infinity 值，我创建了一个求和数据类型：

data MaxBoundedNum a = Inf | Num a deriving Show

我正在尝试处理算法的递归函数，该函数将接收图形、当前节点、目标节点、未访问集以及节点图及其距源节点的长度。下面的骨架函数似乎是我想要的：

go :: (Graph g) =>
  g -> (Node g) -> (Node g) ->
  S.Set (Node g) ->
  M.Map (Node g) (MaxBoundedNum (Edge g)) ->
  Maybe (M.Map (Node g) (MaxBoundedNum (Edge g)))
go graph curr dest uset vals = do
  currNeighbours <- neighbours graph curr
  undefined

这似乎适用于 graph g，其中 graph :: MapGraph Int String

go graph
  :: [Char]
     -> [Char]
     -> S.Set [Char]
     -> M.Map [Char] (MaxBoundedNum Int)
     -> Maybe (M.Map [Char] (MaxBoundedNum Int))

我的 go 函数的下一部分需要从 vals 地图查找当前距离。

currDist <- M.lookup curr vals

如果我执行以下操作，这将在 go 函数之外工作：

currDist = M.lookup current vals

*Main> :t currDist
currDist :: Maybe (MaxBoundedNum Integer)

然而，在 do 块中我得到这个错误：

Could not deduce (Ord (Node g)) arising from a use of ‘M.lookup’
      from the context: Graph g
        bound by the type signature for:
                   go :: forall g.
                         Graph g =>
                         g
                         -> Node g
                         -> Node g
                         -> S.Set (Node g)
                         -> M.Map (Node g) (MaxBoundedNum (Edge g))
                         -> Maybe (M.Map (Node g) (MaxBoundedNum (Edge g)))
        at WithClass.hs:(96,1)-(100,49)
    • In a stmt of a 'do' block: currDist <- M.lookup curr vals

Could not deduce 部分让我觉得我需要给它一个类型注释，所以我这样做了：

currDist <- M.lookup curr vals :: Maybe (MaxBoundedNum (Edge g))

但这给了我这个错误：

WithClass.hs:102:15: error:
    • Couldn't match type ‘Edge g’ with ‘Edge g1’
      Expected type: Maybe (MaxBoundedNum (Edge g1))
        Actual type: Maybe (MaxBoundedNum (Edge g))
      NB: ‘Edge’ is a non-injective type family
    • In a stmt of a 'do' block:
        currDist <- M.lookup curr vals :: Maybe (MaxBoundedNum (Edge g))
      In the expression:
        do currDist <- M.lookup curr vals :: Maybe (MaxBoundedNum (Edge g))
           currNeighbours <- neighbours graph curr
           undefined
      In an equation for ‘go’:
          go graph curr dest uset vals
            = do currDist <- M.lookup curr vals ::
                               Maybe (MaxBoundedNum (Edge g))
                 currNeighbours <- neighbours graph curr
                 undefined
    • Relevant bindings include
        vals :: M.Map (Node g) (MaxBoundedNum (Edge g))
          (bound at WithClass.hs:101:25)
        uset :: S.Set (Node g) (bound at WithClass.hs:101:20)
        dest :: Node g (bound at WithClass.hs:101:15)
        curr :: Node g (bound at WithClass.hs:101:10)
        graph :: g (bound at WithClass.hs:101:4)
        go :: g
              -> Node g
              -> Node g
              -> S.Set (Node g)
              -> M.Map (Node g) (MaxBoundedNum (Edge g))
              -> Maybe (M.Map (Node g) (MaxBoundedNum (Edge g)))
          (bound at WithClass.hs:101:1)

我查看了，但接受的答案只是说要添加 TypeFamilyDependencies 语言扩展，这似乎对我没有任何作用。我做错了什么以及如何修复我的代码？提前谢谢你。

Answer 1

Set (Node g) 和 Map (Node g) 上的操作要求您能够比较节点。这就是 Ord (Node g) 约束所代表的意思。您为 go 提供的类型表示它适用于 any 定义的 Node g，即使是那些无法比较的定义。该错误告诉您，当您使用 M.lookup 时，需要 Ord (Node g) 约束，但无法满足它。

您可以通过将其添加到 go 的签名来满足该约束：

{-# LANGUAGE FlexibleConstraints #-}  -- Also enable this extension

go :: (Graph g, Ord (Node g)) => ...

Haskell 注意：“Edge”是一个非单射类型族

Haskell NB: ‘Edge’ is a non-injective type family

algorithm

haskell

dijkstra

typeclass

type-families