Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to get around the Coverage Condition for Functional Dependencies without using -XUndecidableInstances

Wen using functional dependencies, I frequently hit the Coverage Condition. It is possible to lift it with UndecidableInstances, but I usually try to stay away from that extension.

Here is a somewhat contrived example, that works without UndecidableInstances:

{-# Language MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances #-}

data Result = Result String
  deriving (Eq, Show)

data Arguments a b = Arguments a b

class Applyable a b | a -> b where
  apply :: a -> b -> Result

instance Applyable (Arguments a b) (a -> b -> Result) where
  (Arguments a b) `apply` f = f a b

When I make the result type more generic, the Coverage Condition fails (hence requiring UndecidableInstances):

{-# Language MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances, UndecidableInstances #-}

data Result a = Result a
  deriving (Eq, Show)

data Arguments a b = Arguments a b

class Applyable a b c | a -> b c where
  apply :: a -> b -> Result c

instance Applyable (Arguments a b) (a -> b -> Result c) c where
  (Arguments a b) `apply` f = f a b

I thought that because b and c are both determined by a, the more generic code should not cause any problems, so my questions:

  1. Are there any possible issues with using UndecidableInstances here
  2. Can I model the above scenario without relying on UndecidableInstances (maybe with type families?)
like image 756
user1078763 Avatar asked Jan 31 '12 07:01

user1078763


1 Answers

There's no big reason to stay away from UndecidableInstances. The worst that can happen is that the type checker starts looping (and tells you about it, I think). You can make the coverage condition more and more clever, but it will never do everything you could want since that's undecidable.

like image 64
augustss Avatar answered Sep 26 '22 08:09

augustss