意外地反向非二元函数会产生奇怪的行为

Question

这是有问题的代码(也在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我正在使用的优先级队列的功能:根据源,它不返回空队列.但是,在第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都是a 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]可以是一个Monoidif PQ.MinPQueue b [Node].它是什么.因此,使用此代码可以使用类型检查器.

据推测,我们麻烦的实例的实现是:

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

总的来说,你得到一个空的优先级队列.所以,我认为这归结为一个问题,即设计师是否明智地包含这个实例.它的净效果是返回一个monoid的任何函数都可以是一个monoid,它应该允许你组合结果.这里更有用的例子是mappend,它可以a -> b通过应用它们并使用mappend结合结果来附加两个函数.例如:

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

而不是:

extremes xs = [minimum xs, maximum xs]

嗯,也许别人可以产生一个明智的例子.

Answer 2

所以反引号将二进制函数转换为中缀运算符

x `op` y

相当于

op x y

所以op需要在a -> b -> c哪里x :: a和y :: b.

在你的情况下,op是mempty,与类型Monoid m => m.但是我们知道它是形式的a -> b -> c,所以替换它并且你得到(这不再是有效的语法)Monoid (a -> b -> c) => a -> b -> c,因为m只要约束成立,我们就可以替换它.

现在我们知道(由于实例声明),形式的任何函数s -> t,其中t是Monoid,都是Monoid本身,我们也知道它a -> b -> c是真的a -> (b -> c),即一个函数接受一个参数并返回另一个函数.因此,如果我们替代a的s和(b -> c)为t,我们将履行含半幺群例如,如果t是一个Monoid.当然,t是的(b -> c),所以我们可以再次应用相同的Monoid实例(使用s = b和t = c),所以如果c是Monoid,我们就是好的.

那是什么c？你的表达是

PQ.singleton `mempty` [start]

即

mempty PQ.singleton [start]

Monoid (a -> b)定义的实例声明mempty _ = mempty,即它是一个忽略其参数并返回bMonoid 的空元素的函数.换句话说,我们可以将上面的调用扩展为

mempty [start]

即我们忽略参数并使用内部Monoid的mempty(即b -> c).然后我们重复一遍,再次忽略这个论点:

mempty

所以你所拥有的表达式只相当于一个mempty具有类型的单个Monoid c => c,即它可以是任何Monoid.

在你的情况下,较大的表达式推断c为a PQ.MinPQueue.并且MinPQueue是一个Monoid实例,mempty是一个空队列.

这就是你最终得到你所看到的结果的方式.