[Haskell-cafe] Re: instance Eq (a -> b)

[roconnor at theorem.ca]

On Wed, 14 Apr 2010, Ashley Yakeley wrote:

> Joe Fredette wrote:
>> this is bounded, enumerable, but infinite.
>
> The question is whether there are types like this. If so, we would need a new 
> class:
>
>  class Finite a where
>    allValues :: [a]
>
>  instance (Finite a,Eq b) => Eq (a -> b) where
>     p == q = fmap p allValues == fmap q allValues

As ski noted on #haskell we probably want to extend this to work on 
Compact types and not just Finite types

instance (Compact a, Eq b) => Eq (a -> b) where ...

For example (Int -> Bool) is a perfectly fine Compact set that isn't 
finite and (Int -> Bool) -> Int has a decidable equality in Haskell (which 
Oleg claims that everyone knows ;).

I don't know off the top of my head what the class member for Compact 
should be.  I'd guess it should have a member search :: (a -> Bool) -> a 
with the specificaiton that p (search p) = True iff p is True from some a. 
But I'm not sure if this is correct or not.  Maybe someone know knows more 
than I do can claify what the member of the Compact class should be.

<http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/>

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''