6

I would like to write something like:

{-# LANGUAGE FlexibleContexts,FlexibleInstances #-}

import Data.ByteString.Char8 (ByteString,pack)
import Data.Foldable (Foldable)

class (Show a) => Rows a where
    rRepr :: a -> [ByteString]
    rRepr = (:[]) . pack . show

instance (Foldable f,Show (f a)) => Rows (f a) where
    rRepr = const []

meaning that f a instantiate Rows if f instantiate Foldable and f a instantiate Show. When I run ghc I get:

Constraint is no smaller than the instance head
  in the constraint: Show (f a)
(Use -XUndecidableInstances to permit this)
In the instance declaration for `Rows (f a)'

I have two questions:

  • what "smaller" means in the error and what is the problem?
  • what is the right way to define what I want without using UndecidableInstances?
mariop
  • 3,195
  • 1
  • 19
  • 29
  • 1
    possible duplicate of [Haskell Constraint is no smaller than the instance head](http://stackoverflow.com/questions/7198907/haskell-constraint-is-no-smaller-than-the-instance-head) – jberryman Jul 25 '13 at 16:16
  • In future, as a convenience to anyone who tries to answer a question, you might want to include the imports and tell us which line the error message pointed to. In this case, I added `import Data.ByteString.Lazy (ByteString, pack)` and `import Data.Foldable (Foldable)`. The error is on the `instance ...` line. – mhwombat Jul 25 '13 at 16:23
  • @jberryman I read that post but I couldn't understand how to adapt the answers to my case. @mhwombat added the imports. I didn't put the line number because the ghc error output is clear about that. The error is on the constraint `Show (f a)` of the instance declaration `Rows (f a)` – mariop Jul 25 '13 at 16:38
  • 1
    Isn't `Show (f a)` already implied by the class constraint? – Ingo Jul 25 '13 at 16:58
  • @Ingo no, the class constraint `Show a` says that to be a `Rows`, the type `a` must instantiate `Show`. It is not automatic. – mariop Jul 25 '13 at 17:09
  • @jberryman, seems like same error message but not same question... – HaskellElephant Jul 30 '13 at 11:08
  • @HaskellElephant I think all the answers to this question are in the answers and comments to the other question. But it doesn't hurt having more explanation of a tricky concept – jberryman Jul 30 '13 at 16:20

1 Answers1

12

Let's play compiler: we have a type (f a) we'd like to see if it is a valid satisfier of a Rows constraint. To do so, we need to dispatch a proof that (f a) satisfies Show (f a) as well. This isn't a problem unless someone writes an

 instance Rows (f a) => Show (f a) where ...

in which case I'm back where I began. Encoding an infinite loop like this is sort of foolish, but Haskell statically ensures that it's actually impossible unless you ask for UndecidableInstances.

Normally Haskell ensures that each step of a "resolution chase" reduces the size of the type by at least 1 constructor. This leads to a really simple proof by structural induction that we'll end up with a bare type in a finite number of resolutions.

This is overly restrictive, clearly some instance resolution steps are meaningful, useful, and total even if they don't immediately reduce the constructor tree. This same kind of totality restriction applies in languages like Agda and Coq and often it's a bit of an illustrative challenge to manipulate your algorithm into one which proceeds by structural induction.

So how can we fix it? One way is to lose the Show constraint on the class definition use an instance like Show1 from prelude-extras. 

class Show1 f where ...
show1 :: (Show1 f, Show a) => f a -> String  -- not an instance definition!

and then have instance (Foldable f, Show1 f, Show a) => Rows (f a) where ... which works in my testing. You can then write a default instance as a standalone function.

defRRepr :: Show a => a -> [ByteString]
defRRepr = (:[]) . pack . show

and use it whenever writing an instance definition for a Showable thing.

The other solution is to use newtype wrappers to allow Haskell to see that a "layer" of resolution has been removed.

instance (Foldable f, Show (f a)) => Rows (FoldableRow f a) where
    rRepr = const [] . unFR

newtype FoldableRow f a = FR { unFR :: f a } deriving (Show)
J. Abrahamson
  • 72,246
  • 9
  • 135
  • 180
  • Nice answer, made me introduce a newtype rather than going with `UndecidableInstances` (though that would have worked as well). The newtype communicates intent more explicitly. – ron Aug 05 '23 at 10:06