Geek Answers Handbook

The random return of a non-binary function creates fancy behavior

Here's the abusive code ( 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 shortest paths
-- algorithm. Deemed internal because it needs to be kickstarted with
-- a singleton node queue. Based on FGL 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 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

Strangeness is indicated on line 39, marked by a comment -- !!!. This code compiles, but the runtime error is that no matter what, the function PQ.singletonreturns an empty priority queue. I realized that I accidentally added backticks to mempty, so when I deleted the code, it compiled and worked as expected.

This, however, seemed strange to me. How did the code compile correctly with back windows around mempty, which is not a binary function ( mempty :: a) at all?

After some very generous help in #haskell, I found that it had something to do with the Monoid instance for functions:

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

, , - . - , ?

, singleton, : , . 24 . ( .)

+4
3

, , :

a `f` b

- :

f a b

:

mempty PQ.singleton [start]

, -checker 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] - . . , -checker .

, :

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]

, , - .

+10

, ,

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 , , , a -> b -> c a -> (b -> c), .. , . , a s (b -> c) t, Monoid, t . , t - (b -> c), Monoid ( s = b t = c), , c , .

, c? , ,

PQ.singleton `mempty` [start]

.

mempty PQ.singleton [start]

Monoid (a -> b) mempty _ = mempty, , b Monoid. ,

mempty [start]

. mempty ( b -> c). , :

mempty

, mempty, Monoid c => c, Monoid .

c PQ.MinPQueue. MinPQueue Monoid mempty, .

, .

+5

, , , , 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 Monoid, mempty , .

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

We can bind them recursively. Since it (->)is a right associative (a -> b), it can represent (a -> c -> d)when b == (c -> d). Thus, we can provide an arbitrary number of arguments, and functions memptyfor functions will be recursively applied until all arguments are used.

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

So, we see that the application of the function memptydiscards any arguments it sets and returns memptyfor any type expected at the position in which the expression is located.

+1
source

More articles:


All Articles