On Wed, Apr 16, 2008 at 2:33 PM, Bertram Felgenhauer wrote:

No. Data.Graph.Inductive.Query.Dominators is just buggy. [...] Here's a quick fix:

Thanks! This fixes my problem. Have you submitted a bug and your patch to the appropriate tracker? If not, would someone point me to the appropriate one? Would in be the GHC trac, or is there a libraries-specific one? I'll be happy to submit your patch and credit you for it, if someone will point me in the right direction. -- Denis

Your reasoning differs from the usual understanding of a null product (1 or True), as compared to a null sum (0 or False):

the list of nodes for which *any path* from source to x must touch, i.e., the list of dominators of x.

Here, "any path" means all paths, a logical conjunction: and [True, True] = True and [True ] = True and [ ] = True The empty case of all sources touching is True, so 12 is a valid dominator for 20 if there is no path from 12 to 20. Dan Denis Bueno wrote:

On Thu, Apr 17, 2008 at 11:32 AM, Denis Bueno wrote:

...

On Wed, Apr 16, 2008 at 2:33 PM, Bertram Felgenhauer wrote:

...

No. Data.Graph.Inductive.Query.Dominators is just buggy.

I have one more problem. For the attached graph, the dominators of the -20 node are computed correctly (namely, [-20,-1,11,12]). But the list of dominators for 20 is present, when in fact 20 isn't reachable from 12. I think 20 should be absent from the return value of `dom graph 12'. (And hence a call to `lookup 20 (dom graph 12)' should return Nothing.) Instead it returns [-20,-1,-3,11,12,-14,17].

Is my reasoning correct? I'd try to fix the code, but, I don't understand how it works.

------------------------------------------------------------------------

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

I'm not sure I agree this is the common definition of dominators

Is one undefeated if one has never fought?

I should only ask for the dominators of nodes which I know are reachable from the source node, right?

Yes. Denis Bueno wrote:

On Thu, Apr 17, 2008 at 5:52 PM, Dan Weston wrote:

...

Your reasoning differs from the usual understanding of a null product (1 or True), as compared to a null sum (0 or False):

...

the list of nodes for which *any path* from source to x must touch, i.e., the list of dominators of x.

Here, "any path" means all paths, a logical conjunction:

I'm not sure I agree this is the common definition of dominators, but supposing it is: the upshot is that to get what I expect, I should only ask for the dominators of nodes which I know are reachable from the source node, right?

Dan Weston wrote:

Here, "any path" means all paths, a logical conjunction:

and [True, True] = True and [True ] = True and [ ] = True

Kim-Ee Yeoh wrote:

Hate to nitpick, but what appears to be some kind of a limit in the opposite direction is a curious way of arguing that: and [] = True.

Surely one can also write

and [False, False] = False and [False ] = False and [ ] = False ???

No. I think what Dan meant was that for all non-null xs :: [Bool], it is clearly true that: and (True:xs) == and xs -- (1) It therefore makes sense to define (1) to hold also for empty lists, and since it is also true that: and (True:[]) == True We obtain: and [] == True Since we can't make any similar claim about the conjuctions of lists beginning with False, there is no reasonable argument to the contrary.

Matthew Brecknell wrote:

Dan Weston wrote:

...

Here, "any path" means all paths, a logical conjunction:

and [True, True] = True and [True ] = True and [ ] = True

Kim-Ee Yeoh wrote:

...

Hate to nitpick, but what appears to be some kind of a limit in the opposite direction is a curious way of arguing that: and [] = True.

Surely one can also write

and [False, False] = False and [False ] = False and [ ] = False ???

No. I think what Dan meant was that for all non-null xs :: [Bool], it is clearly true that:

and (True:xs) == and xs -- (1)

It therefore makes sense to define (1) to hold also for empty lists, and since it is also true that:

and (True:[]) == True

We obtain:

and [] == True

Since we can't make any similar claim about the conjuctions of lists beginning with False, there is no reasonable argument to the contrary.

Also, (and I know none of this is original, but it's worth repeating...) It is not just the definition of "and" at stake here. Logical propositions that extend painlessly to [] if (and [] == True) become inconsistent for [] if (and [] == False) and would have to be checked in program calculation. For instance, in propositional logic, you can prove (using Composition, Distribution[2], Material Implication) that for nonnull ys = [y0,y1,..,yn], implying everthing implies each thing: x -> (y0 && y1 && ... yn) <--> (x -> y0) && (x -> y1) && ... && (x -> yn) Writing this in Haskell and using the fact that x -> y means (not x || y), this says that not x || and ys == and (map (not x ||) ys) or in pointfree notation: f . and == and . map f where f = (not x ||) This should look familiar to origamists everywhere. "and" can be defined in terms of foldr iff (and [] == True) [Try it!]. Why is this important? If and is defined with foldr, then the above can be proven for all well-typed f, and for f = (not x ||) in particular, even if ys is null. The law is painlessly extended to cover the null case automatically (and is therefore consistent): LHS: not x || (and []) == not x || True == True RHS: and (map (not x ||) []) == and [] == True Therefore True |- True, an instance of x |- x If (and [] == False), then the law becomes inconsistent: LHS: not x || (and []) == not x || False == not x RHS: and (map (not x ||) []) == and [] == False Since not x == False, then x == True Therefore, True |- x ==> -| x (everything is derivable) so we would have to exclude the null case for this law (and many others). Uck! Better stick with (and [] == True) Naturally, similar reasoning justifies (or [] == False).

Denis Bueno wrote:

On Wed, Apr 16, 2008 at 2:33 PM, Bertram Felgenhauer wrote:

...

No. Data.Graph.Inductive.Query.Dominators is just buggy. [...] Here's a quick fix:

Thanks! This fixes my problem.

Have you submitted a bug and your patch to the appropriate tracker? If not, would someone point me to the appropriate one? Would in be the GHC trac, or is there a libraries-specific one?

The library is shipped with ghc, and the darcs repository lists libraries@haskell.org as the maintainer, so GHC's trac seems to be the right place. I've created a ticket for this now, See http://hackage.haskell.org/trac/ghc/ticket/2227 Note that I opted for reimplementing the whole module instead of just fixing the bug. regards, Bertram