Haskell sub-typeclass requires UndecidableInstances?

Question

Consider the following code example:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-} -- Is there a way to avoid this?

-- A generic class with a generic function.
class Foo a where
  foo :: a -> a

-- A specific class with specific functions.
class Bar a where
  bar :: a -> a
  baz :: a -> a

-- Given the specific class functions, we can implement the generic class function.
instance Bar a => Foo a where
  foo = bar . baz

-- So if a type belongs to the specific class...
instance Bar String where
  bar = id
  baz = id

-- We can invoke the generic function on it.
main :: IO ()
main =
  putStrLn (foo "bar")

(My actual code is way more elaborate; this is a minimal boiled-down case to demonstrate the pattern.)

It isn't clear to me why UndecidableInstances are needed here - the type parameter a appears once in both sides of the Bar a => Foo a, so I expected things to "just work". I'm obviously missing something here. But at any rate, is there a way to do this without using UndecidableInstances?

Answer 1

There are a few approaches you can take; I don't think you've provided enough context to determine which would be the most appropriate. If you're using GHC-7.4, you might want to try the DefaultSignatures extension.

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE DefaultSignatures #-}

-- A generic class with a generic function.
class Foo a where
  foo :: a -> a
  default foo :: Bar a => a -> a
  foo = bar . baz

-- A specific class with specific functions.
class Bar a where
  bar :: a -> a
  baz :: a -> a

instance Bar String where
  bar = id
  baz = id

instance Foo String

main :: IO ()
main =
  putStrLn (foo "bar")

You still need to declare that a type is an instance of Foo, but you don't need to repeat the method declaration because the default implementation will be used.

Another fairly lightweight approach is to use a newtype. If you have functions that need a Foo instance, you can wrap a Bar instance in the newtype.

newtype FooBar a = FooBar { unFooBar :: a }

instance Bar a => Foo (FooBar a) where
    foo = FooBar . bar . baz . unFooBar

-- imported from a library or something...
needsFoo :: Foo a => a -> b

myFunc = needsFoo (FooBar someBar)

Alternatively, you may be able to get by with replacing foo with a normal function, or making a specialized version for Bar instances:

-- if every `Foo` is also a `Bar`, you can just do this.  No need for `Foo` at all!
foo :: Bar a => a -> a
foo = bar . baz

-- if most `Foo`s aren't `Bar`s, you may be able to use this function when you have a `Bar`
fooBar :: Bar a => a -> a
foo = bar . baz

These are probably the best solutions if they work for your situation.

Another option is to declare every Foo instance manually. Although there may be a lot of different conceivable instances, it's fairly common for codebases to only have a handful of instances that are actually used. If that's true here, it's probably less work to just write out the 3 or 4 instances you need rather than try to implement a more general solution.

As a very last resort, you can use something like your original code, but you'll also need OverlappingInstances to make it work (if you don't need OverlappingInstances, then you don't need a Foo class). This is the extension that allows GHC to choose the "most specific instance" when there are multiple available matches. This will more or less work, although you may not get what you expect.

class Foo a where
  foo :: a -> a

class Bar a where
  bar :: a -> a
  baz :: a -> a

instance Bar String where
  bar = id
  baz = id

instance Bar a => Foo a where
  foo = bar . baz

instance Foo [a] where
  foo _ = []

main :: IO ()
main =
  print (foo "foo")

Now main prints an empty string. There are two Foo instances, for a and [a]. The latter is more specific, so it gets chosen for foo "foo" since a string has type [Char], although you probably wanted the former. So now you'd also need to write

instance Foo String where
  foo = bar . baz

at which point you may as well leave out the Bar a => Foo a instance entirely.