Haskell: Between a list and a tuple

Question

I want a function +++ that adds two mathematical vectors.

I could implement vectors as [x, y, z] and use:

(+++) :: (Num a) => [a] -> [a] -> [a]
(+++) = zipWith (+)

And thus accomodate any n-dimensional vector (so this would work for [x, y] too).

Or I could implement vectors as (x, y, z) and use:

type Triple a = (a, a, a)

merge :: (a -> b -> c) -> Triple a -> Triple b -> Triple c
merge f (a, b, c) (x, y, z) = (f a x, f b y, f c z)

(+++) :: (Num a) => Triple a -> Triple a -> Triple a
(+++) = merge (+)

Of course this is slightly more complex but it when I implement all the other vector functions, that is irrelevant (50 lines instead of 40).

The problem with the list approach is that I can add a 2D vector with a 3D vector. In that case, zipWith would simply chop off the 3D vector's z component. While that might make sense (more likely it should expand the 2D vector to [x, y, 0]), for other functions I'm thinking it could be problematic to have either happen silently. The problem with the tuple approach is it limits the vector to 3 components.

Intuitively, I would think that it would make more sense to represent vectors as (x, y, z), since a mathematical vector has a fixed number of components and it doesn't really make sense to cons (prepend) a component to a vector.

On the other hand, although it's very unlikely that I will need anything other than 3D vectors, it doesn't seem quite right to limit it to that.

I guess what I want is functions that take two lists of equal length, or better, functions that operate on tuples of arbitrary size.

Any suggestions, in terms of practicality, scalability, elegance, etc.?

Answer 1

You can use type level programming. First we need to make every natural number a separate type. Following Peano's definition of the natural numbers, Z is 0, and S x is x + 1

data Z = Z
data S a = S a

class Nat a
instance Nat Z
instance (Nat a) => Nat (S a)

Now we can use a type Vec to simply wrap a list, but to keep track of its size by using Nat. For this, we use the smart constructors nil and <:> (so you shouldn't export the data constructor Vec from your module)

data Vec a = Vec a [Int]

nil = Vec Z []

infixr 5 <:>
x <:> (Vec n xs) = Vec (S n) (x:xs)

Now we can define an add function, which requires that two vectors have the same Nat:

add :: Nat a => Vec a -> Vec a -> Vec a
add (Vec n xs) (Vec _ ys) = Vec n (zipWith (+) xs ys) 

Now you have a vector type with length information:

toList (Vec _ xs) = xs
main = print $ toList $ add (3 <:> 4 <:> 2 <:> nil) (10 <:> 12 <:> 0 <:> nil) 

Of course having vectors with different length here will cause a compile error.

This is the easy to understand version, there are shorter, more efficient and/or more convenient solutions.

Answer 2

The easiest way is to put the +++ operator in a type class, and make the various tuple sizes instances:

{-# LANGUAGE FlexibleInstances #-}   -- needed to make tuples type class instances

class Additive v where
  (+++) :: v -> v -> v

instance (Num a) => Additive (a,a) where
  (x,y) +++ (ξ,υ)  =  (x+ξ, y+υ)
instance (Num a) => Additive (a,a,a) where
  (x,y,z) +++ (ξ,υ,ζ)  =  (x+ξ, y+υ, z+ζ)
...

This way, variable-length tuples may be added but it will be ensured at compile-time that both sides always have the same length.

---

Generalizing this to use a function like your merge in the actual type class is also possible: in this case, you need to specify the class instance as a type constructor (like the list monad).

class Mergable q where
  merge :: (a->b->c) -> q a -> q b -> q c

instance Mergable Triple where
  merge f (x,y,z) (ξ,υ,ζ) = (f x ξ, f y υ, f z ζ)

and then simply

(+++) :: (Mergable q, Num a) => q a -> q b -> q c
+++ = merge (+)

Unfortunately, this does not quite work, because type synonyms may not be partially evaluated. You need to make Triple a newtype instead, like

newtype Triple a = Triple(a,a,a)

and then

instance Mergable Triple where
  merge f (Triple(x,y,z)) (Triple((ξ,υ,ζ)) = Triple(f x ξ, f y υ, f z ζ)

which is of course not quite as nice to look at.