Give alternate default definition for (<=)

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

Give alternate default definition for (<=)

Dannyu NDos
I have following datatype for representing arbitrary computable numbers:

    newtype Computable = Inexact (Word -> Integer)

"Inexact" encapsulates Cauchy sequences.

min and max will halt:

    instance Ord Computable where
        min (Inexact f) (Inexact g) = Inexact (\n -> min (f n) (g n))
        max (Inexact f) (Inexact g) = Inexact (\n -> max (f n) (g n))

But comparison functions won't halt for same numbers:

        compare (Inexact f) (Inexact g) = go 0 where
            go n = compare (f n) (g n) <> go (n+1)

So in this case, it would be inappropriate to defaultly define min and max.

It would be nice if there was a function for alternately defining comparison functions:

    defaultLessThan :: Ord a => a -> a -> Bool
    defaultLessThan x y = x == y || x == min x y

Then we can let (<=) = defaultLessThan.

Also I have to mention that the "realAbs" function I suggested in January must be the following definition in this regard:

    realAbs x = max x (negate x)

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Give alternate default definition for (<=)

Dannyu NDos
"defaultLTorEQ" would be a better name, since it's for (<=), not (<).

2020년 5월 8일 (금) 오전 10:49, Dannyu NDos <[hidden email]>님이 작성:
I have following datatype for representing arbitrary computable numbers:

    newtype Computable = Inexact (Word -> Integer)

"Inexact" encapsulates Cauchy sequences.

min and max will halt:

    instance Ord Computable where
        min (Inexact f) (Inexact g) = Inexact (\n -> min (f n) (g n))
        max (Inexact f) (Inexact g) = Inexact (\n -> max (f n) (g n))

But comparison functions won't halt for same numbers:

        compare (Inexact f) (Inexact g) = go 0 where
            go n = compare (f n) (g n) <> go (n+1)

So in this case, it would be inappropriate to defaultly define min and max.

It would be nice if there was a function for alternately defining comparison functions:

    defaultLessThan :: Ord a => a -> a -> Bool
    defaultLessThan x y = x == y || x == min x y

Then we can let (<=) = defaultLessThan.

Also I have to mention that the "realAbs" function I suggested in January must be the following definition in this regard:

    realAbs x = max x (negate x)

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Give alternate default definition for (<=)

Sven Panne-2
In reply to this post by Dannyu NDos
Am Fr., 8. Mai 2020 um 03:50 Uhr schrieb Dannyu NDos <[hidden email]>:
I have following datatype for representing arbitrary computable numbers:

    newtype Computable = Inexact (Word -> Integer)

"Inexact" encapsulates Cauchy sequences.

min and max will halt:

    instance Ord Computable where [...]

Eq is a superclass of Ord, so how do you define that for Computable? 

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Fwd: Give alternate default definition for (<=)

Dannyu NDos


---------- Forwarded message ---------
보낸사람: Dannyu NDos <[hidden email]>
Date: 2020년 5월 8일 (금) 16:35
Subject: Re: Give alternate default definition for (<=)
To: Sven Panne <[hidden email]>


2020년 5월 8일 (금) 15:33, Sven Panne <[hidden email]>님이 작성:
Eq is a superclass of Ord, so how do you define that for Computable?

instance Eq Computable where
    x == y = x <= y && y <= x

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Give alternate default definition for (<=)

Carter Schonwald
That seems undecidable in general.

On Fri, May 8, 2020 at 6:18 PM Dannyu NDos <[hidden email]> wrote:


---------- Forwarded message ---------
보낸사람: Dannyu NDos <[hidden email]>
Date: 2020년 5월 8일 (금) 16:35
Subject: Re: Give alternate default definition for (<=)
To: Sven Panne <[hidden email]>


2020년 5월 8일 (금) 15:33, Sven Panne <[hidden email]>님이 작성:
Eq is a superclass of Ord, so how do you define that for Computable?

instance Eq Computable where
    x == y = x <= y && y <= x
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Give alternate default definition for (<=)

Dannyu NDos
2020년 5월 9일 (토) 12:35, Carter Schonwald <[hidden email]>님이 작성:
That seems undecidable in general.

True. It is proven that there is no algorithm that compares arbitrary computable numbers.

In other words, min and max are algorithms, but (==) and (<=) are not.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Give alternate default definition for (<=)

Dannyu NDos
In reply to this post by Carter Schonwald
Sorry for the mix-up. It really turns out that I can't really define (==) with only min and max. However, it turns out that the suggested default definition is effective when (==) is properly given. I've come up with another type where it is effective, so stay tuned.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries