GHC: Ticket Query
http://ghc.haskell.org/trac/ghc/query?status=closed&component=Compiler+(Type+checker)&milestone=7.6.1&group=resolution&order=priority
The Glasgow Haskell Compileren-USGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/query?status=closed&component=Compiler+(Type+checker)&milestone=7.6.1&group=resolution&order=priority
Trac 1.0.1
http://ghc.haskell.org/trac/ghc/ticket/7171
http://ghc.haskell.org/trac/ghc/ticket/7171#7171: erroneous overlapping instances reported with FunDepsTue, 21 Aug 2012 03:37:47 GMTjwlato<p>
When a superclass constraint has functional dependencies, in certain cases GHC-7.6 erroneously reports that duplicate instances are found.
</p>
<p>
file Foo.hs
</p>
<pre class="wiki">{-# 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
</pre><p>
file Main.hs
</p>
<pre class="wiki">module Main where
import Foo
import Data.ByteString
-- this works
-- test1 :: [Int] -> [Int]
-- test1 = test
-- this fails
test2 :: ByteString -> ByteString
test2 = test
</pre><p>
ghc reports
</p>
<pre class="wiki">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
</pre><p>
For this to manifest, I think that at least the following must be true:
</p>
<ul><li>a function with class constraints must be called from a separate module
</li><li>the type class instance must be monomorphic in the fundep-to parameter
</li></ul><p>
This example works in ghc-7.4.2.
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/7171#changelog
http://ghc.haskell.org/trac/ghc/ticket/3108
http://ghc.haskell.org/trac/ghc/ticket/3108#3108: Do a better job of solving recursive type-class constraints with functional dependenciesWed, 18 Mar 2009 08:54:04 GMTsimonpj<p>
This ticket is just to track this interesting thread on the Haskell list, concerning recursive type-class constraints:
<a class="ext-link" href="http://www.haskell.org/pipermail/haskell/2009-March/021115.html"><span class="icon"></span>http://www.haskell.org/pipermail/haskell/2009-March/021115.html</a>.
We might want to get back to this when the new constraint solver is in place.
</p>
<p>
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:
</p>
<p>
"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.
</p>
<p>
This can happen:
</p>
<pre class="wiki"> 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)
==>
...
</pre><p>
where all the constraint are different because fresh variables are
introduced.
</p>
<p>
What you want to happen is:
</p>
<pre class="wiki"> 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
{}
</pre><p>
It seems that you want improvement to happen at a higher priority than GHC
does now."
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/3108#changelog
http://ghc.haskell.org/trac/ghc/ticket/5769
http://ghc.haskell.org/trac/ghc/ticket/5769#5769: Incorrect error message when compiling with PolyKinds and a type familyFri, 13 Jan 2012 20:13:54 GMTgoldfire<p>
When trying to compile
</p>
<pre class="wiki">{-# LANGUAGE TypeFamilies,
PolyKinds,
ScopedTypeVariables
#-}
convert :: a -> b
convert = undefined
type family Foo a
bar :: forall b a. b -> (Foo a)
bar f = (convert f :: (Foo a))
</pre><p>
I get the following error message:
</p>
<pre class="wiki">Sandbox.hs:12:10:
Couldn't match type `Foo k a' with `Foo * b'
NB: `Foo' is a type function, and may not be injective
In the expression: (convert f :: Foo a)
In an equation for `bar': bar f = (convert f :: Foo a)
</pre><p>
However, this compiles just fine without <tt>PolyKinds</tt>.
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/5769#changelog
http://ghc.haskell.org/trac/ghc/ticket/5770
http://ghc.haskell.org/trac/ghc/ticket/5770#5770: Non-sensical error message when compiling with PolyKinds and a type familyFri, 13 Jan 2012 20:33:00 GMTgoldfire<p>
When I compile the following code:
</p>
<pre class="wiki">{-# LANGUAGE TypeFamilies,
PolyKinds,
ScopedTypeVariables
#-}
convert :: a -> b
convert = undefined
type family Foo a
type instance Foo Int = Bool
bar :: forall a b c dummya. (b -> c) -> ((Foo a) -> c)
bar f = (convert f :: (Foo a) -> c)
</pre><p>
I get the following error message:
</p>
<pre class="wiki">Sandbox.hs:13:34:
Kind mis-match
Expected kind `OpenKind', but `c' has kind `b'
In an expression type signature: (Foo a) -> c
In the expression: (convert f :: (Foo a) -> c)
In an equation for `bar': bar f = (convert f :: (Foo a) -> c)
</pre><p>
This error message does not make sense, for 'b' isn't a kind. It is interesting to note that removing <tt>dummya</tt> from the list of declared type variables changes the error to a GHC panic.
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/5770#changelog
http://ghc.haskell.org/trac/ghc/ticket/5676
http://ghc.haskell.org/trac/ghc/ticket/5676#5676: Typeclass instance function type declarationsSat, 03 Dec 2011 23:24:57 GMTdrb226<p>
See discussion at <a class="ext-link" href="http://stackoverflow.com/questions/8367426/why-cant-one-put-type-signatures-in-instance-declarations-in-haskell"><span class="icon"></span>http://stackoverflow.com/questions/8367426/why-cant-one-put-type-signatures-in-instance-declarations-in-haskell</a>
</p>
<p>
Basically, it would be nice to be able to do something like this:
</p>
<pre class="wiki">instance Functor Maybe where
fmap :: (a -> b) -> Maybe a -> Maybe b
fmap = undefined
</pre><p>
This currently produces a "misplaced type signature" error.
</p>
<p>
It seems like a simple enough extension (we could call it SuperfluousTypeclassSignatures, because "Superfluous" is a cool word). It might be a good idea for Haskell Prime, but let's test it out as a Glasgow extension first.
</p>
<p>
We (a few of us on #haskell irc right now) think it best that only the precisely correct type signatures be accepted (reject signatures that are too lose or too strong), and it would be nice if, given an incorrect type signature, a custom error message were displayed stating the correct type signature.
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/5676#changelog
http://ghc.haskell.org/trac/ghc/ticket/5837
http://ghc.haskell.org/trac/ghc/ticket/5837#5837: Context reduction stack overflow can take very longWed, 01 Feb 2012 08:13:13 GMTdreixel<p>
The following code, taken from the "Haskell Type Constraints Unleashed" paper:
</p>
<pre class="wiki">{-# LANGUAGE TypeFamilies #-}
type family TF a :: *
type instance TF (a,b) = (TF a, TF b)
t :: (a ~ TF (a,Int)) => Int
t = undefined
</pre><p>
fails almost immediately with <tt>Context reduction stack overflow</tt> on GHC 7.2, but seems to loop forever with 7.4.1-rc2. Setting <tt>-fcontext-stack</tt> to <tt>20</tt> results in near immediate termination with the same error. But <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/5395" title="bug: Context reduction stack overflow without undecidable instances (closed: fixed)">#5395</a> raised the context stack size default to <tt>200</tt>, which makes this code (that does not use <tt>-XUndecidableInstances</tt>) take "forever" to compile.
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/5837#changelog
http://ghc.haskell.org/trac/ghc/ticket/5321
http://ghc.haskell.org/trac/ghc/ticket/5321#5321: Very slow constraint solving for type familiesWed, 13 Jul 2011 13:33:51 GMTsimonpj<p>
This post (to the ghc-users mailing list, from Gershom Bazerman) is in literate Haskell. It describes how certain performance leaks are introduced in type level programming. These leaks do not affect program runtimes, but can cause compile times to grow drastically. They exist both with Functional Dependencies and Type Families, but are currently worse with the former, and have grown worse with the new constraint solver in GHC 7. It is intended both as a guide to those encountering these issues, and as a motivation for the GHC development team to address such issues as the constraint solver is developed and improved.
</p>
<pre class="wiki">> {-# OPTIONS_GHC -fcontext-stack=1000 #-} {-# LANGUAGE
> FlexibleContexts, FlexibleInstances, FunctionalDependencies,
> MultiParamTypeClasses, OverlappingInstances, TypeSynonymInstances,
> TypeOperators, UndecidableInstances, TypeFamilies #-} module
> TypePerformance where
</pre><p>
Our running example, for simplicity's sake, is a type-level map of a single function. For reference, here is the code for a simple value-level map of a single function.
</p>
<pre class="wiki">> vfoo = id
> mapfoo (x : xs) = vfoo x : mapfoo xs
> mapfoo [] = []
</pre><p>
Because Haskell is a lazy language, this runs in O(n) time and constant stack.
</p>
<p>
We now lift map to the type level, to operate over HLists.
</p>
<p>
First, the basic HList types
</p>
<pre class="wiki">> infixr 3 :*
> data x :* xs = x :* xs deriving Show
> data HNil = HNil deriving Show
</pre><p>
Next, a large boring HList
</p>
<pre class="wiki">> -- Adds ten cells
> addData x = i :* i :* d :* d :* s :*
> i :* i :* d :* d :* s :*
> x
> where i = 1 :: Int
> d = 1 :: Double
> s = ""
>
> -- Has 70 cells.
> sampleData = addData $ addData $ addData $ addData $ addData $
> addData $ addData $
> HNil
</pre><p>
Next, a simple polymorphic function to map
</p>
<pre class="wiki">> class Foo x y | x -> y
> where foo :: x -> y
> foo = undefined
> instance Foo Int Double
> instance Foo Double Int
> instance Foo String String
</pre><p>
Now, our map
</p>
<pre class="wiki">> class HMapFoo1 as bs | as -> bs where
> hMapFoo1 :: as -> bs
>
> instance (Foo a b, HMapFoo1 as bs) => HMapFoo1 (a :* as) (b :* bs) where
> hMapFoo1 (x :* xs) = foo x :* hMapFoo1 xs
>
> instance HMapFoo1 HNil HNil where
> hMapFoo1 _ = HNil
</pre><p>
If we enable the following line, compilation time is ~ 9 seconds.
</p>
<pre class="wiki"> > testHMapFoo1 = hMapFoo1 sampleData
</pre><p>
Furthermore, playing with the size of sampleData, we see that the time spent in compilation is superlinear -- each additional cell costs a greater amount of time. This is because while Haskell is lazy at the value level, it is strict at the type level. Therefore, just as in a strict language, HMapFoo1's cost grows O(n<strong>2) because even as we induct over the as, we build up a stack of bs. Just as in a strict language, the solution is to make hMapFoo tail recursive through introducing an accumulator. This also reverses the hlist, but never mind that.
</strong></p>
<pre class="wiki">> class HMapFoo2 acc as bs | acc as -> bs where
> hMapFoo2 :: acc -> as -> bs
>
> instance (Foo a b, HMapFoo2 (b :* bs) as res) => HMapFoo2 bs (a :* as) res where
> hMapFoo2 acc (x :* xs) = hMapFoo2 (foo x :* acc) xs
>
> instance HMapFoo2 acc HNil acc where
> hMapFoo2 acc _ = acc
</pre><p>
If we enable the following line, compilation time is a much more satisfying ~0.5s.
</p>
<pre class="wiki"> > testHMapFoo2 = hMapFoo2 HNil sampleData
</pre><p>
But wait, there's trouble on the horizon! Consider the following version:
</p>
<pre class="wiki">> class HMapFoo3 acc as bs | acc as -> bs where
> hMapFoo3 :: acc -> as -> bs
>
> instance (HMapFoo3 (b :* bs) as res, Foo a b) => HMapFoo3 bs (a :* as) res where
> hMapFoo3 acc (x :* xs) = hMapFoo3 (foo x :* acc) xs
>
> instance HMapFoo3 acc HNil acc where
> hMapFoo3 acc _ = acc
</pre><p>
The only difference between hMapFoo2 and hMapFoo3 is that the order of constraints on the inductive case has been reversed, with the recursive constraint first and the immediately checkable constraint second. Now, if we enable the following line, compilation time rockets to ~6s!
</p>
<pre class="wiki"> > testHMapFoo3 = hMapFoo3 HNil sampleData
</pre><p>
Slowdowns such as those described here are not a purely hypothetical issue, but have caused real problems in production code. The example given above is fairly simple. The constraints used are minimal and easily checked. In real programs, the constraints are more difficult, increasing constant factors significantly. These constant factors, combined with unexpected algorithmic slowdowns due to the type inference engine, can lead (and have lead) to compilation times of HList-style code becoming deeply unwieldy-to-unusable, and can lead (and have lead) to this occuring only well after this code has been introduced and used on smaller cases without trouble.
</p>
<p>
The constraint solver should certainly be smart enough to reduce the compile times of HMapFoo3 to those of HMapFoo2. In fact, with type families, the there is no difference (see below). Could the compiler be smart enough to do the same for HMapFoo1? I'm not sure. Certainly, it could at least knock down its own constant factors a bit, even if it can't improve the big-O performance there.
</p>
<hr />
<h2 id="Appendix:ExampleswithTypeFamilies">Appendix: Examples with Type Families</h2>
<p>
As the below code demonstrates, the same issues demonstrated with Functional Dependencies also appear with Type Families, although less horribly, as their code-path seems more optimized in the current constraint solver:
</p>
<pre class="wiki">> class TFoo x where
> type TFooFun x
> tfoo :: x -> TFooFun x
> tfoo = undefined
>
> instance TFoo Int where
> type TFooFun Int = Double
> instance TFoo Double where
> type TFooFun Double = Int
> instance TFoo String where
> type TFooFun String = String
>
> class THMapFoo1 as where
> type THMapFoo1Res as
> thMapFoo1 :: as -> THMapFoo1Res as
>
> instance (TFoo a, THMapFoo1 as) => THMapFoo1 (a :* as) where
> type THMapFoo1Res (a :* as) = TFooFun a :* THMapFoo1Res as
> thMapFoo1 (x :* xs) = tfoo x :* thMapFoo1 xs
>
> instance THMapFoo1 HNil where
> type THMapFoo1Res HNil = HNil
> thMapFoo1 _ = HNil
</pre><p>
The following, when enabled, takes ~3.5s. This demonstrates that slowdown occurs with type families as well.
</p>
<pre class="wiki"> > testTHMapFoo1 = thMapFoo1 sampleData
> class THMapFoo2 acc as where
> type THMapFoo2Res acc as
> thMapFoo2 :: acc -> as -> THMapFoo2Res acc as
>
> instance (TFoo a, THMapFoo2 (TFooFun a :* acc) as) => THMapFoo2 acc (a :* as) where
> type THMapFoo2Res acc (a :* as) = THMapFoo2Res (TFooFun a :* acc) as
> thMapFoo2 acc (x :* xs) = thMapFoo2 (tfoo x :* acc) xs
>
> instance THMapFoo2 acc HNil where
> type THMapFoo2Res acc HNil = acc
> thMapFoo2 acc _ = acc
</pre><p>
The following, when enabled, takes ~0.6s. This demonstrates that the tail recursive transform fixes the slowdown with type families just as with fundeps.
</p>
<pre class="wiki"> > testTHMapFoo2 = thMapFoo2 HNil sampleData
> class THMapFoo3 acc as where
> type THMapFoo3Res acc as
> thMapFoo3 :: acc -> as -> THMapFoo3Res acc as
>
> instance (THMapFoo3 (TFooFun a :* acc) as, TFoo a) => THMapFoo3 acc (a :* as) where
> type THMapFoo3Res acc (a :* as) = THMapFoo3Res (TFooFun a :* acc) as
> thMapFoo3 acc (x :* xs) = thMapFoo3 (tfoo x :* acc) xs
>
> instance THMapFoo3 acc HNil where
> type THMapFoo3Res acc HNil = acc
> thMapFoo3 acc _ = acc
</pre><p>
The following, when enabled, also takes ~0.6s. This demonstrates that, unlike the fundep case, the order of type class constraints does not, in this instance, affect the performance of type families.
</p>
<pre class="wiki"> > testTHMapFoo3 = thMapFoo3 HNil sampleData
</pre>Resultshttp://ghc.haskell.org/trac/ghc/ticket/5321#changelog
http://ghc.haskell.org/trac/ghc/ticket/5978
http://ghc.haskell.org/trac/ghc/ticket/5978#5978: Type error in one function causes wrong type error report in another function in the presence of functionally dependent typesWed, 28 Mar 2012 22:56:36 GMTLemming<p>
When trying to reduce my problem in <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/5970" title="bug: Type checker hangs (closed: wontfix)">#5970</a> to a simple program I encountered an even more obvious bug. The problem is essentially as follows: I have
</p>
<pre class="wiki">correct :: T
correct = ...
wrong :: T
wrong = f correct
</pre><p>
where 'wrong' has a type error and 'correct' is type correct. If I outcomment 'wrong' then GHC correctly confirms type-correctness of 'correct', but if 'wrong' is enabled then GHC claims a type error in both 'wrong' and 'correct'.
To me it looks like the type-checker is trying to unify types across function boundaries. This would explain both non-linear growth of type-checking time and the observed effect of incorrect type errors.
See attached program for a working example.
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/5978#changelog
http://ghc.haskell.org/trac/ghc/ticket/2534
http://ghc.haskell.org/trac/ghc/ticket/2534#2534: Odd probable cause given by type checkerFri, 22 Aug 2008 03:54:40 GMTheatsink<p>
In the following code, a function has been applied to zero arguments, which the type checker suggests is too many.
</p>
<pre class="wiki">Prelude> foldr (>>=) [] []
<interactive>:1:6:
Occurs check: cannot construct the infinite type: b = a -> b
Probable cause: `>>=' is applied to too many arguments
In the first argument of `foldr', namely `(>>=)'
In the expression: foldr (>>=) [] []
</pre>Resultshttp://ghc.haskell.org/trac/ghc/ticket/2534#changelog
http://ghc.haskell.org/trac/ghc/ticket/6013
http://ghc.haskell.org/trac/ghc/ticket/6013#6013: the 'impossible' happenedTue, 17 Apr 2012 16:38:58 GMTtlvb<p>
Please forgive me if this is a duplicate or irrelevant, bug reporting and Haskell are two things I work with seldom enough that I cannot be considered good at either, but as what happened should be 'impossible' I thought I'd at least give you a heads up. I tried looking for similar bugs, but I do not really know what I would be looking for...
</p>
<p>
GHCi (newly opened, -v flag):
</p>
<pre class="wiki">[leo@derse brutelift]$ ghci -v
GHCi, version 7.4.1: http://www.haskell.org/ghc/ :? for help
Glasgow Haskell Compiler, Version 7.4.1, stage 2 booted by GHC version 7.4.1
Using binary package database: /usr/lib/ghc-7.4.1/package.conf.d/package.cache
wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-c2ff696e5b8ec4d4b2bc2e42085fe471
wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-3cccac07aef8e27023f605c1f45bdf74
wired-in package base mapped to base-4.5.0.0-40b99d05fae6a4eea95ea69e6e0c9702
wired-in package rts mapped to builtin_rts
wired-in package template-haskell mapped to template-haskell-2.7.0.0-8c8cd20e21666657195efabced685fe1
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: -static
Loading package ghc-prim ... linking ... done.
*** gcc:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-L/usr/lib/ghc-7.4.1/integer-gmp-0.4.0.0' '--print-file-name' 'libgmp.so'
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :load brutelift
*** Chasing dependencies:
Chasing modules from:
Stable obj: []
Stable BCO: []
unload: retaining objs []
unload: retaining bcos []
Ready for upsweep []
Upsweep completely successful.
*** Deleting temp files:
Deleting:
*** Chasing dependencies:
Chasing modules from: *brutelift.hs
Stable obj: []
Stable BCO: []
unload: retaining objs []
unload: retaining bcos []
Ready for upsweep
[NONREC
ModSummary {
ms_hs_date = Tue Apr 17 18:10:32 CEST 2012
ms_mod = main:Main,
ms_textual_imps = [import (implicit) Prelude, import Data.List]
ms_srcimps = []
}]
*** Deleting temp files:
Deleting:
compile: input file brutelift.hs
Created temporary directory: /tmp/ghc5399_0
*** Checking old interface for main:Main:
[1 of 1] Compiling Main ( brutelift.hs, interpreted )
*** Parser:
*** Renamer/typechecker:
ghc: panic! (the 'impossible' happened)
(GHC version 7.4.1 for x86_64-unknown-linux):
nameModule show{tv abQ}
Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug
>
</pre><p>
brutelift.hs:
</p>
<pre class="wiki">import Data.List
data Transfer = Load | Unload
data Action = Left Transfer Int | Right Transfer Int
data BlockDispersion = Blocks {top :: [Int]
, bottom :: [Int]
, left :: [Int]
, right :: [Int]}
deriving (Show)
data Machine = MOK BlockDispersion [Action] | MError BlockDispersion [Action] deriving (show)
rSplitAt i xs = let (a, b) = splitAt i $ reverse xs in
(reverse b, reverse a)
moveR :: Int -> ([a], [a]) -> ([a], [a])
moveR i (a, b) = let (c, d) = rSplitAt i a
in (c, d++b)
moveL :: Int -> ([a], [a]) -> ([a], [a])
moveL i (a, b) = let (c, d) = splitAt i b
in (a++c, d)
</pre><p>
I am not sure what additional info to provide...
Running an Arch linux system, 8GB ram, installed ghc packgage should be as vanilla as can be...
</p>
<pre class="wiki">[leo@derse brutelift]$ uname -a
Linux derse 3.3.1-1-ARCH #1 SMP PREEMPT Tue Apr 3 06:46:17 UTC 2012 x86_64 Intel(R) Core(TM) i5-2500K CPU @ 3.30GHz GenuineIntel GNU/Linux
</pre>Resultshttp://ghc.haskell.org/trac/ghc/ticket/6013#changelog