haskell - 不小心反勾一个非二元函数会产生奇怪的行为

Question

这是违规代码( also on lpaste.net ):

module Data.Graph.Dijkstra
       ( dijkstra
       , dijkstraPath
       ) where

-- Graph library import
import Data.Graph.Inductive hiding (dijkstra)

-- Priority queue import
import qualified Data.PQueue.Prio.Min as PQ

-- Standard imports
import Data.List (find)
import Data.Maybe (fromJust)
import Data.Monoid

-- Internal routine implementing Dijkstra's shortest paths
-- algorithm. Deemed internal because it needs to be kickstarted with
-- a singleton node queue. Based on FGL's current implementation of
-- Dijkstra.
dijkstraInternal ::
  (Graph gr, Ord b, Monoid b) => gr a b -> PQ.MinPQueue b [Node] -> [[Node]]
dijkstraInternal g q
  | PQ.null q = []
  | otherwise =
    case match v g of
      (Just cxt,g') -> p:dijkstraInternal  g' (PQ.unions (q' : expand cxt minDist p))
      (Nothing, g') -> dijkstraInternal g' q'
  where ((minDist,p@(v:_)), q') = PQ.deleteFindMin q
        expand (_,_,_,s) dist pathToC =
          map (\(edgeCost,n) -> PQ.singleton (dist `mappend` edgeCost) (n:pathToC)) s

-- Given a graph and a start node, returns a list of lists of nodes
-- corresponding to the shortest paths from the start to all other
-- nodes, where the edge costs are accumulated according to the Monoid
-- instance of the edge label type and costs are compared by the edge
-- label's Ord instance.
dijkstra :: (Graph gr, Ord b, Monoid b) => gr a b -> Node -> [[Node]]
dijkstra g start = dijkstraInternal g (PQ.singleton `mempty` [start])  -- !!!

dijkstraPath :: (Graph gr, Ord b, Monoid b) => gr a b -> Node -> Node -> [LNode a]
dijkstraPath g start goal =
  let paths = dijkstra g start
      pathNodes  = find ((goal ==) . head) paths -- Can paths be empty?
  in
   case pathNodes of
     Nothing -> []
     Just ps -> reverse $ map (\n -> (n, fromJust $ lab g n)) ps

奇怪的是在第 39 行，标有 -- !!!评论。这段代码编译通过了，但是运行时错误是不管怎样， PQ.singleton函数返回一个空的优先级队列。我意识到我不小心在 mempty 中添加了反引号，所以当我删除那些代码时，编译并按预期工作。

然而这让我觉得很奇怪。代码如何在 mempty 周围正确编译并带有反引号，哪个根本不是二元函数( mempty :: a )？

在对#haskell 的一些非常慷慨的帮助之后，我发现它与函数的 Monoid 实例有关:

instance Monoid b => Monoid (a -> b)

我现在对为什么这个错误成功地进行了类型检查有一个非常模糊的理解，但我仍然感到不知何故在道德上受到了委屈。有人能解释一下这是怎么发生的吗？

此外，我还想直接关注优先队列的 singleton我正在使用的功能:根据 the source ，它不会返回一个空队列。然而，在第 24 行，相同的优先级队列立即被评估为空。 (我通过跟踪调用验证了这一点。)

Answer 1

所以，一般来说，代码:

a `f` b

只是语法糖:

f a b

因此你的代码变成了:

mempty PQ.singleton [start]

因此类型检查器推断出该特定 mempty 的类型:

mempty :: (k -> a -> PQ.MinPQueue k a) -> [Node] -> PQ.MinPQueue b [Node]

您正确地找到了问题所在的正确实例。任何类型 a -> b是 Monoid ，前提是 b是。所以让我们把上面的类型括起来:

mempty :: (k -> a -> PQ.MinPQueue k a) -> ([Node] -> PQ.MinPQueue b [Node])

因此，该类型可以是 Monoid如果 [Node] -> PQ.MinPQueue b [Node]是 Monoid .按照同样的逻辑， [Node] -> PQ.MinPQueue b [Node]可以是 Monoid如果 PQ.MinPQueue b [Node]是一个。它是哪个。所以类型检查器对这段代码没问题。

想必我们麻烦的实例的实现是:

instance Monoid => Monoid (a -> b) where
  mempty = const mempty

所以总的来说，你得到一个空的优先级队列。所以说真的，我认为这归结为一个问题，即设计师完全包括这个实例是否明智。它的净效果是任何返回幺半群的函数都可以是幺半群，这应该允许您组合结果。这里比较有用的情况是mappend，它可以追加两个 a -> b通过应用它们并使用 mappend 来实现函数合并结果。例如:

extremes = (return . minimum) `mappend` (return . maximum)

而不是:

extremes xs = [minimum xs, maximum xs]

嗯，也许其他人可以提供一个明智的更简洁的例子。