# instance Eq (a -> b) Classic List Threaded 70 messages 1234
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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. > > 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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 KmettOn Mon, Apr 19, 2010 at 6:02 PM, Ashley Yakeley 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
Open this post in threaded view
|

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

 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