[Haskell-cafe] Problems with type family in a class

[Niklas Haas]

On Wed, 16 Jul 2014 22:32:27 -0400, Leza Morais Lutonda <leza.ml at fecrd.cujae.edu.cu> wrote:
> 
> Hi,
> 
> Consider the following type classes:
> 
> class (Signal sx) => Complexable sx where
> type ComplexSignalType
> ....
> 
> class (Complexable sx) => FourierTransformable sx where
> fft :: (cx ~ ComplexSignalType sx) => cx -> cx
> ....
> 
> and an instance:
> 
> instance (RealFloat e) => Complexable [e] where
> type ComplexSignalType = [Complex e]
> 
> instance (RealFloat e) => FourierTransformable [e] where
> fft = ...
> 
> Why this example will give errors:
> 
> *DSP.Signals.Core Prelude Data.Complex> :t ax
> ax :: [Complex Double]
> *DSP.Signals.Core Prelude Data.Complex> fft ax
> 
> <interactive>:90:1:
> No instance for (FourierTransformable s0 [Complex Double])
> arising from a use of ‘fft’
> The type variable ‘s0’ is ambiguous
> Note: there is a potential instance available:
> instance [overlap ok] (RealFloat e, Math.FFT.Base.FFTWReal e) =>
> FourierTransformable [e] [Complex e]
> -- Defined at src/DSP/Signals/Instances/List.hs:40:10
> In the expression: fft ax
> In an equation for ‘it’: it = fft ax
> 
> 
> Thanks!

The reason you're getting this error is because all you know about your
instance is that the type of fft is :: [Complex Double] -> [Complex
Double].

Since by definition this [Complex Double] is ComplexSignalType sx, all
we know about the associated instance (parametrized by sx) is that
ComplexSignalType sx ~ [Complex Double]. Since ComplexSignalType is a
type family, it's not injective, so this does not suffice to uniquely
identify our actual instance (sx, here called s0 by GHC).

For example, we could have a second instance:

instance Complexable () where
  type ComplexSignalType () = [Complex Double]

instance FourierTransformable () where
  fft = error "oops"

And with this instance, fft would also be [Complex Double] -> [Complex
Double] but the behavior of would clearly be different to your actually
intended function.

If you think your signal function is bijective, you could use a two-way
functional dependency like this:

class Complexable sx cx | sx -> cx, cx -> sx

class Complexable sx cx => FourierTransformable sx cx where
  fft :: cx -> cx

Or if you want to avoid the overhead of redesigning Complexable you
could even do something like this:

class (cx ~ ComplexSignalType sx, Complexable sx) => FourierTransformable sx cx | cx -> sx where
  fft :: cx -> cx

Either way, if instance selection should be possible based solely on the
type of ‘cx’, then ‘cx’ must imply everything contained in the instance
head.