How to make a fixed-length instance an applicative instance?

Question

I recently found out about a career and decided to try writing vectors.

{-# LANGUAGE DataKinds, GADTs, KindSignatures #-} module Vector where data Nat = Next Nat | Zero data Vector :: Nat -> * -> * where Construct :: t -> Vector nt -> Vector ('Next n) t Empty :: Vector 'Zero t instance Functor (Vector n) where fmap fa = case a of Construct xb -> Construct (fx) (fmap fb) Empty -> Empty 

So far, everything is working. But I ran into a problem while trying to make an instance of Vector Applicative .

 instance Applicative (Vector n) where a <*> b = case a of Construct fc -> case b of Construct xd -> Construct (fx) (c <*> d) Empty -> Empty pure x = _ 

I had no idea how to do this pure . I tried this:

 case n of Next _ -> Construct x (pure x) Zero -> Empty 

but the error received is Variable not in scope: n :: Nat for the first line and Couldn't match type n with 'Zero for the third line of this expression.

So, I used the following hack.

 class Applicative' n where ap' :: Vector n (t -> u) -> Vector nt -> Vector nu pure' :: t -> Vector nt instance Applicative' n => Applicative' ('Next n) where ap' (Construct fa) (Construct xb) = Construct (fx) (ap' ab) pure' x = Construct x (pure' x) instance Applicative' 'Zero where ap' Empty Empty = Empty pure' _ = Empty instance Applicative' n => Applicative (Vector n) where (<*>) = ap' pure = pure' 

He does his job, but it’s not very. It introduces the useless Applicative' class. And every time I want to use Applicative for Vector in any function, I have to provide an additional useless Applicative' n constraint that actually holds for any n .

What would be a better, cleaner way to do this?

Answer 1

You can do the same directly:

 instance Applicative (Vector Zero) where a <*> b = Empty pure x = Empty instance Applicative (Vector n) => Applicative (Vector (Next n)) where a <*> b = case a of Construct fc -> case b of Construct xd -> Construct (fx) (c <*> d) pure x = Construct x (pure x) 

How can I reason about this: for different types of a class, the code must be type aware. If you had multiple instances, different types would get a different implementation, and that would be easily resolved. But, if you try to do this with one non-recursive instance, it does not have type information at runtime, and the code, which is always the same, still has to decide which type to process. When you have input parameters, you can use GADT to provide you with type information. But for pure there are no input parameters. Therefore, you should have some context for the Applicative instance.

Answer 2

This (comment) that uses the singletons package.

Very rudely, Haskell does not allow us to map patterns to values ​​of type type, such as n in the code above. With singletons we can, by requiring and providing multiple instances of SingI here and there.

 {-# LANGUAGE GADTs , KindSignatures, DataKinds, TemplateHaskell, TypeFamilies, ScopedTypeVariables #-} {-# OPTIONS -Wall #-} import Data.Singletons.TH -- Autogenerate singletons for this type $(singletons [d| data Nat = Next Nat | Zero |]) -- as before data Vector :: Nat -> * -> * where Construct :: t -> Vector nt -> Vector ('Next n) t Empty :: Vector 'Zero t -- as before instance Functor (Vector n) where fmap _ Empty = Empty fmap f (Construct xb) = Construct (fx) (fmap fb) -- We now require n to carry its own SingI instance. -- This allows us to pattern match on n. instance SingI n => Applicative (Vector n) where Empty <*> Empty = Empty -- Here, we need to access the singleton on n, so that later on we -- can provide the SingI (n-1) instance we need for the recursive call. -- The withSingI allows us to use m :: SNat (n-1) to provide the instance. (Construct fc) <*> (Construct xd) = case sing :: SNat n of SNext m -> withSingI m $ Construct (fx) (c <*> d) -- Here, we can finally pattern match on n. -- As above, we need to provide the instance with withSingI -- to the recursive call. pure x = case sing :: SNat n of SZero -> Empty SNext m -> withSingI m $ Construct x (pure x) 

Using this will require providing an instance of SingI n for each use, which is a bit inconvenient, but not too much (IMO). The sad part is that <*> really does not need SingI n , since in principle it can double-check this from two vectors. However, pure does not have an input vector, so it can only match a pattern with a single tone provided.

As another alternative, similar to the source code, you can write

 instance Applicative (Vector Zero) where ... instance Applicative (Vector n) => Applicative (Vector (Next n)) where ... 

This is not completely equivalent and will require the addition of Applicative (Vector n) => contexts to all functions that will later be displayed where n unknown, but may be sufficient for many purposes.

Answer 3

Consider this addition to @chi to give an additional explanation of the singleton approach ...

I would advise you to read the Hashotism document if you have not already done so. In particular, in section 3.1 of this article, they consider this problem and use it as a motivational example for cases when implicit singleton parameters ( SingI response and NATTY class in the Hashokhism document) are necessary, and not just convenient.

As this applies to your code, the main problem is that pure requires a representation of the runtime of the vector that it should generate, and a variable of type n does not fit the count. The solution is to introduce a new GADT, "singleton", which provides run-time values ​​that correspond directly to the advanced types Next and Zero :

 data Natty (n :: Nat) where ZeroTy :: Natty Zero NextTy :: Natty n -> Natty (Next n) 

I tried to use roughly the same naming convention as paper: NATTY the same, and ZeroTy and NextTy correspond to Zy and Sy paper.

This explicit singleton is useful in itself. For example, see the definition of vchop in a document. In addition, we can easily write a pure variant that takes an explicit singleton to do its job:

 vcopies :: Natty n -> a -> Vector na vcopies ZeroTy _ = Empty vcopies (NextTy n) x = Construct x (vcopies nx) 

We cannot use this to define pure yet, though, since the signature pure is defined by a class of type Applicative , and we cannot compress the explicit singlet Natty n .

The solution is to introduce implicit singletones that allow us to get an explicit singleton when necessary, using the NATTY function in the context of the following class type:

 class NATTY n where natty :: Natty n instance NATTY Zero where natty = ZeroTy instance NATTY n => NATTY (Next n) where natty = NextTy natty 

Now, if we are in the context of Natty n , we can call vcopies natty to provide vcopies its explicit NATTY parameter, which allows us to write:

 instance NATTY n => Applicative (Vector n) where (<*>) = vapp pure = vcopies natty 

using the definitions of vcopies and NATTY above, and the definition of vapp below:

 vapp :: Vector n (a -> b) -> Vector na -> Vector nb vapp Empty Empty = Empty vapp (Construct fc) (Construct xd) = Construct (fx) (vapp cd) 

Pay attention to one oddity. We needed to introduce this helper function vapp for an unclear reason. The following non- NATTY matches your case definition and type:

 instance Applicative (Vector n) where Empty <*> Empty = Empty Construct fc <*> Construct xd = Construct (fx) (c <*> d) pure = error "Argh! No NATTY!" 

If we add a NATTY constraint to define pure :

 instance NATTY n => Applicative (Vector n) where Empty <*> Empty = Empty Construct fc <*> Construct xd = Construct (fx) (c <*> d) pure = vcopies natty 

the definition (<*>) no longer checks the type. The problem is that the Natty n restriction on the left side of the second case (<*>) does not imply an automatic restriction on NATTY n1 on the right side (where Next n ~ n1 ), so the GHC does not want to let us call (<*>) on the right parts. In this case, since the restriction is not actually required after using it for the first time, the helper function without the NATTY restriction, namely vapp , works around the problem.

@chi uses case matching on NATTY and the NATTY helper function as an alternative solution. Here, the equivalent code will use a helper function that turns an explicit singleton into an implicit NATTY context:

 withNATTY :: Natty n -> (NATTY n => a) -> a withNATTY ZeroTy a = a withNATTY (NextTy n) a = withNATTY na 

allows us to write:

 instance NATTY n => Applicative (Vector n) where Empty <*> Empty = Empty Construct fc <*> Construct xd = case (natty :: Natty n) of NextTy n -> withNATTY n $ Construct (fx) (c <*> d) pure x = case (natty :: Natty n) of ZeroTy -> Empty NextTy n -> Construct x (withNATTY n $ pure x) 

This will require ScopedTypeVariables and RankNTypes .

In any case, adhering to the auxiliary functions, the complete program is as follows:

 {-# LANGUAGE DataKinds, GADTs, KindSignatures #-} module Vector where data Nat = Next Nat | Zero data Vector :: Nat -> * -> * where Construct :: t -> Vector nt -> Vector ('Next n) t Empty :: Vector 'Zero t data Natty (n :: Nat) where ZeroTy :: Natty Zero NextTy :: Natty n -> Natty (Next n) class NATTY n where natty :: Natty n instance NATTY Zero where natty = ZeroTy instance NATTY n => NATTY (Next n) where natty = NextTy natty instance Functor (Vector n) where fmap fa = case a of Construct xb -> Construct (fx) (fmap fb) Empty -> Empty instance NATTY n => Applicative (Vector n) where (<*>) = vapp pure = vcopies natty vapp :: Vector n (a -> b) -> Vector na -> Vector nb vapp Empty Empty = Empty vapp (Construct fc) (Construct xd) = Construct (fx) (vapp cd) vcopies :: Natty n -> a -> Vector na vcopies ZeroTy _ = Empty vcopies (NextTy n) x = Construct x (vcopies nx) 

Compliance with the singletons library is as follows:

 $(singletons [d| data Nat = Next Nat | Zero |]) 

automatically generates singletones (with SZero and SNat instead of ZeroTy and NATTY , and with SNat type instead of NATTY ) and an implicit single-point class (called SingI instead of from NATTY and using the sing function instead of NATTY ), giving the full program:

 {-# LANGUAGE DataKinds, GADTs, KindSignatures, TemplateHaskell, TypeFamilies #-} module Vector where import Data.Singletons import Data.Singletons.TH $(singletons [d| data Nat = Next Nat | Zero |]) data Vector :: Nat -> * -> * where Construct :: t -> Vector nt -> Vector ('Next n) t Empty :: Vector 'Zero t instance Functor (Vector n) where fmap fa = case a of Construct xb -> Construct (fx) (fmap fb) Empty -> Empty instance SingI n => Applicative (Vector n) where (<*>) = vapp pure = vcopies sing vapp :: Vector n (a -> b) -> Vector na -> Vector nb vapp Empty Empty = Empty vapp (Construct fc) (Construct xd) = Construct (fx) (vapp cd) vcopies :: SNat n -> a -> Vector na vcopies SZero _ = Empty vcopies (SNext n) x = Construct x (vcopies nx) 

For more on what the singletons library does and how it is built, I would suggest reading the Introduction to Singletons .

Answer 4

Several other answers have implemented the Natty or SNat to implement pure . Indeed, the presence of this type significantly reduces the need for one-time classes. However, a potential drawback of the traditional Natty / SNat GADT is that your program will actually create a view and then use it even if Nat known at compile time. Usually this does not happen with the helper class approach. You can get around this using a different view.

I will use these names:

 data Nat = Z | S Nat 

Suppose we define ordinary

 data Natty n where Zy :: Natty 'Z Sy :: Natty n -> Natty ( n) 

We can write its rectifier (induction principle), thus:

 natty :: p 'Z -> (forall k. pk -> p ( k)) -> Natty n -> pn natty z _ Zy = z natty zs (Sy n) = s (natty zsn) 

For our purpose, we really do not need Natty ; we need only his principle of induction! So let's define a different version. I assume that there is a correct name for this encoding, but I have no idea what it could be.

 newtype NatC n = NatC { unNatC :: forall p. p 'Z -- base case -> (forall k. pk -> p ( k)) -- inductive step -> pn } 

This is isomorphic to Natty :

 nattyToNatC :: Natty n -> NatC n nattyToNatC n = NatC (\zs -> natty zsn) natCToNatty :: NatC n -> Natty n natCToNatty (NatC f) = f Zy Sy 

Now we can write a class for Nat , we know how to fix it:

 class KnownC n where knownC :: NatC n instance KnownC 'Z where knownC = NatC $ \z _ -> z instance KnownC n => KnownC ( n) where knownC = NatC $ \zs -> s $ unNatC knownC zs 

Now here is the vector type (I renamed things according to my taste):

 infixr 4 :< data Vec :: Nat -> * -> * where (:<) :: t -> Vec nt -> Vec ( n) t Nil :: Vec 'Z t 

Since the Vec length parameter is not the last, we will have to flip it for use with NatC :

 newtype Flip fan = {unFlip :: fna} induct2 :: f 'Z a -> (forall k. fka -> f ( k) a) -> NatC n -> fna induct2 zsn = unFlip $ unNatC n (Flip z) (\(Flip r) -> Flip (sr)) replC :: NatC n -> a -> Vec na replC na = induct2 Nil (a :<) n instance KnownC n => Applicative (Vec n) where pure = replC knownC (<*>) = ... 

Now, if the length of the vector is known at compile time, the pure vector will be built directly, without an intermediate structure.