여기에 이상한 행동을

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에 매우 관대 한 도움이 후, 나는 그것이 기능을위한 모노 이드 인스턴스 함께 할 수있는 뭔가 남겼 :

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

내가 지금이 오류가 성공적으로 타입 체크하는 이유에 매우 막연한 이해를하지만, 나는 아직도 어떻게 든 도덕적으로 잘못 생각합니다. 누군가 어떻게 이런 일이 일어 났는지 정확하게 설명 할 수 있습니까?

또한 우선 순위 큐의 singleton 함수에주의를 기울이고 싶습니다. the source에 따르면 빈 큐를 반환하지 않습니다. 그러나 24 행에서 동일한 우선 순위 큐는 즉시 비어있는 것으로 평가됩니다. (I 추적 호출을이을 확인했습니다.)

Answer 1

그래서, 일반적으로, 코드 : 코드가되었다 따라서

f a b 

:

mempty PQ.singleton [start] 

a `f` b 

가 단지 문법 설탕입니다

그래서 유형 검사기가 특정 메모 유형을 유추했습니다 :

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

문제의 올바른 인스턴스를 올바르게 찾을 수 있습니다. a -> b 유형은 Monoid이며 b 인 경우 제공됩니다. 위의 입력 그래서하자 브래킷 : [Node] -> PQ.MinPQueue b [Node]가 Monoid 경우

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

그래서, 그 유형은 Monoid 될 수 있습니다. 그리고 동일한 논리에 의해 은 이 1이면 Monoid이 될 수 있습니다. 그것은 어느 것입니다. 따라서이 코드에서는 형식 검사기로 문제가 없습니다.

는 아마도 우리의 골칫거리 인스턴스의 구현은 다음과 같습니다

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

그래서 전반적으로, 당신은 빈 우선 순위 큐를 얻을. 그래서 저는 디자이너가이 인스턴스를 전혀 포함하지 않는 것이 현명한 것인지에 대한 문제로 생각합니다. 그 효과는 monoid를 반환하는 모든 함수가 monoid가 될 수 있기 때문에 결과를 결합 할 수 있어야합니다. 보다 유용한 경우는 mappend이며 두 가지를 모두 적용하고 mappend을 사용하여 결과를 결합하여 두 개의 a -> b 함수를 추가 할 수 있습니다.

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

보다는 : 예를 들어

는

extremes xs = [minimum xs, maximum xs] 

흠, 어쩌면 다른 사람이 현명한 terser 예를 생성 할 수 있습니다.

Answer 2

그래서 역 따옴표은 ​​x :: a와 y :: b 형 a -> b -> c이어야

op x y 

하도록 op 요구

x `op` y 

동등하게 중위 연산자로 이진 함수를 설정.

귀하의 경우 op은 mempty이고 유형은 Monoid m => m입니다. 그러나 형식이 a -> b -> c 인 것으로 알고 있기 때문에이를 대체하면 더 이상 유효한 구문이 아닙니다 Monoid (a -> b -> c) => a -> b -> c입니다. 왜냐하면 제약 조건이 적용되는 한 아무 것도 입력하지 않기 때문에 m을 사용할 수 있기 때문입니다.

이제 우리는 t는 모노 이드 인 형태 s -> t, 어떤 기능을하는 모노 이드 자체이다 (때문에 인스턴스 선언에) 알고 있고, 우리는 또한 a -> b -> c이 정말 a -> (b -> c) 것을 알고 즉, 하나 개의 인수를 복용 함수와 다른 함수를 반환합니다. 따라서 및 (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)의 인스턴스 선언은 그것의 인수를 무시하고 b 모노 이드의 빈 요소를 반환하는 함수입니다 즉, mempty _ = mempty 정의합니다. 즉, 우리는 주장을 무시

mempty [start] 

즉 위의 호출을 확장 ( b -> c이다) 내부의 mempty 모노 이드를 사용할 수있다. 그럼 우리가 다시 인수를 무시하고, 반복 :

mempty 

그래서 당신이했던 표현은 유형 Monoid c => c을 가지고 하나의 mempty, 단지와 동일, 즉 그것은 어떤 모노 이드에게 무엇이든지 할 수 있습니다.

큰 경우 표현식이 c이 PQ.MinPQueue으로 추정됩니다. MinPQueue은 빈 큐인 mempty 인 Monoid 인스턴스입니다.

이렇게하면 결과가 어떻게 표시되는지 알 수 있습니다.

Answer 3

이미 몇 가지 좋은 해답을 얻었습니다. ghci에서이 문제를 해결할 때 조금 더 간단하고 도움이 되었기 때문에이 글을 게시 할 것이라고 생각했습니다.

mempty :: (a -> b) = mempty _ = mempty 따라서 본질적으로는 const mempty입니다.

λ> :t mempty :: (a -> b) 
<interactive>:1:1: 
    No instance for (Monoid b) arising from a use of `mempty' 

그래서 b, 우리는 해당 유형의 mempty를 요청하고 이후 Monoid이어야 의미가 있습니다.

λ> :t mempty :: (a -> [b]) 
mempty :: (a -> [b]) :: a -> [b] 
λ> :t mempty :: (a -> c -> [b]) 
mempty :: (a -> c -> [b]) :: a -> c -> [b] 

우리는 이들을 재귀 적으로 연결할 수 있습니다. (->)이 올바른 연관이기 때문에 은 b == (c -> d) 일 때 (a -> c -> d)을 나타낼 수 있습니다. 따라서 임의의 수의 인수를 제공 할 수 있고 함수에 대한 mempty은 모든 인수를 소비 할 때까지 재귀 적으로 적용됩니다.

λ> import Data.Map 
λ> (mempty :: (a -> c -> Map Int Int)) 4 5 
fromList [] 
λ> (mempty :: (a -> c -> d -> Map Int Int)) 4 5 6 
fromList [] 

그래서 우리는 기능 mempty를 적용하는 것이 주어진 것 인수를 버리고 유형이 표현에 위치에 예상되는 무엇에 대한 mempty를 반환합니다 것을 알 수있다.

당신이 발생하는 문제가 무엇