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

[Maciej Piechotka]

On Tue, 2010-04-13 at 23:03 -0700, Ashley Yakeley wrote:
> Why isn't there an instance Eq (a -> b) ?
> 
>    allValues :: (Bounded a,Enum a) => [a]
>    allValues = enumFrom minBound
> 
>    instance (Bounded a,Enum a,Eq b) => Eq (a -> b) where
>      p == q = fmap p allValues == fmap q allValues
> 
> Of course, it's not perfect, since empty types are finite but not 
> Bounded. One can nevertheless make them instances of Bounded with 
> undefined bounds, and have enumFrom and friends always return the empty 
> list.
> 

I guess that the fact that:
- It is costly. On modern machine comparing Int -> a functions would
take 18446744073709551615 steps. Using optimistic assumption (3 GHz, 1
clock per check) it would take 185948 years. Ok - it can be parallelised
but  it would make it better by factor of 16 (which would be
monumentally offset by the fact you likely have this 16 clock cycles
spent on computation/memory access etc.).
- It is rarely needed. I had much often errors about missing Eq (a -> b)
instances when I had error then I needed it.

> It seems one should also be able to write
> 
>    instance (Bounded a,Enum a) => Traversable (a -> b) where ???
> 
> But this turns out to be curiously hard.
> 

To begin with {_|_} -> R - LHS is finite (so bound and enumerable) but
there is uncountable number of such functions.

Q⋂[0,1] -> Q⋂[0,1] -Is not countable (enumerable) as well.
Q⋂[0,1] -> {0,1} - Also uncountable (due to diagonalisation argument)
IIRC

Regards

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20100414/9f68e08b/attachment.bin