Generalizing some type signatures involving Int

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

Generalizing some type signatures involving Int

Vanessa McHale
Would it be possible to generalize replicate and length to have type
signatures

replicate :: Integral a => a -> b -> [b]

and

length :: (Integral a, Foldable t) => t b -> a

?

There have been a few instances where such a thing would have been
useful to me.

Cheers



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

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

RE: Generalizing some type signatures involving Int

Alexandre Rodrigues

:+1: from me.

 


From: Libraries <[hidden email]> on behalf of Vanessa McHale <[hidden email]>
Sent: Wednesday, November 14, 2018 1:18:58 AM
To: Haskell Libraries
Subject: Generalizing some type signatures involving Int
 
Would it be possible to generalize replicate and length to have type
signatures

replicate :: Integral a => a -> b -> [b]

and

length :: (Integral a, Foldable t) => t b -> a

?

There have been a few instances where such a thing would have been
useful to me.

Cheers



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

Re: Generalizing some type signatures involving Int

Eric Mertens
Int is the right type to be able to do efficient internal operations when implementing length and replicate. It's unlikely that someone would want to run these operations on another type internally than Int. Some times people propose types like these where they imagine just a built-in use of fromIntegral on either the initial argument or the result, but that really quite unnecessary. Could you elaborate on what cases you had in mind?

While genericLength exists, I have yet to see a good use of it.

Best regards,
Eric Mertens
glguy

On Tue, Nov 13, 2018 at 5:34 PM Alexandre Rodrigues <[hidden email]> wrote:

:+1: from me.

 


From: Libraries <[hidden email]> on behalf of Vanessa McHale <[hidden email]>
Sent: Wednesday, November 14, 2018 1:18:58 AM
To: Haskell Libraries
Subject: Generalizing some type signatures involving Int
 
Would it be possible to generalize replicate and length to have type
signatures

replicate :: Integral a => a -> b -> [b]

and

length :: (Integral a, Foldable t) => t b -> a

?

There have been a few instances where such a thing would have been
useful to me.

Cheers


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


--
Eric Mertens

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

Re: Generalizing some type signatures involving Int

Evan Laforge
In reply to this post by Vanessa McHale
You can already get these as Data.List.genericLength and
Data.List.genericReplicate

As for changing the prelude ones, this would probably cause a lot of
busywork.  Where I work we compile with -Werror and -Wtype-defaults,
so a lot of places might have to get type annotations.
On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:

>
> Would it be possible to generalize replicate and length to have type
> signatures
>
> replicate :: Integral a => a -> b -> [b]
>
> and
>
> length :: (Integral a, Foldable t) => t b -> a
>
> ?
>
> There have been a few instances where such a thing would have been
> useful to me.
>
> Cheers
>
>
> _______________________________________________
> 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: Generalizing some type signatures involving Int

David Feuer
genericLength is extremely inefficient for typical numeric types. Int is a rather sad type for these things; it really should be Word. But that may not be worth fixing.

On Tue, Nov 13, 2018, 9:51 PM Evan Laforge <[hidden email] wrote:
You can already get these as Data.List.genericLength and
Data.List.genericReplicate

As for changing the prelude ones, this would probably cause a lot of
busywork.  Where I work we compile with -Werror and -Wtype-defaults,
so a lot of places might have to get type annotations.
On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>
> Would it be possible to generalize replicate and length to have type
> signatures
>
> replicate :: Integral a => a -> b -> [b]
>
> and
>
> length :: (Integral a, Foldable t) => t b -> a
>
> ?
>
> There have been a few instances where such a thing would have been
> useful to me.
>
> Cheers
>
>
> _______________________________________________
> 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

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

Re: Generalizing some type signatures involving Int

Vanessa McHale
In reply to this post by Eric Mertens

I certainly do! What's wrong with iterating over a Word?

On 11/13/18 8:49 PM, Eric Mertens wrote:
Int is the right type to be able to do efficient internal operations when implementing length and replicate. It's unlikely that someone would want to run these operations on another type internally than Int. Some times people propose types like these where they imagine just a built-in use of fromIntegral on either the initial argument or the result, but that really quite unnecessary. Could you elaborate on what cases you had in mind?

While genericLength exists, I have yet to see a good use of it.

Best regards,
Eric Mertens
glguy

On Tue, Nov 13, 2018 at 5:34 PM Alexandre Rodrigues <[hidden email]> wrote:

:+1: from me.

 


From: Libraries <[hidden email]> on behalf of Vanessa McHale <[hidden email]>
Sent: Wednesday, November 14, 2018 1:18:58 AM
To: Haskell Libraries
Subject: Generalizing some type signatures involving Int
 
Would it be possible to generalize replicate and length to have type
signatures

replicate :: Integral a => a -> b -> [b]

and

length :: (Integral a, Foldable t) => t b -> a

?

There have been a few instances where such a thing would have been
useful to me.

Cheers


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


--
Eric Mertens

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

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing some type signatures involving Int

Vanessa McHale
In reply to this post by Evan Laforge
Thanks! This is a decent stopgap.

On 11/13/18 8:50 PM, Evan Laforge wrote:

> You can already get these as Data.List.genericLength and
> Data.List.genericReplicate
>
> As for changing the prelude ones, this would probably cause a lot of
> busywork.  Where I work we compile with -Werror and -Wtype-defaults,
> so a lot of places might have to get type annotations.
> On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>> Would it be possible to generalize replicate and length to have type
>> signatures
>>
>> replicate :: Integral a => a -> b -> [b]
>>
>> and
>>
>> length :: (Integral a, Foldable t) => t b -> a
>>
>> ?
>>
>> There have been a few instances where such a thing would have been
>> useful to me.
>>
>> Cheers
>>
>>
>> _______________________________________________
>> 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

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing some type signatures involving Int

David Feuer
No, genericLength is *not* a decent stopgap. It's horrible. Just look at the implementation!

On Tue, Nov 13, 2018, 10:21 PM Vanessa McHale <[hidden email] wrote:
Thanks! This is a decent stopgap.

On 11/13/18 8:50 PM, Evan Laforge wrote:
> You can already get these as Data.List.genericLength and
> Data.List.genericReplicate
>
> As for changing the prelude ones, this would probably cause a lot of
> busywork.  Where I work we compile with -Werror and -Wtype-defaults,
> so a lot of places might have to get type annotations.
> On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>> Would it be possible to generalize replicate and length to have type
>> signatures
>>
>> replicate :: Integral a => a -> b -> [b]
>>
>> and
>>
>> length :: (Integral a, Foldable t) => t b -> a
>>
>> ?
>>
>> There have been a few instances where such a thing would have been
>> useful to me.
>>
>> Cheers
>>
>>
>> _______________________________________________
>> 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

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

Re: Generalizing some type signatures involving Int

Vanessa McHale
In reply to this post by Evan Laforge
I want more than this, actually. genericLength doesn't work over any
Foldable.

On 11/13/18 8:50 PM, Evan Laforge wrote:

> You can already get these as Data.List.genericLength and
> Data.List.genericReplicate
>
> As for changing the prelude ones, this would probably cause a lot of
> busywork.  Where I work we compile with -Werror and -Wtype-defaults,
> so a lot of places might have to get type annotations.
> On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>> Would it be possible to generalize replicate and length to have type
>> signatures
>>
>> replicate :: Integral a => a -> b -> [b]
>>
>> and
>>
>> length :: (Integral a, Foldable t) => t b -> a
>>
>> ?
>>
>> There have been a few instances where such a thing would have been
>> useful to me.
>>
>> Cheers
>>
>>
>> _______________________________________________
>> 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

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing some type signatures involving Int

Vanessa McHale
In reply to this post by David Feuer

This is perhaps not the right place, but if there are benchmarks proving that genericLength is slower than it should be, it should be easy to add a SPECIALIZE pragma.

On 11/13/18 9:13 PM, David Feuer wrote:
genericLength is extremely inefficient for typical numeric types. Int is a rather sad type for these things; it really should be Word. But that may not be worth fixing.

On Tue, Nov 13, 2018, 9:51 PM Evan Laforge <[hidden email] wrote:
You can already get these as Data.List.genericLength and
Data.List.genericReplicate

As for changing the prelude ones, this would probably cause a lot of
busywork.  Where I work we compile with -Werror and -Wtype-defaults,
so a lot of places might have to get type annotations.
On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>
> Would it be possible to generalize replicate and length to have type
> signatures
>
> replicate :: Integral a => a -> b -> [b]
>
> and
>
> length :: (Integral a, Foldable t) => t b -> a
>
> ?
>
> There have been a few instances where such a thing would have been
> useful to me.
>
> Cheers
>
>
> _______________________________________________
> 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

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

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing some type signatures involving Int

David Feuer
In reply to this post by Vanessa McHale
You still haven't said why you need this. Only a rather exotic data structure is likely to have a length greater than maxBound @Int.

On Tue, Nov 13, 2018, 10:23 PM Vanessa McHale <[hidden email] wrote:
I want more than this, actually. genericLength doesn't work over any
Foldable.

On 11/13/18 8:50 PM, Evan Laforge wrote:
> You can already get these as Data.List.genericLength and
> Data.List.genericReplicate
>
> As for changing the prelude ones, this would probably cause a lot of
> busywork.  Where I work we compile with -Werror and -Wtype-defaults,
> so a lot of places might have to get type annotations.
> On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>> Would it be possible to generalize replicate and length to have type
>> signatures
>>
>> replicate :: Integral a => a -> b -> [b]
>>
>> and
>>
>> length :: (Integral a, Foldable t) => t b -> a
>>
>> ?
>>
>> There have been a few instances where such a thing would have been
>> useful to me.
>>
>> Cheers
>>
>>
>> _______________________________________________
>> 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

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

Re: Generalizing some type signatures involving Int

David Feuer
In reply to this post by Vanessa McHale
That won't help whatsoever in most cases. The matter has been discussed several times with no progress. If you want to add RULES for Int8, Int16, ..., Word, Word8, ..., and Natural to match the ones for Int and Integer, that would make sense, but the basic problem will remain for unmentioned types.

On Tue, Nov 13, 2018, 10:24 PM Vanessa McHale <[hidden email] wrote:

This is perhaps not the right place, but if there are benchmarks proving that genericLength is slower than it should be, it should be easy to add a SPECIALIZE pragma.

On 11/13/18 9:13 PM, David Feuer wrote:
genericLength is extremely inefficient for typical numeric types. Int is a rather sad type for these things; it really should be Word. But that may not be worth fixing.

On Tue, Nov 13, 2018, 9:51 PM Evan Laforge <[hidden email] wrote:
You can already get these as Data.List.genericLength and
Data.List.genericReplicate

As for changing the prelude ones, this would probably cause a lot of
busywork.  Where I work we compile with -Werror and -Wtype-defaults,
so a lot of places might have to get type annotations.
On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>
> Would it be possible to generalize replicate and length to have type
> signatures
>
> replicate :: Integral a => a -> b -> [b]
>
> and
>
> length :: (Integral a, Foldable t) => t b -> a
>
> ?
>
> There have been a few instances where such a thing would have been
> useful to me.
>
> Cheers
>
>
> _______________________________________________
> 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

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

RE: Generalizing some type signatures involving Int

Alexandre Rodrigues

I spoke too soon, I failed to consider that such a proposal must have been under consideration many times before, and there must have been a good reason for it to not to move forward.

Adding RULES for the most commonly used integer types is probably a good place to start, but perhaps I am mistaken.

 


From: Libraries <[hidden email]> on behalf of David Feuer <[hidden email]>
Sent: Wednesday, November 14, 2018 3:30:38 AM
To: Vanessa McHale
Cc: Haskell Libraries
Subject: Re: Generalizing some type signatures involving Int
 
That won't help whatsoever in most cases. The matter has been discussed several times with no progress. If you want to add RULES for Int8, Int16, ..., Word, Word8, ..., and Natural to match the ones for Int and Integer, that would make sense, but the basic problem will remain for unmentioned types.

On Tue, Nov 13, 2018, 10:24 PM Vanessa McHale <[hidden email] wrote:

This is perhaps not the right place, but if there are benchmarks proving that genericLength is slower than it should be, it should be easy to add a SPECIALIZE pragma.

On 11/13/18 9:13 PM, David Feuer wrote:
genericLength is extremely inefficient for typical numeric types. Int is a rather sad type for these things; it really should be Word. But that may not be worth fixing.

On Tue, Nov 13, 2018, 9:51 PM Evan Laforge <[hidden email] wrote:
You can already get these as Data.List.genericLength and
Data.List.genericReplicate

As for changing the prelude ones, this would probably cause a lot of
busywork.  Where I work we compile with -Werror and -Wtype-defaults,
so a lot of places might have to get type annotations.
On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>
> Would it be possible to generalize replicate and length to have type
> signatures
>
> replicate :: Integral a => a -> b -> [b]
>
> and
>
> length :: (Integral a, Foldable t) => t b -> a
>
> ?
>
> There have been a few instances where such a thing would have been
> useful to me.
>
> Cheers
>
>
> _______________________________________________
> 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

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

Re: Generalizing some type signatures involving Int

Carter Schonwald
In reply to this post by David Feuer
Agreed. 

As David and Eric both say:
For in heap / memory size structures, it’s impossible to ever have an in ram structure that exceeds the largest positive value for Int.  And ghc is also quite good at optimizing int.  

1) what is your application domain / context ?

2) all of these are implementable in user space, what design / implementation experiments have you done ?

It’s worth mentioning that RULES style optimization in this case would only run AFTER it’s been specialized to a concrete type.  And that short of lots of specialize pragmas or inlining , the generic code will thusly miss out on all sorts of unboxong etc.  

On Tue, Nov 13, 2018 at 10:31 PM David Feuer <[hidden email]> wrote:
That won't help whatsoever in most cases. The matter has been discussed several times with no progress. If you want to add RULES for Int8, Int16, ..., Word, Word8, ..., and Natural to match the ones for Int and Integer, that would make sense, but the basic problem will remain for unmentioned types.

On Tue, Nov 13, 2018, 10:24 PM Vanessa McHale <[hidden email] wrote:

This is perhaps not the right place, but if there are benchmarks proving that genericLength is slower than it should be, it should be easy to add a SPECIALIZE pragma.

On 11/13/18 9:13 PM, David Feuer wrote:
genericLength is extremely inefficient for typical numeric types. Int is a rather sad type for these things; it really should be Word. But that may not be worth fixing.

On Tue, Nov 13, 2018, 9:51 PM Evan Laforge <[hidden email] wrote:
You can already get these as Data.List.genericLength and
Data.List.genericReplicate

As for changing the prelude ones, this would probably cause a lot of
busywork.  Where I work we compile with -Werror and -Wtype-defaults,
so a lot of places might have to get type annotations.
On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>
> Would it be possible to generalize replicate and length to have type
> signatures
>
> replicate :: Integral a => a -> b -> [b]
>
> and
>
> length :: (Integral a, Foldable t) => t b -> a
>
> ?
>
> There have been a few instances where such a thing would have been
> useful to me.
>
> Cheers
>
>
> _______________________________________________
> 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
_______________________________________________
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: Generalizing some type signatures involving Int

Henning Thielemann
In reply to this post by David Feuer

On Tue, 13 Nov 2018, David Feuer wrote:

> No, genericLength is *not* a decent stopgap. It's horrible. Just look at
> the implementation!

It looks like it is intended to return something like a lazy Peano number.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing some type signatures involving Int

David Feuer
That is precisely correct. And I have heard that it has actually been
used that way ... once. It's not exactly a common application.
On Thu, Nov 15, 2018 at 1:39 PM Henning Thielemann
<[hidden email]> wrote:
>
>
> On Tue, 13 Nov 2018, David Feuer wrote:
>
> > No, genericLength is *not* a decent stopgap. It's horrible. Just look at
> > the implementation!
>
> It looks like it is intended to return something like a lazy Peano number.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing some type signatures involving Int

Zemyla
In reply to this post by Carter Schonwald
It's not actually impossible to have an in RAM structure that exceeds
the largest positive value for Int. Data.Sequence.replicate does it by
exploiting sharing. replicate n a uses O(lg n) space.

> length $ let x = Data.Sequence.Replicate maxBound 'a' :> 'b' in mappend x x
0

Also, I really would like to have all the length and count-based
functions in base, containers, etc. take or return Words, but there's
way too much inertia behind Ints, even if it means you have to check
for negative numbers (which really runs counter to the main thesis
behind Haskell; i.e. have your types say what you mean).

On Thu, Nov 15, 2018 at 12:30 AM Carter Schonwald
<[hidden email]> wrote:

>
> Agreed.
>
> As David and Eric both say:
> For in heap / memory size structures, it’s impossible to ever have an in ram structure that exceeds the largest positive value for Int.  And ghc is also quite good at optimizing int.
>
> 1) what is your application domain / context ?
>
> 2) all of these are implementable in user space, what design / implementation experiments have you done ?
>
> It’s worth mentioning that RULES style optimization in this case would only run AFTER it’s been specialized to a concrete type.  And that short of lots of specialize pragmas or inlining , the generic code will thusly miss out on all sorts of unboxong etc.
>
> On Tue, Nov 13, 2018 at 10:31 PM David Feuer <[hidden email]> wrote:
>>
>> That won't help whatsoever in most cases. The matter has been discussed several times with no progress. If you want to add RULES for Int8, Int16, ..., Word, Word8, ..., and Natural to match the ones for Int and Integer, that would make sense, but the basic problem will remain for unmentioned types.
>>
>> On Tue, Nov 13, 2018, 10:24 PM Vanessa McHale <[hidden email] wrote:
>>>
>>> This is perhaps not the right place, but if there are benchmarks proving that genericLength is slower than it should be, it should be easy to add a SPECIALIZE pragma.
>>>
>>> On 11/13/18 9:13 PM, David Feuer wrote:
>>>
>>> genericLength is extremely inefficient for typical numeric types. Int is a rather sad type for these things; it really should be Word. But that may not be worth fixing.
>>>
>>> On Tue, Nov 13, 2018, 9:51 PM Evan Laforge <[hidden email] wrote:
>>>>
>>>> You can already get these as Data.List.genericLength and
>>>> Data.List.genericReplicate
>>>>
>>>> As for changing the prelude ones, this would probably cause a lot of
>>>> busywork.  Where I work we compile with -Werror and -Wtype-defaults,
>>>> so a lot of places might have to get type annotations.
>>>> On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>>>> >
>>>> > Would it be possible to generalize replicate and length to have type
>>>> > signatures
>>>> >
>>>> > replicate :: Integral a => a -> b -> [b]
>>>> >
>>>> > and
>>>> >
>>>> > length :: (Integral a, Foldable t) => t b -> a
>>>> >
>>>> > ?
>>>> >
>>>> > There have been a few instances where such a thing would have been
>>>> > useful to me.
>>>> >
>>>> > Cheers
>>>> >
>>>> >
>>>> > _______________________________________________
>>>> > 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
>>
>> _______________________________________________
>> 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
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing some type signatures involving Int

Henning Thielemann

On Thu, 15 Nov 2018, Zemyla wrote:

> It's not actually impossible to have an in RAM structure that exceeds
> the largest positive value for Int. Data.Sequence.replicate does it by
> exploiting sharing. replicate n a uses O(lg n) space.
>
>> length $ let x = Data.Sequence.Replicate maxBound 'a' :> 'b' in mappend x x
> 0

One could also imagine a data structure like Multiset/Bag, where every
element has a count and 'length' returns the total count.

> Also, I really would like to have all the length and count-based
> functions in base, containers, etc. take or return Words, but there's
> way too much inertia behind Ints, even if it means you have to check
> for negative numbers (which really runs counter to the main thesis
> behind Haskell; i.e. have your types say what you mean).

We would also need a bound-checked counterpart to Word. Currently,
(-1)::Word or (2-3)::Word is accepted without a runtime error.
Consequently, 'newTake (-1) xs' would likely return the full list xs.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Generalizing some type signatures involving Int

David Feuer
In reply to this post by Zemyla
Data.Sequence actually doesn't support anything outside the Int range. It could, at a small cost. We perform some range checks cheaply using unsigned comparisons. We'd have to stop doing that to allow sequences to be just a tad more absurdly large. Since that's not often useful, sequences are currently limited to lengths of maxBound @Int.

On Thu, Nov 15, 2018, 5:53 PM Zemyla <[hidden email] wrote:
It's not actually impossible to have an in RAM structure that exceeds
the largest positive value for Int. Data.Sequence.replicate does it by
exploiting sharing. replicate n a uses O(lg n) space.

> length $ let x = Data.Sequence.Replicate maxBound 'a' :> 'b' in mappend x x
0

Also, I really would like to have all the length and count-based
functions in base, containers, etc. take or return Words, but there's
way too much inertia behind Ints, even if it means you have to check
for negative numbers (which really runs counter to the main thesis
behind Haskell; i.e. have your types say what you mean).

On Thu, Nov 15, 2018 at 12:30 AM Carter Schonwald
<[hidden email]> wrote:
>
> Agreed.
>
> As David and Eric both say:
> For in heap / memory size structures, it’s impossible to ever have an in ram structure that exceeds the largest positive value for Int.  And ghc is also quite good at optimizing int.
>
> 1) what is your application domain / context ?
>
> 2) all of these are implementable in user space, what design / implementation experiments have you done ?
>
> It’s worth mentioning that RULES style optimization in this case would only run AFTER it’s been specialized to a concrete type.  And that short of lots of specialize pragmas or inlining , the generic code will thusly miss out on all sorts of unboxong etc.
>
> On Tue, Nov 13, 2018 at 10:31 PM David Feuer <[hidden email]> wrote:
>>
>> That won't help whatsoever in most cases. The matter has been discussed several times with no progress. If you want to add RULES for Int8, Int16, ..., Word, Word8, ..., and Natural to match the ones for Int and Integer, that would make sense, but the basic problem will remain for unmentioned types.
>>
>> On Tue, Nov 13, 2018, 10:24 PM Vanessa McHale <[hidden email] wrote:
>>>
>>> This is perhaps not the right place, but if there are benchmarks proving that genericLength is slower than it should be, it should be easy to add a SPECIALIZE pragma.
>>>
>>> On 11/13/18 9:13 PM, David Feuer wrote:
>>>
>>> genericLength is extremely inefficient for typical numeric types. Int is a rather sad type for these things; it really should be Word. But that may not be worth fixing.
>>>
>>> On Tue, Nov 13, 2018, 9:51 PM Evan Laforge <[hidden email] wrote:
>>>>
>>>> You can already get these as Data.List.genericLength and
>>>> Data.List.genericReplicate
>>>>
>>>> As for changing the prelude ones, this would probably cause a lot of
>>>> busywork.  Where I work we compile with -Werror and -Wtype-defaults,
>>>> so a lot of places might have to get type annotations.
>>>> On Tue, Nov 13, 2018 at 5:19 PM Vanessa McHale <[hidden email]> wrote:
>>>> >
>>>> > Would it be possible to generalize replicate and length to have type
>>>> > signatures
>>>> >
>>>> > replicate :: Integral a => a -> b -> [b]
>>>> >
>>>> > and
>>>> >
>>>> > length :: (Integral a, Foldable t) => t b -> a
>>>> >
>>>> > ?
>>>> >
>>>> > There have been a few instances where such a thing would have been
>>>> > useful to me.
>>>> >
>>>> > Cheers
>>>> >
>>>> >
>>>> > _______________________________________________
>>>> > 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
>>
>> _______________________________________________
>> 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
_______________________________________________
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