Positive integers

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

Positive integers

Daniel McAllansmith
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
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Aaron Denney
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

Daniel McAllansmith
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

Jared Updike
> 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
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Ben Rudiak-Gould
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
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Malcolm Wallace
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
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Henning Thielemann

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

Re: Positive integers

Henning Thielemann
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

Bulat Ziganshin-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Jared Updike
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
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Aaron Denney
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

Nils Anders Danielsson
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
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Henning Thielemann
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

Iavor Diatchki
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
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Aaron Denney
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

Henning Thielemann

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

Re: Re: Positive integers

Daniel McAllansmith
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

Daniel McAllansmith
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
Reply | Threaded
Open this post in threaded view
|

Re: Positive integers

Daniel McAllansmith
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
Reply | Threaded
Open this post in threaded view
|

Re: Re: Positive integers

ajb@spamcop.net
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
12