[GHC] #13073: BooleanFormula implies is wrong

[GHC]

#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