Deriving of unboxed vector for newtypes

[Shimuuar]

Problem is very simple. Newtype deriving doesn't work since roles were introduced to GHC.

{-# LANGUAGE DerivingStrategies         #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# LANGUAGE TypeFamilies               #-}
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as MU
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
newtype X = X Int

newtype instance U.Vector     X = V_X (U.Vector Int)
newtype instance MU.MVector s X = M_X (MU.MVector s Int)

deriving newtype instance G.Vector   U.Vector   X
deriving newtype instance GM.MVector MU.MVector X 

So this simple program fails with:

    • Couldn't match representation of type ‘m1 (MU.MVector
                                                   (PrimState m1) Int)’
                               with that of ‘m1 (MU.MVector
                                                   (PrimState m1) X)’
        arising from a use of ‘GHC.Prim.coerce’
    ...

Reason for that are very obvious. Methods of type class has type ∀m. PrimMonad m => ... -> m a and GHC can't coerce m Int to m X because it can't assume that Int has representational/phantom role.

This problem could be fixed by changing ∀m. PrimMonad ⇒ m type parameter to ∀s. ST s. Since m only appears in positive positions both approaches are equivalent and every instance that could be written in one style could be written in another.

This is of course breaking change but breakage should be relatively limited. Type class methods are not meant to be used directly and custom instances should continue to compile

[Bodigrim]

What would happen to mutable vectors, manipulated in IO monad, under this proposal?

[Shimuuar]

Do you mean ones that use IO in implementation (Storable)? I think nothing. They need to use unsafePrimToPrim anyway. It will work just fine for converting to ST.

User facing API shouldn't change at all. D.V.Generic.Mutable should continue to use PrimMonad

[Bodigrim]

Are you proposing this?

class MVector v a where ...
  basicClear :: v s a -> ST s ()

clear :: (PrimMonad m, MVector v a) => v (PrimState m) a -> m ()

[Shimuuar]

Yes. Exactly this.

[lehins]

This looks legit to me.

[Bodigrim]

And what would be the definition of clear?

[Shimuuar]

clear :: (PrimMonad m, MVector v a) => v (PrimState m) a -> m ()
clear = basicClear
-- vvv
clear = primToPrim . basicClear

[Bodigrim]

Got it. Agreed, great idea.

I quickly grepped GitHub, seems that folks mostly follow the recommendation do not use basic* functions, so the amount of breakage should be tolerable.

[lehins]

Here is an alternative approach for easy creation of Unbox instances I've been doing quite successfully for some time. Seems relevant to the ticket, so I'd like to share it:

Create a class (which could I think be simply added to Unbox class):

class Unbox (Components e) => MyUnbox e where
  type Components e :: Type
  toComponents :: e -> Components  e
  fromComponents :: Components e -> e

Here is an example in Color: https://github.com/lehins/Color/blob/c39b5fc99c6e0ccef3a5216fcb9fd162aa1186d1/Color/src/Graphics/Color/Model/Internal.hs#L78-L84

Default implementation with Coercible can further simplify the process for new types, but that is not terribly important.

Then we just create all the boiler plate only once and further instances become so much simpler. An example of an instance say for Complex a:

instance Unbox a => MyComplex (Complex a) where
  type Components (Complex a) = (a, a)
  toComponents (r :+ i) = (r, i)
  fromComponents (r, i) = r :+ i

And that all it takes to unbox a type with this approach and it looks like ghc is smart enough to optimize it all away.

The full example from Color: https://github.com/lehins/Color/blob/c39b5fc99c6e0ccef3a5216fcb9fd162aa1186d1/Color/src/Graphics/Color/Model/Internal.hs#L162-L213

@Shimuuar and @Bodigrim let me know what are you thoughts on this.

[Shimuuar]

But you still need to write down all this 50 lines of MVector/Vector instances, right? I think any practically useful deriving mechanism must not require write those by hand. Programmers will do that only is they absolutely have to.Effectively it limits unboxed vector to types derived in libraries.

But I think you basically described iso-deriving's approach. Say one wants to define Unbox instance for data Foo = Foo Int Double. So he define isomorphism between Foo and (Double,Int) by type class and uses DerivingVia to transform instance for tuple into instance for Foo.

Since DerivingVia uses same mechanism as GND it only strengthens case for proposed change.

[lehins]

But you still need to write down all this 50 lines of MVector/Vector instances, right

That's the point, if MyUnbox becomes the new Unbox then you don't need to write anything besides the Unbox instance. In the libraries where I used it, it works because of a common type family, but it can work for any type that can be made isomorphic to an already unboxed type.

[Shimuuar]

I see. But changing definition of Unbox is much more invasive change all existing Unbox instances. There're very few experiments on how SoA could be encoded in haskell. We have Unbox that works but probably could be improved O(1) zips/unzips for product for example.

But this is to a large degree independent from this proposal. It aim to make it possible to use GDN DerivingVia for MVector/Vector type classes. Mostly for benefit of unboxed vectors but there could be other uses.

[Bodigrim]

I'm not fully on board with changing the existing Unbox class, which sounds quite disruptive. Anyways, I agree with @Shimuuar, that this is an orthogonal proposal.

[lehins]

No worries, I just threw it there as an alternative idea that worked well for me. I am by no means suggesting we should apply it. I do prefer not to break users code either ;)

[Shimuuar]

I accidentally stumbled on GHC issue about deriving for vectors: https://gitlab.haskell.org/ghc/ghc/-/issues/9112

[lehins]

If I understand that ghc ticket correctly it is suggesting a wrong thing. We should ask ourselves a question: is it correct to have representational or especially phantom role for unboxed vector. Both Storable and Primitive vectors have been switched to nominal for good reasons:

vector/Data/Vector/Primitive/Mutable.hs

Line 82 in 6b8fcdf

type role MVector nominal nominal

and

vector/Data/Vector/Storable/Mutable.hs

Line 100 in c7858a7

type role MVector nominal nominal

I think the same reasoning applies to unboxed vectors as well. Nothing prevents me from creating two instances for two equivalent newtypes which implement unboxing differently. If representational type families were a thing it would allow me to cast between incompatible unboxed vector representations.

[Shimuuar]

I just wrote down related issue on GHC bug tracker.

I however was under implression that GHC can perform coercions when corresponding constructors are in scope.

[lehins]

@Shimuuar You are right, this will compile just fine because all newtype constructors are in scope

newtype Foo = Foo Int

newtype Bar = Bar Int

newtype instance VU.MVector s Foo = MV_Foo Foo
newtype instance VU.MVector s Bar = MV_Bar Bar

λ> foo = MV_Foo (Foo 5) :: VU.MVector () Foo
λ> coerce foo :: VU.MVector () Bar
coerce foo :: VU.MVector () Bar :: VU.MVector () Bar

But this one will not, because they aren't declared as newtypes:

data instance VU.MVector s Foo = MV_Foo Foo
data instance VU.MVector s Bar = MV_Bar Bar

Note that in the ghc ticket it is declared as data:

data instance MVector s Int -- implementation not important

The whole point about roles is that I can implement the way values of Foo type are written into memory in a completely different way the values of type Bar are with a custom instance of the MVector class.

Coercion is good for deriving, but for custom Storable, Prim and Unbox instances not so much.

Not quite sure what's the correct direction to go here. If we are to promote the same safety for unboxed as we are for storable and primitive we might want to hide the constructor for MVector here

vector/Data/Vector/Unboxed/Mutable.hs

Line 17 in 6b8fcdf

MVector(..), IOVector, STVector, Unbox,

just as it is done for Vector data families here:

vector/Data/Vector/Unboxed.hs

Line 40 in 6b8fcdf

Vector, MVector(..), Unbox,

This way if anyone needs access to these constructors for deriving as it is suggested in this ticket they will have to use the internal Data.Vector.Unboxed.Base module.

[Shimuuar]

Fixed by #335