indexM or (!?)-style accessor for arrays?

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

indexM or (!?)-style accessor for arrays?

Zemyla
This is an issue I originally proposed on GHC Trac, but I'm posting it
here because (I think) the Data.Array package is under the purview of
the Libraries committee.

The vector package has indexM and its cousins so that a user can be
strict in the array without necessarily being strict in the value
retrieved from that array. Arrays don't have that sort of thing,
meaning that anything you do that takes an array will necessarily
leave references to the array unless you force the whole thing, and
that's not only inefficient, it's untenable for general libraries.

What I'm thinking is that the IArray class should have a function like

unsafeAtM :: (Array a e, Ix i, Applicative m) => a i e -> Int -> m e

For compatibility with older code that wouldn't necessarily define
this but would define unsafeAt, we'd have the default implementation

unsafeAtM a !n = pure (unsafeAt a n)

Also, you could have unsafeAt defined in terms of unsafeAtM, so the
minimal implementation could require only one of them:

unsafeAt = (coerce :: (a i e -> Int -> Identity e) -> a i e -> Int ->
e) unsafeAtM

Also, (!?) would be a "safe" indexing tool for arrays, which would
incidentally also force the array without forcing the value inside.
You would have

(!?) :: (Array a e, Ix i) => a i e -> i -> Maybe e
(!?) a e = case bounds a of
  p@(l, u) -> case inRange p e of
    True -> unsafeAtM arr $ unsafeIndex p e
    False -> Nothing
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: indexM or (!?)-style accessor for arrays?

Edward Kmett-2
I'm pretty strongly +1 on this, assuming someone is willing to chase down all the implementation issues, as the current API doesn't really allow for efficient usage.

I'm not sure that Applicative is strong enough to give the desired behavior, though.

e.g. to write a strict fmap (<$!>) you need Monad.

-Edward

On Tue, Aug 13, 2019 at 9:24 AM Zemyla <[hidden email]> wrote:
This is an issue I originally proposed on GHC Trac, but I'm posting it
here because (I think) the Data.Array package is under the purview of
the Libraries committee.

The vector package has indexM and its cousins so that a user can be
strict in the array without necessarily being strict in the value
retrieved from that array. Arrays don't have that sort of thing,
meaning that anything you do that takes an array will necessarily
leave references to the array unless you force the whole thing, and
that's not only inefficient, it's untenable for general libraries.

What I'm thinking is that the IArray class should have a function like

unsafeAtM :: (Array a e, Ix i, Applicative m) => a i e -> Int -> m e

For compatibility with older code that wouldn't necessarily define
this but would define unsafeAt, we'd have the default implementation

unsafeAtM a !n = pure (unsafeAt a n)

Also, you could have unsafeAt defined in terms of unsafeAtM, so the
minimal implementation could require only one of them:

unsafeAt = (coerce :: (a i e -> Int -> Identity e) -> a i e -> Int ->
e) unsafeAtM

Also, (!?) would be a "safe" indexing tool for arrays, which would
incidentally also force the array without forcing the value inside.
You would have

(!?) :: (Array a e, Ix i) => a i e -> i -> Maybe e
(!?) a e = case bounds a of
  p@(l, u) -> case inRange p e of
    True -> unsafeAtM arr $ unsafeIndex p e
    False -> Nothing
_______________________________________________
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: indexM or (!?)-style accessor for arrays?

Zemyla
Well, the reason I say Applicative is because the only method from
Monad which is used is return, which is the same as pure in
Applicative. I'm preparing for when the "Monad of no return" proposal
gets implemented.

On Tue, Aug 13, 2019 at 11:29 AM Edward Kmett <[hidden email]> wrote:

>
> I'm pretty strongly +1 on this, assuming someone is willing to chase down all the implementation issues, as the current API doesn't really allow for efficient usage.
>
> I'm not sure that Applicative is strong enough to give the desired behavior, though.
>
> e.g. to write a strict fmap (<$!>) you need Monad.
>
> -Edward
>
> On Tue, Aug 13, 2019 at 9:24 AM Zemyla <[hidden email]> wrote:
>>
>> This is an issue I originally proposed on GHC Trac, but I'm posting it
>> here because (I think) the Data.Array package is under the purview of
>> the Libraries committee.
>>
>> The vector package has indexM and its cousins so that a user can be
>> strict in the array without necessarily being strict in the value
>> retrieved from that array. Arrays don't have that sort of thing,
>> meaning that anything you do that takes an array will necessarily
>> leave references to the array unless you force the whole thing, and
>> that's not only inefficient, it's untenable for general libraries.
>>
>> What I'm thinking is that the IArray class should have a function like
>>
>> unsafeAtM :: (Array a e, Ix i, Applicative m) => a i e -> Int -> m e
>>
>> For compatibility with older code that wouldn't necessarily define
>> this but would define unsafeAt, we'd have the default implementation
>>
>> unsafeAtM a !n = pure (unsafeAt a n)
>>
>> Also, you could have unsafeAt defined in terms of unsafeAtM, so the
>> minimal implementation could require only one of them:
>>
>> unsafeAt = (coerce :: (a i e -> Int -> Identity e) -> a i e -> Int ->
>> e) unsafeAtM
>>
>> Also, (!?) would be a "safe" indexing tool for arrays, which would
>> incidentally also force the array without forcing the value inside.
>> You would have
>>
>> (!?) :: (Array a e, Ix i) => a i e -> i -> Maybe e
>> (!?) a e = case bounds a of
>>   p@(l, u) -> case inRange p e of
>>     True -> unsafeAtM arr $ unsafeIndex p e
>>     False -> Nothing
>> _______________________________________________
>> 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: indexM or (!?)-style accessor for arrays?

Edward Kmett-2
I'd for some reason assumed that vector's indexM actually combined values for the Unboxed case, but it looks like _it_ should be generalized to Applicative, too.

-Edwrd

On Tue, Aug 13, 2019 at 10:33 AM Zemyla <[hidden email]> wrote:
Well, the reason I say Applicative is because the only method from
Monad which is used is return, which is the same as pure in
Applicative. I'm preparing for when the "Monad of no return" proposal
gets implemented.

On Tue, Aug 13, 2019 at 11:29 AM Edward Kmett <[hidden email]> wrote:
>
> I'm pretty strongly +1 on this, assuming someone is willing to chase down all the implementation issues, as the current API doesn't really allow for efficient usage.
>
> I'm not sure that Applicative is strong enough to give the desired behavior, though.
>
> e.g. to write a strict fmap (<$!>) you need Monad.
>
> -Edward
>
> On Tue, Aug 13, 2019 at 9:24 AM Zemyla <[hidden email]> wrote:
>>
>> This is an issue I originally proposed on GHC Trac, but I'm posting it
>> here because (I think) the Data.Array package is under the purview of
>> the Libraries committee.
>>
>> The vector package has indexM and its cousins so that a user can be
>> strict in the array without necessarily being strict in the value
>> retrieved from that array. Arrays don't have that sort of thing,
>> meaning that anything you do that takes an array will necessarily
>> leave references to the array unless you force the whole thing, and
>> that's not only inefficient, it's untenable for general libraries.
>>
>> What I'm thinking is that the IArray class should have a function like
>>
>> unsafeAtM :: (Array a e, Ix i, Applicative m) => a i e -> Int -> m e
>>
>> For compatibility with older code that wouldn't necessarily define
>> this but would define unsafeAt, we'd have the default implementation
>>
>> unsafeAtM a !n = pure (unsafeAt a n)
>>
>> Also, you could have unsafeAt defined in terms of unsafeAtM, so the
>> minimal implementation could require only one of them:
>>
>> unsafeAt = (coerce :: (a i e -> Int -> Identity e) -> a i e -> Int ->
>> e) unsafeAtM
>>
>> Also, (!?) would be a "safe" indexing tool for arrays, which would
>> incidentally also force the array without forcing the value inside.
>> You would have
>>
>> (!?) :: (Array a e, Ix i) => a i e -> i -> Maybe e
>> (!?) a e = case bounds a of
>>   p@(l, u) -> case inRange p e of
>>     True -> unsafeAtM arr $ unsafeIndex p e
>>     False -> Nothing
>> _______________________________________________
>> 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: indexM or (!?)-style accessor for arrays?

Zemyla
Also, even if the base implementation of indexM were Monad-only, you could do

indexA :: (Applicative m, Array a e, Ix i) => a i e -> i -> m e
indexA a e = runCont (indexM a e) pure

to pass it to an Applicative.

On Tue, Aug 13, 2019 at 12:47 PM Edward Kmett <[hidden email]> wrote:

>
> I'd for some reason assumed that vector's indexM actually combined values for the Unboxed case, but it looks like _it_ should be generalized to Applicative, too.
>
> -Edwrd
>
> On Tue, Aug 13, 2019 at 10:33 AM Zemyla <[hidden email]> wrote:
>>
>> Well, the reason I say Applicative is because the only method from
>> Monad which is used is return, which is the same as pure in
>> Applicative. I'm preparing for when the "Monad of no return" proposal
>> gets implemented.
>>
>> On Tue, Aug 13, 2019 at 11:29 AM Edward Kmett <[hidden email]> wrote:
>> >
>> > I'm pretty strongly +1 on this, assuming someone is willing to chase down all the implementation issues, as the current API doesn't really allow for efficient usage.
>> >
>> > I'm not sure that Applicative is strong enough to give the desired behavior, though.
>> >
>> > e.g. to write a strict fmap (<$!>) you need Monad.
>> >
>> > -Edward
>> >
>> > On Tue, Aug 13, 2019 at 9:24 AM Zemyla <[hidden email]> wrote:
>> >>
>> >> This is an issue I originally proposed on GHC Trac, but I'm posting it
>> >> here because (I think) the Data.Array package is under the purview of
>> >> the Libraries committee.
>> >>
>> >> The vector package has indexM and its cousins so that a user can be
>> >> strict in the array without necessarily being strict in the value
>> >> retrieved from that array. Arrays don't have that sort of thing,
>> >> meaning that anything you do that takes an array will necessarily
>> >> leave references to the array unless you force the whole thing, and
>> >> that's not only inefficient, it's untenable for general libraries.
>> >>
>> >> What I'm thinking is that the IArray class should have a function like
>> >>
>> >> unsafeAtM :: (Array a e, Ix i, Applicative m) => a i e -> Int -> m e
>> >>
>> >> For compatibility with older code that wouldn't necessarily define
>> >> this but would define unsafeAt, we'd have the default implementation
>> >>
>> >> unsafeAtM a !n = pure (unsafeAt a n)
>> >>
>> >> Also, you could have unsafeAt defined in terms of unsafeAtM, so the
>> >> minimal implementation could require only one of them:
>> >>
>> >> unsafeAt = (coerce :: (a i e -> Int -> Identity e) -> a i e -> Int ->
>> >> e) unsafeAtM
>> >>
>> >> Also, (!?) would be a "safe" indexing tool for arrays, which would
>> >> incidentally also force the array without forcing the value inside.
>> >> You would have
>> >>
>> >> (!?) :: (Array a e, Ix i) => a i e -> i -> Maybe e
>> >> (!?) a e = case bounds a of
>> >>   p@(l, u) -> case inRange p e of
>> >>     True -> unsafeAtM arr $ unsafeIndex p e
>> >>     False -> Nothing
>> >> _______________________________________________
>> >> 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