instance Eq (a -> b)

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
70 messages Options
1234
Reply | Threaded
Open this post in threaded view
|

Re: instance Eq (a -> b)

Ashley Yakeley
On 2010-04-15 06:18, Nick Bowler wrote:

> Your definitions seem very strange, because according to this, the
> functions
>
>    f :: Double ->  Double
>    f x = 1/x
>
> and
>
>    g :: Double ->  Double
>    g x = 1/x
>
> are not equal, since (-0.0 == 0.0) yet f (-0.0) /= g (0.0).

There's an impedance mismatch between the IEEE notion of equality (under
which -0.0 == 0.0), and the Haskell notion of equality (where we'd want
x == y to imply f x == f y).

A Haskellish solution would be to implement Eq so that it compares the
bits of the representations of Float and Double, thus -0.0 /= 0.0, NaN
== NaN (if it's the same NaN). But this might surprise people expecting
IEEE equality, which is probably almost everyone using Float or Double.

--
Ashley Yakeley
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: instance Eq (a -> b)

Ketil Malde-5
Ashley Yakeley <[hidden email]> writes:

> There's an impedance mismatch between the IEEE notion of equality
> (under which -0.0 == 0.0), and the Haskell notion of equality (where
> we'd want x == y to imply f x == f y).

Do we also want to modify equality for lazy bytestrings, where equality
is currently independent of chunk segmentation?  (I.e.

  toChunks s1 == toChunks s2 ==> s1 == s2  

but not vice versa.)

My preference would be to keep Eq as it is, a rough approximation of
an intuitive notion of equality.

-k
--
If I haven't seen further, it is by standing in the footprints of giants
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: instance Eq (a -> b)

Ashley Yakeley
In reply to this post by roconnor
[hidden email] wrote:

> 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/>

Here's a first attempt, which works when I tried comparing values of
type ((Integer -> Bool) -> Bool). It needs some generalisation, however.
I want to be able to write these:

   instance (Countable a,Countable b) => Countable (a,b)
   instance (Countable c,Compact b) => Compact (c -> b)

...


{-# LANGUAGE FlexibleInstances #-}
module Compact where

   import Data.List
   import Data.Maybe
   import Prelude

   class Countable a where
     countPrevious :: a -> Maybe a

   countDown :: (Countable a) => a -> [a]
   countDown a = case countPrevious a of
     Just a' -> a':(countDown a')
     Nothing -> []

   instance Countable () where
     countPrevious () = Nothing

   instance Countable Bool where
     countPrevious True = Just False
     countPrevious False = Nothing

   instance Countable Integer where
     countPrevious 0 = Nothing
     countPrevious a | a < 0 = Just (- a - 1)
     countPrevious a = Just (- a)

   instance (Countable a) => Countable (Maybe a) where
     countPrevious = fmap countPrevious

   class Compact a where
     search :: (a -> Bool) -> Maybe a
     forsome :: (a -> Bool) -> Bool
     forsome = isJust . search

   forevery :: (Compact a) => (a -> Bool) -> Bool
   forevery p = not (forsome (not . p))

   instance (Compact a) => Compact (Maybe a) where
     search mab = if mab Nothing
      then Just Nothing
      else fmap Just (search (mab . Just))

   prepend :: (Countable c) => b -> (c -> b) -> c -> b
   prepend b cb c = case countPrevious c of
     Just c' -> cb c'
     Nothing -> b

   find_i :: (Countable c) => ((c -> Bool) -> Bool) -> c -> Bool
   find_i cbb = let
     b = forsome(cbb . (prepend True)) in
     prepend b (find_i (cbb . (prepend b)))

   instance (Countable c) => Compact (c -> Bool) where
     forsome cbb = cbb (find_i cbb)
     search cbb = if forsome cbb then Just(find_i cbb) else Nothing

   instance (Compact a,Eq b) => Eq (a -> b) where
     p == q = forevery (\a -> p a == q a)

   class (Compact a,Countable a) => Finite a where
     allValues :: [a]

   finiteSearch :: (Finite a) => (a -> Bool) -> Maybe a
   finiteSearch p = find p allValues

   instance Compact () where
     search = finiteSearch

   instance Finite () where
     allValues = [()]

   instance Compact Bool where
     search = finiteSearch

   instance Finite Bool where
     allValues = [False,True]

   instance (Finite a) => Finite (Maybe a) where
     allValues = Nothing:(fmap Just allValues)
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: instance Eq (a -> b)

Ashley Yakeley
In reply to this post by Ketil Malde-5
Ketil Malde wrote:
> Do we also want to modify equality for lazy bytestrings, where equality
> is currently independent of chunk segmentation?  (I.e.
>
>   toChunks s1 == toChunks s2 ==> s1 == s2  
>
> but not vice versa.)

Why is toChunks exposed?

--
Ashley Yakeley
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: instance Eq (a -> b)

Ashley Yakeley
In reply to this post by Ashley Yakeley
I wrote:

>   class Compact a where

After reading Luke Palmer's message I'm thinking this might not be the
best name.

--
Ashley Yakeley
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: instance Eq (a -> b)

Edward Kmett-2
In reply to this post by Ashley Yakeley
Because it is the most utilitarian way to get a bunch of strict ByteStrings out of a lazy one.

Yes it exposes an implementation detail, but the alternatives involve an unnatural amount of copying.

-Edward Kmett

On Sat, Apr 17, 2010 at 6:37 PM, Ashley Yakeley <[hidden email]> wrote:
Ketil Malde wrote:
Do we also want to modify equality for lazy bytestrings, where equality
is currently independent of chunk segmentation?  (I.e.

 toChunks s1 == toChunks s2 ==> s1 == s2  
but not vice versa.)

Why is toChunks exposed?

--
Ashley Yakeley

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: instance Eq (a -> b)

Ashley Yakeley
Why is a function that gets a bunch of strict ByteStrings out of a lazy one exposed?

In any case, it sounds like a similar situation to (==) on Float and Double. There's a mismatch between the "Haskellish" desire for a law on (==), and the "convenient" desire for -0.0 == 0.0, or for exposing toChunks. Which one you prefer depends on your attitude. My point is not so much to advocate for the Haskellish viewpoint than to recognise the tension in the design. Float and Double are pretty ugly anyway from a Haskell point of view, since they break a bunch of other desirable properties for (+), (-) and so on.

The theoretical reason for using floating point rather than fixed point is when one needs relative precision over a range of scales: for other needs one should use fixed point or rationals. I added a Fixed type to base, but it doesn't implement the functions in the Floating class and I doubt it's as fast as Double for common arithmetic functions.

It would be possible to represent the IEEE types in a Haskellish way, properly revealing all their ugliness. This would be gratifying for us purists, but would annoy those just trying to get some numeric calculations done.

--
Ashley Yakeley


On Mon, 2010-04-19 at 15:32 -0400, Edward Kmett wrote:
Because it is the most utilitarian way to get a bunch of strict ByteStrings out of a lazy one.

Yes it exposes an implementation detail, but the alternatives involve an unnatural amount of copying.

-Edward Kmett

On Sat, Apr 17, 2010 at 6:37 PM, Ashley Yakeley <[hidden email]> wrote:
Ketil Malde wrote:
Do we also want to modify equality for lazy bytestrings, where equality
is currently independent of chunk segmentation?  (I.e.

 toChunks s1 == toChunks s2 ==> s1 == s2  
but not vice versa.)


Why is toChunks exposed?

--
Ashley Yakeley


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: instance Eq (a -> b)

Edward Kmett-2
I don't mind the 0.0 == -0.0 case, its the NaN /= NaN one that gets me. ;)

The former just says that the equivalence relation you are using isn't structural. The latter breaks the notion that you have an equivalence relation by breaking reflexivity.

Eq doesn't state anywhere that the instances should be structural, though in general where possible it is a good idea, since you don't have to worry about whether or not functions respect your choice of setoid.

Ultimately, I find myself having to play a bit unsafe with lazy bytestrings more often than I'd like to admit. Use of toChunks should always be careful to be safe to work regardless of the size of the chunks exposed, and can also rely on the extra-logical fact enforced by the bytestring internals that each such chunk is non-empty.

It greatly facilitates 'lifting' algorithms that work over strict bytestrings to work over their lazy kin, and its omission would deal a terrible blow to the practical usability and efficiency of the bytestring library. I frankly would be forced to reimplement them from scratch in several packages were it gone.

Ultimately, almost any libraries relies on a contract that extends beyond the level of the type system to ensure they are used them correctly. A malformed 'Ord' instance can wreak havoc with Set, a non-associative 'Monoid' can leak structural information out of a FingerTree.

Similarly, the pleasant fiction that x == y ==> f x == f y -- only holds if the Eq instance is structural, and toChunks can only 'safely' be used in a manner that is oblivious to the structural partitioning of the lazy bytestring.

-Edward Kmett

On Mon, Apr 19, 2010 at 6:02 PM, Ashley Yakeley <[hidden email]> wrote:
Why is a function that gets a bunch of strict ByteStrings out of a lazy one exposed?

In any case, it sounds like a similar situation to (==) on Float and Double. There's a mismatch between the "Haskellish" desire for a law on (==), and the "convenient" desire for -0.0 == 0.0, or for exposing toChunks. Which one you prefer depends on your attitude. My point is not so much to advocate for the Haskellish viewpoint than to recognise the tension in the design. Float and Double are pretty ugly anyway from a Haskell point of view, since they break a bunch of other desirable properties for (+), (-) and so on.

The theoretical reason for using floating point rather than fixed point is when one needs relative precision over a range of scales: for other needs one should use fixed point or rationals. I added a Fixed type to base, but it doesn't implement the functions in the Floating class and I doubt it's as fast as Double for common arithmetic functions.

It would be possible to represent the IEEE types in a Haskellish way, properly revealing all their ugliness. This would be gratifying for us purists, but would annoy those just trying to get some numeric calculations done.

--
Ashley Yakeley



On Mon, 2010-04-19 at 15:32 -0400, Edward Kmett wrote:
Because it is the most utilitarian way to get a bunch of strict ByteStrings out of a lazy one.

Yes it exposes an implementation detail, but the alternatives involve an unnatural amount of copying.

-Edward Kmett

On Sat, Apr 17, 2010 at 6:37 PM, Ashley Yakeley <[hidden email]> wrote:
Ketil Malde wrote:
Do we also want to modify equality for lazy bytestrings, where equality
is currently independent of chunk segmentation?  (I.e.

 toChunks s1 == toChunks s2 ==> s1 == s2  
but not vice versa.)


Why is toChunks exposed?

--
Ashley Yakeley


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Re: instance Eq (a -> b)

Max Rabkin-2
On Wed, Apr 21, 2010 at 1:44 AM, Edward Kmett <[hidden email]> wrote:
> Eq doesn't state anywhere that the instances should be structural, though in
> general where possible it is a good idea, since you don't have to worry
> about whether or not functions respect your choice of setoid.

Wikipedia's definition of structural equality is an object-oriented
one, but if by structural equality you mean the natural equality on
algebraic datatypes (as derived automatically), I don't believe this
is quite the case. If the type is abstract, surely the Eq instance
need only be a quotient w.r.t. the operations defined on it. Thus, for
example, two Sets can be considered equal if they contain the same
elements, rather than having identical tree shapes (except that
Data.Set exports unsafe functions, like mapMonotonic which has an
unchecked precondition).

--Max
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Re: Re: instance Eq (a -> b)

Edward Kmett-2
On Wed, Apr 21, 2010 at 5:25 AM, Max Rabkin <[hidden email]> wrote:
On Wed, Apr 21, 2010 at 1:44 AM, Edward Kmett <[hidden email]> wrote:
> Eq doesn't state anywhere that the instances should be structural, though in
> general where possible it is a good idea, since you don't have to worry
> about whether or not functions respect your choice of setoid.

Wikipedia's definition of structural equality is an object-oriented
one, but if by structural equality you mean the natural equality on
algebraic datatypes (as derived automatically), I don't believe this
is quite the case. If the type is abstract, surely the Eq instance
need only be a quotient w.r.t. the operations defined on it. Thus, for
example, two Sets can be considered equal if they contain the same
elements, rather than having identical tree shapes (except that
Data.Set exports unsafe functions, like mapMonotonic which has an
unchecked precondition).

Yes. My point about why falling back on structural equality is a good idea when possible, is that then you don't have to work so hard to make sure that x == y =>  f x == f y holds. When your equality instance isn't structural you need to effectively prove a theorem every time you work with the structure to avoid violating preconceptions. My post was acknowledging the expedience of such methods.

I think we are using a lot of words to agree with one another. ;)

-Edward Kmett


 
--Max


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
1234