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.

Answer 3

As OP wanted a more lightweight approach, I would use associated types.

class VecMath a b where
    type Res a b :: *
    (+++) :: a -> b -> Res a b

instance Num a => VecMath (a,a,a) (a,a,a) where
    type Res (a,a,a) (a,a,a) = (a,a,a)
    (x1,y1,z1) +++ (x2,y2,z2) = (x1+x2, y1+y2, z1+z2)

instance Num a => VecMath (a,a) (a,a,a) where
    type Res (a,a) (a,a,a) = (a,a,a)
    (x1,y1) +++ (x2,y2,z) = (x1+x2, y1+y2, z)

instance Num a => VecMath (a,a,a) (a,a) where
    type Res (a,a) (a,a,a) = (a,a,a)
    -- (+++) analog
instance Num a => VecMath (a,a) (a,a) where
    type Res (a,a) (a,a) = (a,a)
    -- ...

Res is a type function, here essentially resulting in the 'bigger' type of it's arguments. The advantage is that you still can work with plain old tuples, as if VecMath didn't exist. The dark side is the exponential explosion of instances you have to write, if you consider adding new types to the domain of Res. For more information see this.

Answer 4

Landei's and leftaroundabout's answers are good (thanks to you both), and I guess I should have realized that this wouldn't be as simple as I'd hoped. Trying to do either of the options I suggested makes for complex code, which woudn't be a problem in itself except that it seems the user code wouldn't be very pretty to look at either.

I think I've decided to go with tuples and stick with 3-dimension only vectors, simply because it seems more semantically correct than using lists. I'm ending up re-implenting map, zipWith, sum and others for triples, though. I want to stick with simplicity—I feel as though if I had a compelling argument to think of vectors as lists, then that solution would work better (provided I make sure I don't mix dimensions)… When I actually use the vectors, though, functions will take a 3d vector as an argument, not one of variable dimensions, and Num a => [a] can't enforce that.