Haskell "not" type constraint

Question

I'm trying to define a pair of class instances inductively. That is:

class Foo a b | a -> b where
  foo :: a -> b

instance (not?)Foo a => Bar a b
  foo x = ...

instance Foo a => Bar a b
  foo x = ...

The first instances determines the base action, and the seconds recursively calls foo. Is there any way to do this? A good example would be flattening a list, where in the first case it's the identity function and in the second it's a recursive application of concat.

Answer 1

There's no way to do this directly, for a very simple reason--instance selection only looks at the "head", i.e., the part after the =>. Nothing you put in the context--the part before the =>--can influence which instance is selected.

For simple cases, you can often avoid the issue entirely, such as if there's a limited number of "base case" types. A common example there would be type-level lists, where you'd have a recursive case for Cons and a base case of Nil and that's it.

In the general case, you'll typically need some sort of "conditional test" type class that picks a type based on whether some condition is fulfilled, then hand off the actual implementation to a "helper" class which takes the conditional's result value as a parameter and uses that to select an instance.

Answer 2

Here is an implementation of a flatten function that works with any level of nested list. I wouldn't really recommend using it though - here just for demonstration of how to achieve something like this in haskell.