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

Question

我正在尝试用 Haskell 编写自己的图形库，以便在代码出现时使用。我正在尝试使用一个图形类和一个使用 Data.Map 的具体实现。我正在尝试编写 Dijkstra 算法，但在类型系列方面遇到了一些麻烦。我有以下类型类和具体实现:

{-# 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 值，我创建了一个 sum 数据类型:

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 map 的当前距离。

currDist <- M.lookup curr vals

如果我执行以下操作，这将在 go 函数之外起作用:

currDist = M.lookup current vals

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

但是，在 do block 内我收到此错误:

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

无法推断部分让我觉得我需要给它一个类型注释，所以我这样做了:

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)

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

Answer 1

对Set(节点g)和Map(节点g)的操作要求您能够比较节点。这就是 Ord (Node g) 约束所代表的内容。您为 go 提供的类型表示它适用于 Node g 的任何定义，甚至是那些无法比较的定义。该错误告诉您，当您使用 M.lookup 时，需要一个 Ord (Node g) 约束，但没有办法满足它。

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

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

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