Databases
StackOverflow2013
Postsdbo
POAccidentally backticking a non-binary function creates bizarre behaviour
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAccidentally backticking a non-binary function creates bizarre behaviour
    primarykey
    data
    text
    <p>Here's the offending code (<a href="http://lpaste.net/96826" rel="nofollow">also on lpaste.net</a>):</p> <pre><code>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) =&gt; gr a b -&gt; PQ.MinPQueue b [Node] -&gt; [[Node]] dijkstraInternal g q | PQ.null q = [] | otherwise = case match v g of (Just cxt,g') -&gt; p:dijkstraInternal g' (PQ.unions (q' : expand cxt minDist p)) (Nothing, g') -&gt; dijkstraInternal g' q' where ((minDist,p@(v:_)), q') = PQ.deleteFindMin q expand (_,_,_,s) dist pathToC = map (\(edgeCost,n) -&gt; 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) =&gt; gr a b -&gt; Node -&gt; [[Node]] dijkstra g start = dijkstraInternal g (PQ.singleton `mempty` [start]) -- !!! dijkstraPath :: (Graph gr, Ord b, Monoid b) =&gt; gr a b -&gt; Node -&gt; Node -&gt; [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 -&gt; [] Just ps -&gt; reverse $ map (\n -&gt; (n, fromJust $ lab g n)) ps </code></pre> <p>The weirdness is in line 39, marked with the <code>-- !!!</code> comment. This code compiles, but the runtime error is that no matter what, the <code>PQ.singleton</code> function returns an empty priority queue. I realized I had accidentally added backticks to <code>mempty</code>, so when I removed those the code compiled and worked as expected.</p> <p>This however struck me as strange. How could the code have correctly compiled with backticks around <code>mempty</code>, which is not a binary function at all (<code>mempty :: a</code>)?</p> <p>After some very generous help on #haskell, I found that it had something to do with the Monoid instance for functions:</p> <pre><code>instance Monoid b =&gt; Monoid (a -&gt; b) </code></pre> <p>I now have an extremely vague understanding of why this error successfully typechecked, but I still feel somehow morally wronged. Can someone explain exactly how this happened?</p> <p>Additionally, I'd also like to direct attention to the priority queue's <code>singleton</code> function that I'm using: according to <a href="http://hackage.haskell.org/package/pqueue-1.2.1/docs/src/Data-PQueue-Prio-Internals.html#singleton" rel="nofollow">the source</a>, it doesn’t return an empty queue. However, at line 24, that same priority queue immediately gets evaluated as being empty. (I verified this with trace calls.)</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USGreg Bacon
    1. USgiogadi
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAccidentally backticking a non-binary function creates bizarre behaviour
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POAccidentally backticking a non-binary function creates bizarre behaviour
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POAccidentally backticking a non-binary function creates bizarre behaviour
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhat's the problem you're having with the monoid instance? You said #haskell explained it, so what's still unclear?
      singulars
      1. POAccidentally backticking a non-binary function creates bizarre behaviour
      1. USbennofs
    2. COFrom their explanation I understand that this particular Monoid instance must be the root cause, but I still can't wrap my head around exactly how it works. Also, I believe that a public answer to this question would be really helpful to the Haskell community at large (and myself!) for understanding the Monoid instance of (->).
      singulars
      1. POAccidentally backticking a non-binary function creates bizarre behaviour
      1. USgiogadi
    3. CONot that you can apply that instance twice, meaning that `a -> b -> c` is an instance of `Monoid` if `c` is a `Monoid`, so it's a perfectly valid binary function.
      singulars
      1. POAccidentally backticking a non-binary function creates bizarre behaviour
      1. USGabriel Gonzalez
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload