Unless I've missed it, there is no typeclass for positive integers in GHC.
Is there any particular reason it doesn't exist? Also, it seems Word would be a far better type in the likes of (!!), length, etc. Is it just tradition that resulted in the use of Int? Daniel _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On 2006-03-24, Daniel McAllansmith <[hidden email]> wrote:
> Unless I've missed it, there is no typeclass for positive integers in GHC. > Is there any particular reason it doesn't exist? The number of useable operations is small, and checks for leaving the domain would have to be done all the time. It basically doesn't buy anything. > Also, it seems Word would be a far better type in the likes of (!!), length, > etc. Is it just tradition that resulted in the use of Int? No. I'd like to be able to get the differences in length both positive and negative, for example. (This could be fixed by making (+) and (-) instance of an MPTC, though, as additive torsors.) -- Aaron Denney -><- _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Friday 24 March 2006 13:14, Aaron Denney wrote:
> On 2006-03-24, Daniel McAllansmith <[hidden email]> wrote: > > Unless I've missed it, there is no typeclass for positive integers in > > GHC. Is there any particular reason it doesn't exist? > > The number of useable operations is small, and checks for leaving the > domain would have to be done all the time. It basically doesn't buy > anything. I can see the domain bounds check would be a problem in theory, but in practice doesn't the type enforce that? Keeping Word positive costs nothing because it just overflows. Wouldn't it be much the same? Not that I'm really concerned about the absence, probably because of your other point. > > > Also, it seems Word would be a far better type in the likes of (!!), > > length, etc. Is it just tradition that resulted in the use of Int? > > No. I'd like to be able to get the differences in length both positive > and negative, for example. (This could be fixed by making (+) and (-) > instance of an MPTC, though, as additive torsors.) An additive torsor is? I'd maintain that the difference between two lengths is an entirely different quantity from the length of a list. Though I'll admit the extra work converting to Integrals to get that quantity would be a pain, and probably not worth it. I was more concerned about functions with Int as input, such as (!!), that can result in errors. If practically feasible I would have preferred (!!) to take a Word rather than Int, even though you'd sometimes need bounds checks at fromInteger calls to be safe. I suppose the 'correct' type for the index in (!!) would be (Integral n, LowBounded n) => n if such a low bound type class existed. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
> An additive torsor is?
Surprisingly, there is a page on MathWorld about Torsors but it is empty. Google turned up the following page with a good explanation. http://math.ucr.edu/home/baez/torsors.html > I'd maintain that the difference between two lengths is an entirely different > quantity from the length of a list. (Maybe this is a good example of what the term torsor captures.) Thanks to Aaron for expanding our vocabulary. Jared. -- http://www.updike.org/~jared/ reverse ")-:" _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Daniel McAllansmith
Daniel McAllansmith wrote:
> I can see the domain bounds check would be a problem in theory, but in > practice doesn't the type enforce that? Keeping Word positive costs nothing > because it just overflows. Wouldn't it be much the same? If you're planning wraparound semantics then you're better off with Int indexes. Passing an index congruent to -1 mod 2^32 is certainly an error, and (!!) may as well fail immediately rather than try to traverse 2^32-1 list nodes. I think both Int and Word are equally "correct" here, since both are proper supersets of the valid set of indexes. (If you're working with lists so long that Int may not be big enough, you shouldn't trust Word either.) Haskell 98's List module supplies "generic" versions of the list functions, like genericIndex :: Integral a => [b] -> a -> b, which will work with Word. -- Ben _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Daniel McAllansmith
Daniel McAllansmith <[hidden email]> wrote:
> Unless I've missed it, there is no typeclass for positive integers in > GHC. Is there any particular reason it doesn't exist? > > Also, it seems Word would be a far better type in the likes of (!!), > length, etc. Is it just tradition that resulted in the use of Int? There is a good argument that what you really want here is the lazy infinite natural numbers. Think Peano: data Natural = Zero | Succ Natural The clear correspondance between lazy lists and the size/index of a lazy list makes this type fairly compelling. It can be jolly useful, particularly with infinite streams, to be able to compute (length xs > n) without forcing the evaluation of the list to more than n places. Of course, if the naturals were actually represented in Peano (unary) form, that would be somewhat inefficient, but there are various strategies that can be used to make the representation smaller whilst retaining their nice properties. Regards, Malcolm _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Fri, 24 Mar 2006, Malcolm Wallace wrote: > Daniel McAllansmith <[hidden email]> wrote: > >> Unless I've missed it, there is no typeclass for positive integers in >> GHC. Is there any particular reason it doesn't exist? >> >> Also, it seems Word would be a far better type in the likes of (!!), >> length, etc. Is it just tradition that resulted in the use of Int? > > There is a good argument that what you really want here is the lazy > infinite natural numbers. Think Peano: > > data Natural = Zero | Succ Natural > > The clear correspondance between lazy lists and the size/index of a lazy > list makes this type fairly compelling. It can be jolly useful, > particularly with infinite streams, to be able to compute > (length xs > n) > without forcing the evaluation of the list to more than n places. Fortunately there are already List functions like genericLength and genericTake, which can handle such a number type. Shouldn't be Peano numbers part of the standard libraries? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Aaron Denney
On Fri, 24 Mar 2006, Aaron Denney wrote: > On 2006-03-24, Daniel McAllansmith <[hidden email]> wrote: >> Unless I've missed it, there is no typeclass for positive integers in GHC. >> Is there any particular reason it doesn't exist? > > The number of useable operations is small, and checks for leaving the > domain would have to be done all the time. It basically doesn't buy > anything. A new type, say Cardinal as in Modula, would document for the user of a function that only non-negative numbers are allowed and the function writer can be sure, that only non-negative numbers are passed. Today function writers have to check explicitly for negative numbers, when they are not wanted. With a Cardinal type some of these checks can be dropped because of the static guarantee that Cardinals are never negative. Further on think of QuickCheck: A Cardinal type with an Arbitrary instance would save us the (>=0) condition and it would reduce the number of tests that must be skipped because of non-fulfilled conditions. Because I was confronted with adding positivity checks to QuickCheck properties quite frequently, I finally wrote wrappers newtype Cardinal = Cardinal Integer deriving (Show, Read, Eq, Ord, Ix) newtype Card = Card Int deriving (Show, Read, Eq, Ord, Ix) in order to simplify such checks. Since the pros and cons of new types are true for every number type, the discussion whether Cardinal should be supported or not ends up with the question how often it can be used. When I look through my Modula programs I encounter CARDINAL quite often, so yes, it seems to be useful. Inductive definitions of functions of integers need a base case - which is often zero. That is such functions are intended for Cardinals rather than Integers. The (n+k) pattern are often defended because of its use in inductive definitions. So I claim that Cardinals are at least as important as (n+k) patterns. :-) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Hello Henning,
Friday, March 24, 2006, 3:55:55 PM, you wrote: > A new type, say Cardinal as in Modula, would document for the user of a the only problem is what Haskell don't support automatic integral types conversion. you will need to write a lot of `fromIntegral` calls -- Best regards, Bulat mailto:[hidden email] _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Henning Thielemann
> Fortunately there are already List functions like genericLength and
> genericTake, which can handle such a number type. Shouldn't be Peano > numbers part of the standard libraries? Natural numbers are being discussed as a possible part of the new Haskell' standard. http://hackage.haskell.org/trac/haskell-prime/ticket/79 Jared. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Henning Thielemann
On 2006-03-24, Henning Thielemann <[hidden email]> wrote:
> > On Fri, 24 Mar 2006, Aaron Denney wrote: > >> On 2006-03-24, Daniel McAllansmith <[hidden email]> wrote: >>> Unless I've missed it, there is no typeclass for positive integers in GHC. >>> Is there any particular reason it doesn't exist? >> >> The number of useable operations is small, and checks for leaving the >> domain would have to be done all the time. It basically doesn't buy >> anything. > > A new type, say Cardinal as in Modula, would document for the user of a > function that only non-negative numbers are allowed and the function > writer can be sure, that only non-negative numbers are passed. Today > function writers have to check explicitly for negative numbers, when they > are not wanted. With a Cardinal type some of these checks can be dropped > because of the static guarantee that Cardinals are never negative. As long as the constructors aren't exposed, and then the checks get pushed into the injection function. Which really doesn't give us "static safety", but does let us push the discovery earlier, so may still be useful. And indexing still needs to check for overflows. > Further on think of QuickCheck: A Cardinal type with an Arbitrary > instance would save us the (>=0) condition True. > The (n+k) pattern are often defended because of its use in > inductive definitions. So I claim that Cardinals are at least as important > as (n+k) patterns. :-) And neither need to be in the language. :) Basically, my big objection is that it's hard to define many useful operations on them that are statically safe. Any definition of Num a for instance leaves a whole bunch of unsafe methods, or just plain inapplicable methods, such as "negate". Now granted, the numeric hierarchy should be broken up a bit (hmm, I should finish my strawman proposal for Haskell'), but even then I see problems. -- Aaron Denney -><- _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Henning Thielemann
On Fri, 24 Mar 2006, Henning Thielemann <[hidden email]> wrote:
> Further on think of QuickCheck: A Cardinal type with an Arbitrary > instance would save us the (>=0) condition and it would reduce the > number of tests that must be skipped because of non-fulfilled > conditions. Because I was confronted with adding positivity checks to > QuickCheck properties quite frequently, I finally wrote wrappers > newtype Cardinal = Cardinal Integer deriving (Show, Read, Eq, Ord, Ix) > newtype Card = Card Int deriving (Show, Read, Eq, Ord, Ix) > in order to simplify such checks. I wouldn't mind having a natural number type, but the technique above is useful anyway. When using QuickCheck you often need custom generators, and the technique removes the need for non-dependent forAlls: prop_foo (Cardinal n) (Balanced t) (Prime p) (Small s) = ... n ... t ... p ... s ... The property above is considerably easier to read than the following one: prop_foo = forAll cardinal $ \c -> forAll balanced $ \t -> forAll prime $ \p -> forAll small $ \s -> ... n ... t ... p ... s ... It would be nice to have a bunch of newtypes like these in a library. -- /NAD _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Aaron Denney
On Fri, 24 Mar 2006, Aaron Denney wrote: > Basically, my big objection is that it's hard to define many useful > operations on them that are statically safe. Why not defining the Torsor class you suggested? > Any definition of Num a for instance leaves a whole bunch of unsafe > methods, or just plain inapplicable methods, such as "negate". Yes Num class is quite inappropriate. > Now granted, the numeric hierarchy should be broken up a bit (hmm, I > should finish my strawman proposal for Haskell'), but even then I see > problems. Hm, is there something going on? Without breaking compatibility? But class instances become invalid if the hierarchy is modified. If there is some progress towards a refined numeric class hierarchy I want to point again to http://cvs.haskell.org/darcs/numericprelude/ http://cvs.haskell.org/darcs/numericprelude/src/Algebra/Core.lhs I hope I don't annoy you. :-) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Ben Rudiak-Gould
Hello,
On 3/23/06, Ben Rudiak-Gould <[hidden email]> wrote: > Daniel McAllansmith wrote: > > I can see the domain bounds check would be a problem in theory, but in > > practice doesn't the type enforce that? Keeping Word positive costs nothing > > because it just overflows. Wouldn't it be much the same? > > If you're planning wraparound semantics then you're better off with Int > indexes. Passing an index congruent to -1 mod 2^32 is certainly an error, > and (!!) may as well fail immediately rather than try to traverse 2^32-1 > list nodes. I think both Int and Word are equally "correct" here, since both > are proper supersets of the valid set of indexes. (If you're working with > lists so long that Int may not be big enough, you shouldn't trust Word either.) This need not be the case: Haskell has only positive literals, so there could be a separate class that does not have 'negate' and '(-)' of which natural numbers are an instance. Then overflows would only occur through the 'topEnd' of the number :-). Of course one could still use 'n+k' patterns to decrement naturals in loops. -Iavor _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Henning Thielemann
On 2006-03-24, Henning Thielemann <[hidden email]> wrote:
> > On Fri, 24 Mar 2006, Aaron Denney wrote: > >> Basically, my big objection is that it's hard to define many useful >> operations on them that are statically safe. > > Why not defining the Torsor class you suggested? Torsor is not quite the right word -- it's just that one of the contexts for non-negative numbers is very similar to one fairly standard example of torsors -- pointers and offsets. >> Now granted, the numeric hierarchy should be broken up a bit (hmm, I >> should finish my strawman proposal for Haskell'), but even then I see >> problems. > > Hm, is there something going on? A strawman proposal, not yet posted anywhere. > Without breaking compatibility? > But class instances become invalid if the hierarchy is modified. No, compatibility will be broken. Hopefully not for most uses -- I don't think most people define new instances, and those that do will be able to do so more reasonably, so hopefully wouldn't mind. > If there is some > progress towards a refined numeric class hierarchy I want to point again > to > http://cvs.haskell.org/darcs/numericprelude/ > http://cvs.haskell.org/darcs/numericprelude/src/Algebra/Core.lhs > I hope I don't annoy you. :-) Not at all. That is one of the things I looked at a while ago, that has inspired a lot of my decisions -- but I'm more willing to rename things that I think have silly names. And there are a few minor details, like allowing only for euclidean domains rather than principal ideal domains. I will probably actually put two proposals up, with one allowing more generality via MPTCs and FDs (which I truly hope make it into the standard). -- Aaron Denney -><- _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Fri, 24 Mar 2006, Aaron Denney wrote: >> Without breaking compatibility? >> But class instances become invalid if the hierarchy is modified. > > No, compatibility will be broken. Hopefully not for most uses -- I > don't think most people define new instances, and those that do will be > able to do so more reasonably, so hopefully wouldn't mind. There are a lot of instances of Num around. Everywhere where Haskell is used as a wrapper to other languages like CSound, SuperCollider, metapost new numerical instances are defined. Since restructuring the numerical type class hierarchy would break them I assumed that a modified hierarchy is out of scope of Haskell'. > Not at all. That is one of the things I looked at a while ago, that has > inspired a lot of my decisions -- but I'm more willing to rename things > that I think have silly names. And there are a few minor details, like > allowing only for euclidean domains rather than principal ideal domains. > > I will probably actually put two proposals up, with one allowing more > generality via MPTCs and FDs (which I truly hope make it into the > standard). Whatever you propose for Haskell' feel encouraged to also contribute improvements to NumericPrelude. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Jared Updike
On Friday 24 March 2006 14:37, you wrote:
> > An additive torsor is? > > Surprisingly, there is a page on MathWorld about Torsors but it is > empty. Google turned up the following page with a good explanation. > > http://math.ucr.edu/home/baez/torsors.html Nice clear explanation that. Thanks for the link Jared. > > > I'd maintain that the difference between two lengths is an entirely > > different quantity from the length of a list. > > (Maybe this is a good example of what the term torsor captures.) > > Thanks to Aaron for expanding our vocabulary. Yep. Now I agree with Aaron. And now I won't get offended if someone calls me a closet torsor user! :) > > Jared. > -- > http://www.updike.org/~jared/ > reverse ")-:" _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Ben Rudiak-Gould
On Friday 24 March 2006 16:16, Ben Rudiak-Gould wrote:
> Daniel McAllansmith wrote: > > I can see the domain bounds check would be a problem in theory, but in > > practice doesn't the type enforce that? Keeping Word positive costs > > nothing because it just overflows. Wouldn't it be much the same? > > If you're planning wraparound semantics then you're better off with Int > indexes. I wasn't really _planning_ wrap around semantics. More just making the point that saying the cost of using Word is greater than the cost of using Int, due to the bounds checking required, seems unfair. I see your point about quick detection of bad indices, though I'd still rather have the type document the fact that only positive integers are expected. Daniel _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Malcolm Wallace
On Friday 24 March 2006 23:29, Malcolm Wallace wrote:
> Daniel McAllansmith <[hidden email]> wrote: > > Unless I've missed it, there is no typeclass for positive integers in > > GHC. Is there any particular reason it doesn't exist? > > > > Also, it seems Word would be a far better type in the likes of (!!), > > length, etc. Is it just tradition that resulted in the use of Int? > > There is a good argument that what you really want here is the lazy > infinite natural numbers. Think Peano: > > data Natural = Zero | Succ Natural > > The clear correspondance between lazy lists and the size/index of a lazy > list makes this type fairly compelling. It can be jolly useful, > particularly with infinite streams, to be able to compute > (length xs > n) > without forcing the evaluation of the list to more than n places. > > Of course, if the naturals were actually represented in Peano (unary) > form, that would be somewhat inefficient, but there are various > strategies that can be used to make the representation smaller whilst > retaining their nice properties. I was thinking about several things in this thread, torsors, overflow semantics, bounds checking... I wonder if there would be any merit in being able to define constrained subsets of integers and the semantics when/if they overflow. For example, take UNIX nice levels -20 to 19. You could have data ConstrainedInteger = CI {distToMax :: Natural, distToMin :: Natural} this would ensure only the 40 integers can be represented. Then you could have _something_ that defined what happened on overflow, whether it wraps, reflects, errors, truncates or whatever. When it comes to compile, or source preprocessing, time these numbers could be realigned to a primitive Int or Word representation of suitable size and have the appropriate overflow code written in. And, in the case of error or wrap overflow semantics on a set of the right size, the overflow checks could be disabled, like other assertions, at runtime. Daniel _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Jared Updike
G'day all.
Quoting Jared Updike <[hidden email]>: > Surprisingly, there is a page on MathWorld about Torsors but it is > empty. Google turned up the following page with a good explanation. > > http://math.ucr.edu/home/baez/torsors.html Ah, right. So "torsor" is just a short name for "regular group action",which in turn is a short name for "free transitive group action". We discussed these previously in the context of other kinds of difference types: http://www.haskell.org/pipermail/libraries/2005-May/003899.html Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |