时间戳

首页 > 解决方案 > Haskell NB：'Edge' 是一个非内射类型族

algorithm - Haskell NB：'Edge' 是一个非内射类型族

问题描述

我正在尝试在 Haskell 中编写自己的图形库，以便在代码出现时使用。我正在尝试使用一个用于图形的类和一个使用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)

为了表示InfinityDijkstra 算法中未访问节点的值，我创建了一个 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 gwheregraph :: 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似乎对我没有任何作用的语言扩展。我做错了什么，如何修复我的代码？先感谢您。

标签： algorithmhaskelltypeclassdijkstratype-families

解决方案

操作Set (Node g)并Map (Node 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)) => ...

推荐阅读