#13073: BooleanFormula implies is wrong -------------------------------------+------------------------------------- Reporter: ezyang | Owner: Type: bug | Status: patch Priority: normal | Milestone: 8.2.1 Component: Compiler (Type | Version: 8.1 checker) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D2925 Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * milestone: => 8.2.1 @@ -21,1 +21,2 @@ - But neither of the decomposed formulas are true. + But neither of the decomposed formulas are true, so GHC will never find a + proof. New description: The current implementation looks like this: {{{ implies :: Eq a => BooleanFormula a -> BooleanFormula a -> Bool x `implies` Var y = x `impliesAtom` y x `implies` And ys = all (implies x . unLoc) ys x `implies` Or ys = any (implies x . unLoc) ys x `implies` Parens y = x `implies` (unLoc y) }}} This cannot possibly be correct: this will decompose the formula A \/ B -> A \/ B in the following way {{{ Or [Var a, Var b] `implies` Or [Var a, Var b] Or [Var a, Var b] `implies` Var a || Or [Var a, Var b] `implies` Var b }}} But neither of the decomposed formulas are true, so GHC will never find a proof. I didn't find a case in the typechecker where this actually mattered. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13073#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler