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 |
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 |
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 |
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 |
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 |
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:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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. On Sat, Apr 17, 2010 at 6:37 PM, Ashley Yakeley <[hidden email]> wrote: Ketil Malde wrote: Why is toChunks exposed?
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
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 |
On Wed, Apr 21, 2010 at 5:25 AM, Max Rabkin <[hidden email]> wrote:
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 |
Free forum by Nabble | Edit this page |