GHC issueshttps://gitlab.haskell.org/ghc/ghc/-/issues2019-07-07T19:05:21Zhttps://gitlab.haskell.org/ghc/ghc/-/issues/3108Do a better job of solving recursive type-class constraints with functional d...2019-07-07T19:05:21ZSimon Peyton JonesDo a better job of solving recursive type-class constraints with functional dependenciesThis ticket is just to track this interesting thread on the Haskell list, concerning recursive type-class constraints:
http://www.haskell.org/pipermail/haskell/2009-March/021115.html.
We might want to get back to this when the new constr...This ticket is just to track this interesting thread on the Haskell list, concerning recursive type-class constraints:
http://www.haskell.org/pipermail/haskell/2009-March/021115.html.
We might want to get back to this when the new constraint solver is in place.
The question concerns the interaction of solving recursive type-class constraints, where it is important to aggressively apply functional dependencies. Here's Tom Schrijvers's analysis of Ralf's example:
"The cyclic dictionaries approach is a bit fragile. The problem appears to
be here that GHC alternates exhaustive phases of constraint reduction and
functional dependency improvement. The problem is that in your example you
need both for detecting a cycle.
This can happen:
```
C1 Int
==> 3rd C1 inst
C2 Int y, C1 (y,Bool)
==> 1st C1 inst
C2 Int y, C1 y, C1 Bool
==> 2nd C1 inst
C2 Int y, C1 y
==> 3rd C1 inst
C2 Int y, C2 y z, C1 (z,Bool)
==>
...
```
where all the constraint are different because fresh variables are
introduced.
What you want to happen is:
```
C1 Int
==> 3rd C1 inst
C2 Int y, C1 (y,Bool)
==> 1st C1 inst
C2 Int y, C1 y, C1 Bool
==> 2nd C1 inst
C2 Int y, C1 y
==> C2 FD improvement {Int/y} <<<<
C2 Int Int, C1 Int
==> C1 Int cycle detected
C2 Int Int
==> C2 1st instance
{}
```
It seems that you want improvement to happen at a higher priority than GHC
does now."
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ----------------------- |
| Version | 6.10.1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | Compiler (Type checker) |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Do a better job of solving recursive type-class constraints with functional dependencies","status":"New","operating_system":"","component":"Compiler (Type checker)","related":[],"milestone":"6.12 branch","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"6.10.1","keywords":[],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"This ticket is just to track this interesting thread on the Haskell list, concerning recursive type-class constraints:\r\nhttp://www.haskell.org/pipermail/haskell/2009-March/021115.html.\r\nWe might want to get back to this when the new constraint solver is in place.\r\n\r\nThe question concerns the interaction of solving recursive type-class constraints, where it is important to aggressively apply functional dependencies. Here's Tom Schrijvers's analysis of Ralf's example:\r\n\r\n\"The cyclic dictionaries approach is a bit fragile. The problem appears to\r\nbe here that GHC alternates exhaustive phases of constraint reduction and\r\nfunctional dependency improvement. The problem is that in your example you\r\nneed both for detecting a cycle.\r\n\r\nThis can happen:\r\n{{{\r\n C1 Int\r\n ==> 3rd C1 inst\r\n C2 Int y, C1 (y,Bool)\r\n ==> 1st C1 inst\r\n C2 Int y, C1 y, C1 Bool\r\n ==> 2nd C1 inst\r\n C2 Int y, C1 y\r\n ==> 3rd C1 inst\r\n C2 Int y, C2 y z, C1 (z,Bool)\r\n ==>\r\n ...\r\n}}}\r\nwhere all the constraint are different because fresh variables are\r\nintroduced.\r\n\r\nWhat you want to happen is:\r\n{{{\r\n C1 Int\r\n ==> 3rd C1 inst\r\n C2 Int y, C1 (y,Bool)\r\n ==> 1st C1 inst\r\n C2 Int y, C1 y, C1 Bool\r\n ==> 2nd C1 inst\r\n C2 Int y, C1 y\r\n ==> C2 FD improvement {Int/y} <<<<\r\n C2 Int Int, C1 Int\r\n ==> C1 Int cycle detected\r\n C2 Int Int\r\n ==> C2 1st instance\r\n {}\r\n}}}\r\nIt seems that you want improvement to happen at a higher priority than GHC\r\ndoes now.\"\r\n","type_of_failure":"OtherFailure","blocking":[]} -->7.6.1https://gitlab.haskell.org/ghc/ghc/-/issues/7128Panic "lookupVarEnv_NF" when using a functional dependency with a kind variable2019-07-07T18:51:15ZRichard Eisenbergrae@richarde.devPanic "lookupVarEnv_NF" when using a functional dependency with a kind variableThe following code causes a panic:
```
{-# LANGUAGE PolyKinds, DataKinds, MultiParamTypeClasses,
FunctionalDependencies
#-}
class Foo a (b :: k) | a -> k
instance Foo Bool False
```
The error is
```
ghc-stage2: panic! (...The following code causes a panic:
```
{-# LANGUAGE PolyKinds, DataKinds, MultiParamTypeClasses,
FunctionalDependencies
#-}
class Foo a (b :: k) | a -> k
instance Foo Bool False
```
The error is
```
ghc-stage2: panic! (the 'impossible' happened)
(GHC version 7.7.20120807 for x86_64-apple-darwin):
lookupVarEnv_NF: Nothing
```
In previous versions of GHC 7.5.x, a functional dependency of this nature worked just fine and had the expected behavior of fixing the value of `k` once `a` was known. It's unclear to me whether this should compile or not, but it shouldn't cause a panic. I believe that my code that used the functional dependency could use `a -> b` in place of `a -> k` with no ill effect, so turning this into an error is not a problem.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ------------ |
| Version | 7.5 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | Compiler |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"Panic \"lookupVarEnv_NF\" when using a functional dependency with a kind variable","status":"New","operating_system":"","component":"Compiler","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.5","keywords":["FunctionalDependencies","PolyKinds"],"differentials":[],"test_case":"","architecture":"","cc":[""],"type":"Bug","description":"The following code causes a panic:\r\n\r\n{{{\r\n{-# LANGUAGE PolyKinds, DataKinds, MultiParamTypeClasses,\r\n FunctionalDependencies\r\n #-}\r\n\r\nclass Foo a (b :: k) | a -> k\r\ninstance Foo Bool False\r\n}}}\r\n\r\nThe error is \r\n\r\n{{{\r\nghc-stage2: panic! (the 'impossible' happened)\r\n (GHC version 7.7.20120807 for x86_64-apple-darwin):\r\n\tlookupVarEnv_NF: Nothing\r\n}}}\r\n\r\nIn previous versions of GHC 7.5.x, a functional dependency of this nature worked just fine and had the expected behavior of fixing the value of {{{k}}} once {{{a}}} was known. It's unclear to me whether this should compile or not, but it shouldn't cause a panic. I believe that my code that used the functional dependency could use {{{a -> b}}} in place of {{{a -> k}}} with no ill effect, so turning this into an error is not a problem.","type_of_failure":"OtherFailure","blocking":[]} -->7.6.1https://gitlab.haskell.org/ghc/ghc/-/issues/7171erroneous overlapping instances reported with FunDeps2019-07-07T18:51:01Zjwlatoerroneous overlapping instances reported with FunDepsWhen a superclass constraint has functional dependencies, in certain cases GHC-7.6 erroneously reports that duplicate instances are found.
file Foo.hs
```
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
modu...When a superclass constraint has functional dependencies, in certain cases GHC-7.6 erroneously reports that duplicate instances are found.
file Foo.hs
```
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}
module Foo where
import Data.ByteString as B
import Data.Word
class Foo a b | a -> b
class (Foo a b) => Bar a b | a -> b
instance Foo [a] a
instance Bar [a] a
instance Foo ByteString Word8
instance Bar ByteString Word8
test :: Bar full item => full -> full
test inp = inp
-- this works
-- _test_x :: ByteString -> ByteString
-- _test_x = test
```
file Main.hs
```
module Main where
import Foo
import Data.ByteString
-- this works
-- test1 :: [Int] -> [Int]
-- test1 = test
-- this fails
test2 :: ByteString -> ByteString
test2 = test
```
ghc reports
```
Main.hs:12:9:
Overlapping instances for Foo ByteString GHC.Word.Word8
arising from a use of `test'
Matching instances:
instance Foo ByteString GHC.Word.Word8 -- Defined at Foo.hs:20:10
There exists a (perhaps superclass) match:
(The choice depends on the instantiation of `'
To pick the first instance above, use -XIncoherentInstances
when compiling the other instance declarations)
In the expression: test
In an equation for `test2': test2 = test
```
For this to manifest, I think that at least the following must be true:
> - a function with class constraints must be called from a separate module
> - the type class instance must be monomorphic in the fundep-to parameter
This example works in ghc-7.4.2.
<details><summary>Trac metadata</summary>
| Trac field | Value |
| ---------------------- | ----------------------- |
| Version | 7.6.1-rc1 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | Compiler (Type checker) |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | jwlato@gmail.com |
| Operating system | |
| Architecture | |
</details>
<!-- {"blocked_by":[],"summary":"erroneous overlapping instances reported with FunDeps","status":"New","operating_system":"","component":"Compiler (Type checker)","related":[],"milestone":"","resolution":"Unresolved","owner":{"tag":"Unowned"},"version":"7.6.1-rc1","keywords":["classes,","fundeps","type"],"differentials":[],"test_case":"","architecture":"","cc":["jwlato@gmail.com"],"type":"Bug","description":"When a superclass constraint has functional dependencies, in certain cases GHC-7.6 erroneously reports that duplicate instances are found.\r\n\r\nfile Foo.hs\r\n{{{\r\n{-# LANGUAGE FunctionalDependencies #-}\r\n{-# LANGUAGE FlexibleInstances #-}\r\n\r\nmodule Foo where\r\n\r\nimport Data.ByteString as B\r\nimport Data.Word\r\n\r\nclass Foo a b | a -> b\r\n\r\nclass (Foo a b) => Bar a b | a -> b\r\n\r\ninstance Foo [a] a\r\ninstance Bar [a] a\r\ninstance Foo ByteString Word8\r\ninstance Bar ByteString Word8\r\n\r\ntest :: Bar full item => full -> full\r\ntest inp = inp\r\n\r\n-- this works\r\n-- _test_x :: ByteString -> ByteString\r\n-- _test_x = test\r\n\r\n\r\n}}}\r\n\r\nfile Main.hs\r\n{{{\r\nmodule Main where\r\n\r\nimport Foo\r\nimport Data.ByteString\r\n\r\n-- this works\r\n-- test1 :: [Int] -> [Int]\r\n-- test1 = test\r\n\r\n-- this fails\r\ntest2 :: ByteString -> ByteString\r\ntest2 = test\r\n\r\n}}}\r\n\r\nghc reports\r\n\r\n{{{\r\nMain.hs:12:9:\r\n Overlapping instances for Foo ByteString GHC.Word.Word8\r\n arising from a use of `test'\r\n Matching instances:\r\n instance Foo ByteString GHC.Word.Word8 -- Defined at Foo.hs:20:10\r\n There exists a (perhaps superclass) match:\r\n (The choice depends on the instantiation of `'\r\n To pick the first instance above, use -XIncoherentInstances\r\n when compiling the other instance declarations)\r\n In the expression: test\r\n In an equation for `test2': test2 = test\r\n}}}\r\n\r\nFor this to manifest, I think that at least the following must be true:\r\n - a function with class constraints must be called from a separate module\r\n - the type class instance must be monomorphic in the fundep-to parameter\r\n\r\nThis example works in ghc-7.4.2.","type_of_failure":"OtherFailure","blocking":[]} -->7.6.1