#10592: Allow cycles in class declarations -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.1 checker) | Keywords: Resolution: | Architecture: Operating System: Unknown/Multiple | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by MikeIzbicki): Thanks! That workaround solves my immediate problem :) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10592#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10592: Allow cycles in class declarations -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.1 checker) | Keywords: Resolution: | Architecture: Operating System: Unknown/Multiple | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by simonpj): Hmm. I think it'd be easy to send GHC into an infinite loop using this; i.e. the current implementation is over-liberal. {{{ type instance FieldScalar x = Field x }}} Is it true that you expect `Scalar (Scalar a) ~ Scalar a)` (cf #10318). If so, you could make it better behaved by saying {{{ class (Scalar (Scalar a) ~ Scalar a, Field (Scalar a)) => Vector a class Vector x => Field x }}} This still isn't accepted but could be under comment:6 of #10318 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10592#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10592: Allow cycles in class declarations -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.1 checker) | Keywords: Resolution: | Architecture: Operating System: Unknown/Multiple | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by simonpj): The stuff in #10318 is speculation about a possible feature. But the question remains: in your application If {{{ class (Scalar (Scalar a) ~ Scalar a, Field (Scalar a)) => Vector a class Vector x => Field x }}} was accepted by GHC, would it serve your purpose? That means that in any instance of `Vector t`, GHC will need to prove that `Scalar (Scalar t) ~ Scalar t`. Will that be true, in your application? If so, that makes the speculation in #10318 more persuasive. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10592#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10592: Allow cycles in class declarations -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.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): -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones ): In [changeset:"6eabb6ddb7c53784792ee26b1e0657bde7eee7fb/ghc" 6eabb6d/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="6eabb6ddb7c53784792ee26b1e0657bde7eee7fb" Allow recursive (undecidable) superclasses This patch fulfils the request in Trac #11067, #10318, and #10592, by lifting the conservative restrictions on superclass constraints. These restrictions are there (and have been since Haskell was born) to ensure that the transitive superclasses of a class constraint is a finite set. However (a) this restriction is conservative, and can be annoying when there really is no recursion, and (b) sometimes genuinely recursive superclasses are useful (see the tickets). Dimitrios and I worked out that there is actually a relatively simple way to do the job. It’s described in some detail in Note [The superclass story] in TcCanonical Note [Expanding superclasses] in TcType In brief, the idea is to expand superclasses only finitely, but to iterate (using a loop that already existed) if there are more superclasses to explore. Other small things - I improved grouping of error messages a bit in TcErrors - I re-centred the haddock.compiler test, which was at 9.8% above the norm, and which this patch pushed slightly over }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10592#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10592: Allow cycles in class declarations -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.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): Wiki Page: | -------------------------------------+------------------------------------- Description changed by bgamari: Old description:

In particular, I would like to have a class hierarchy that looks like:

{{{ {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE FlexibleContexts #-}

type family Scalar x

class Field (Scalar x) => Vector x

class Vector x => Field x }}}

It is the case that every field is a vector, and the scalar associated with every vector is a field. But we can't currently enforce that.

New description: In particular, I would like to have a class hierarchy that looks like: {{{#!hs {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE FlexibleContexts #-} type family Scalar x class Field (Scalar x) => Vector x class Vector x => Field x }}} It is the case that every field is a vector, and the scalar associated with every vector is a field. But we can't currently enforce that. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10592#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10592: Allow cycles in class declarations -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: infoneeded Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.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): Wiki Page: | -------------------------------------+------------------------------------- Comment (by MikeIzbicki): Awesome! I have two comments: 1. One of my use cases is very similar to the code attached below, which causes GHC to loop. The code provides an alternate class hierarchy for comparisons. One of the features of the hierarchy is that `(||)` and `(&&)` can be used directly on functions. Unfortunately, the instances for `(->)` cause GHC to loop. The instances seem like they should work to me. I'm not sure if my reasoning is faulty or if there's a bug in the implementation. 2. I believe there is an incorrect error message. If you take the code below and comment out the line `instance Boolean b => Boolean (a -> b)`, then GHC gives the error message: {{{ [1 of 1] Compiling ClassCycles ( ClassCycles.hs, ClassCycles.o ) ClassCycles.hs:1:1: error: solveWanteds: too many iterations (limit = 4) Set limit with -fsolver-iterations=n; n=0 for no limit WC {wc_simple = [W] $dBoolean_a1KZ :: Boolean (a -> fsk_a1KH) (CDictCan) [D] _ :: Boolean (a -> fsk_a1Ll) (CDictCan)} }}} But when I try to set the limit to something different, GHC complains that the flag doesn't exist: {{{ $ ~/proj/ghc/inplace/bin/ghc-stage2 ClassCycles.hs -fsolver-iterations=10 ghc-stage2: unrecognised flag: -fsolver-iterations=10 Usage: For basic information, try the `--help' option }}} ---- {{{ {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE UndecidableSuperClasses #-} module ClassCycles where import Prelude (Bool(True,False),Integer,Ordering) import qualified Prelude -------------------- -- class hierarchy class Boolean (Logic a) => Eq a where type Logic a :: * (==) :: a -> a -> Logic a class Eq a => POrd a where inf :: a -> a -> a class POrd a => MinBound a where minBound :: a class POrd a => Lattice a where sup :: a -> a -> a class (Lattice a, MinBound a) => Bounded a where maxBound :: a class Bounded a => Complemented a where not :: a -> a class Bounded a => Heyting a where infixr 3 ==> (==>) :: a -> a -> a class (Complemented a, Heyting a) => Boolean a (||) :: Boolean a => a -> a -> a (||) = sup (&&) :: Boolean a => a -> a -> a (&&) = inf -------------------- -- Bool instances -- (these work fine) instance Eq Bool where type Logic Bool = Bool (==) = (Prelude.==) instance POrd Bool where inf True True = True inf _ _ = False instance MinBound Bool where minBound = False instance Lattice Bool where sup False False = False sup _ _ = True instance Bounded Bool where maxBound = True instance Complemented Bool where not True = False not False = True instance Heyting Bool where False ==> _ = True True ==> a = a instance Boolean Bool -------------------- -- Integer instances -- (these work fine) instance Eq Integer where type Logic Integer = Bool (==) = (Prelude.==) instance POrd Integer where inf = Prelude.min instance Lattice Integer where sup = Prelude.max -------------------- -- function instances -- (these cause GHC to loop) instance Eq b => Eq (a -> b) where type Logic (a -> b) = a -> Logic b f==g = \a -> f a == g a instance POrd b => POrd (a -> b) where inf f g = \a -> inf (f a) (g a) instance MinBound b => MinBound (a -> b) where minBound = \_ -> minBound instance Lattice b => Lattice (a -> b) where sup f g = \a -> sup (f a) (g a) instance Bounded b => Bounded (a -> b) where maxBound = \_ -> maxBound instance Complemented b => Complemented (a -> b) where not f = \a -> not (f a) instance Heyting b => Heyting (a -> b) where f ==> g = \a -> f a ==> g a instance Boolean b => Boolean (a -> b) }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10592#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10592: Allow cycles in class declarations -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: infoneeded Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.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): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): OK I've got it. Patch coming. Your example differs from Edward's in #10318, because you really do have an infinite stack of superclasses. * `Eq a` has `Boolean (Logic a)` as a superclass * `Boolean a` ultimately has `Eq a` as a superclass So we get `Eq (Logic a)`, `Eq (Logic (Logic a))`, etc forever. Do you really mean that. Edward cut this off by adding a constraint {{{ Frac (Frac a) ~ Frac a }}} Can you do something like that for `Logic`? If you really really do have infinitely many superclasses then unsolved constraints will indeed hit the iteration limit as you found... GHC keeps adding superclasses in the hope of finding one that works, but there are infinitely many of them (I fixed the error message to give the right flag name, but it doesn't solve the problem). I don't see any way to solve this without you giving GHC some way to bound the tower as Edward did. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10592#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10592: Allow cycles in class declarations -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: infoneeded Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.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): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): MikeIzbicki: OK can you try again now? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10592#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10592: Allow cycles in class declarations -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: infoneeded Priority: normal | Milestone: Component: Compiler (Type | Version: 7.10.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): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Well, you only want to add that constraint if it's actually true -- that is, if you intend that `Logic` is idempotent. But hurrah anyway. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10592#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler