Declaring a type class for multiplying a matrix of N-by-N elements and a column vector of an N-element

Question

In Haskell, if you have a "family" of types (say, matrices of N-on-N-elements, for some N values) and a parallel family of "related" types (say, N-element vectors, for the same N values) and an operation that requires one specific type from each family (for example, multiplying the N-by-N-element matrix and the N-element column vector), is it then possible to declare the type a class for this operation?

In this specific example, I assume that it will look something like this:

class MatrixNxN m where --| Multiplication of two N-by-N-element matrices mmul :: Num a => ma -> ma -> ma --| Multiplication of an N-by-N-element matrix and an N-element column vector vmul :: Num a => ma -> va -> va 

I do not know how to restrict type v . Is it possible to do something like this?

Please note that I welcome both answers to the general question about declaring a type class from several related types, as well as the answers to the specific question about declaring a type class to multiply matrix vectors. In my particular case, there is only a small, well-known set of N values ​​(2, 3, and 4), but I'm usually interested in understanding what can be encoded in a system like Haskell.

EDIT: I implemented this using MultiParamTypeClasses and FunctionalDependencies , as suggested by Gabriel Gonzalez and Mflamer below. This is what the relevant bits of my implementation looked like this:

 class MatrixVectorMultiplication mv | m -> v, v -> m where vmul :: Num a => ma -> va -> va data Matrix3x3 a = ... data Vector3 a = ... instance MatrixVectorMultiplication Matrix3x3 Vector3 where vmul = ... 

This is a signature of type vmul , in itself and partially applied:

 vmul :: (Num a, MatrixVectorMultiplication mv) => ma -> va -> va (`vmul` v) :: Matrix3x3 Integer -> Vector3 Integer (m `vmul`) :: Vector3 Integer -> Vector3 Integer 

I find it very elegant. Thanks for answers!:)

Answer 1

This is a very small variation of the MFlamer answer, which also makes m dependent on v :

 {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} class MatrixNxN mv | m -> v, v -> m where mmul :: Num a => ma -> ma -> ma vmul :: Num a => ma -> va -> va 

Thus, if you do:

 (`vmul` someVector) 

... then the compiler can select the correct instance only based on someVector type.

A type family solution will not work for the same reason, mainly because if you declare a constructor of type v as a function of a type of constructor of type m , this type function is not necessarily 1-to-1, so the compiler cannot deduce m from v . This is why people say that functional dependencies are more powerful than type families.

Answer 2

Please note that the dimension of the matrix / vector can be encoded using digits of type type, which allow instead of general encodings Matrix3x3 , Matrix4x4 , etc. more general definitions of class MatrixNum (n :: Nat) , and also to prevent re-multiplication of the compilation type of incompatible objects, In GHC 7.4. * It can be defined as follows.

 {-# LANGUAGE TypeFamilies, DataKinds, FlexibleInstances #-} data Nat = Zero | Succ Nat class MatrixNum (n :: Nat) where type Matrix n :: * -> * type Vector n :: * -> * mmul :: Num a => Matrix na -> Matrix na -> Matrix na vmul :: Num a => Matrix na -> Vector na -> Vector na newtype ListMatrix (n :: Nat) a = ListMatrix [[a]] deriving Show newtype ListVector (n :: Nat) a = ListVector [a] deriving Show instance MatrixNum n where type Matrix n = ListMatrix n type Vector n = ListVector n mmul (ListMatrix xss) (ListMatrix yss) = ListMatrix $ error "Not implemented" vmul (ListMatrix xss) (ListVector ys) = ListVector $ error "Not implemented" 

This is even better in GHC 7.6. *, which now supports advanced level literals , so you can abandon the above Nat definitions and use Nat from GHC.TypeLits and use a numeric literal in types to indicate the sizes of your objects:

 m1 :: ListMatrix 3 Int m1 = ListMatrix [[1,2,3],[4,5,6],[7,8,9]] v1 :: ListVector 3 Int v1 = ListVector [1,2,3] v2 = m1 `vmul` v1 -- has type ListVector 3 Int 

Answer 3

Here's how I did it using MultiParamTypeClasses, as was also suggested in the answers above. You also need to use the FunctionalDependencies extension, since both types are not used in every function of the class. Someone else will probably provide a more complete answer, but I have been using this template recently, so I thought this might help.

 {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} module Test where class MatrixNxN mv | m -> v where mmul :: Num a => ma -> ma -> ma vmul :: Num a => ma -> va -> va 

Answer 4

I assume that it is also possible to implement using class classes. To avoid circular functional dependencies, we declare that the types of vectors and matrices depend on the scalar type. Although scalars also require newtype , as well as corresponding vectors and matrices, it also has some advantages. In particular, we do not need to hold the Num a constraint when declaring mmul and vmul . We can leave it to the implementation example, what restrictions they impose on their scalar values.

 {-# LANGUAGE TypeFamilies #-} class MatrixNxN a where data Matrix a :: * data Vector a :: * -- | Multiplication of two N-by-N-element matrices mmul :: Matrix a -> Matrix a -> Matrix a -- | Multiplication of an N-by-N-element matrix -- and an N-element column vector vmul :: Matrix a -> Vector a -> Vector a -- List matrices on any kind of numbers: newtype ListScalar a = ListScalar a instance Num a => MatrixNxN (ListScalar a) where newtype Matrix (ListScalar a) = ListMatrix [[a]] newtype Vector (ListScalar a) = ListVector [a] vmul (ListMatrix mss) (ListVector vs) = ... mmul (ListMatrix m1ss) (ListMatrix m2ss) = ... -- We can have matrices that have no `Num` instance for -- their scalars, like Z2 implemented as `Bool`: newtype ListBool = ListBool Bool instance MatrixNxN ListBool where newtype Matrix ListBool = ListBoolMatrix [[Bool]] newtype Vector ListBool = ListBoolVector [Bool] vmul (ListBoolMatrix mss) (ListBoolVector vs) = ... mmul (ListBoolMatrix m1ss) (ListBoolMatrix m2ss) = ...