3

Recently I tried implementing linear maps class for 2d vectors. It was fine until I tried to change the base type (base-ring) of vectors to a generic one. I have the following type for vectors:

data Vector a = V a a

(As far as I know, I can't or shouldn't specify what a is.)

And I want to have a class (not a type) for linear maps. The reason behind it: I want to have a very specific linear maps, say rotations, that depends on a different set of parameters (and may even not depend on any params, for example x-reflection have no params), but they all have one purpose -- apply to vector (that is why I call it a class).

I tried defining the following class

class LinearMap m where
  apply :: m -> Vector a -> Vector a

And say I want two instances

data Rotation a = Rot a

instance LinearMap (Rotation a) where
  Rot phi `apply` V x y = V (c * x - s * y) (s * x + c * y)
    where
      (c, s) = (cos phi, sin phi)

but it gives me an error, because I expected a type

apply :: Rotation a -> Vector a -> Vector a

while compiler expected

apply :: Rotation a -> Vector b -> Vector b

And even if type binding is not a problem as in the following

data Reflection = XRefl | YRefl

instance LinearMap Reflection where
  XRefl `apply` V x y = V (-x) y
  YRefl `apply` V x y = V x (-y)

I get an error, because now x and y must be instances of Num, but I don't see where I should write the instance.

An easy option would be to edit the LinearMap class and add something like

class LinearMap m where
  apply :: Num a => m -> Vector a -> Vector a

but it is not what I was trying to do (I hope you see my motivation), and it doesn't solve the Rotation problem, either.

UPD: Here is what I came up with (not quite happy)

class LinearMap m a | m -> a where
  apply :: m -> Vector a -> Vector a

Now Rotation is fine:

instance Floating a => LinearMap (Rotation a) a where
  -- apply = ...

But Reflection needs an update

data Reflection a = XRefl | YRefl

so I can define an instance

instance Num a => LinearMap (Reflection a) a where
  -- apply = ...

Because a depends on m as in LinearMap class definition. But now I'm not happy that Reflection depends on something (it shouldn't right?).

2
  • Do you really need the functional dependency? Nov 15 at 12:03
  • The vector space is defined on top of a base field (or if you prefer a module is defined on top of a base ring) and those always have additive inverse. But in Haskell, the unary minus function is restricted to Num, so if you use it, your base ring/field is automatically restricted to Num. Nov 15 at 12:32

2 Answers 2

1

Approach 1: using type families and constraints

This is probably not the most elegant approach, yet... one way to do it is to add in the class a dependent constraint on the a type you use in Vector a.

Here's the class:

{-# LANGUAGE TypeFamilies #-}

import Data.Kind

data Vector a = V a a

class LinearMap m where
  type CMap m (a :: Type) :: Constraint
  apply :: CMap m a => m -> Vector a -> Vector a

Here, CMap m a is a constraint defining what's needed for apply to work.

data Rotation a = Rot a

instance LinearMap (Rotation a) where
  type CMap (Rotation a) a' = (Floating a, a ~ a')
  Rot phi `apply` V x y = V (c * x - s * y) (s * x + c * y)
    where
      (c, s) = (cos phi, sin phi)

For Rotation a, we need a to be the same a in Vector a, so we require the type equality a ~ a'. We also require Floating so that cos can be used.

data Reflection = XRefl | YRefl

instance LinearMap Reflection where
  type CMap Reflection a' = (Num a')
  XRefl `apply` V x y = V (-x) y
  YRefl `apply` V x y = V x (-y)

For Rotation, we only require Num. Any numeric a' is allowed.

Approach 2: just remove the fundep (?)

I now wonder if it would be better to use both arguments in the type class, as in LinearMap m a and move the constraints to the instances. We just avoid the fundep m -> a.

class LinearMap m a where
  apply :: m -> Vector a -> Vector a

data Rotation a = Rot a

instance Floating a => LinearMap (Rotation a) a where
  Rot phi `apply` V x y = V (c * x - s * y) (s * x + c * y)
    where
      (c, s) = (cos phi, sin phi)

data Reflection = XRefl | YRefl

instance Num a => LinearMap Reflection a where
  XRefl `apply` V x y = V (-x) y
  YRefl `apply` V x y = V x (-y)

Is there anything wrong with this simpler approach I missed? We don't get a inferred from Rotation a during type inference since we lack the fundep. Is that a real issue?

1

As far as I know, I can't or shouldn't specify what a is

You absolutely can specify what a is. Whether you should is a different matter. Most of the Haskell community uses the linear package, which does indeed leave the scalar type fully polymorphic. IMO this makes little sense, because only very few types make sense in practice as scalars, and it is not sensible for vector types to be fully parametric functors (because conceptually, the choice of basis is arbitrary but fmapping a nonlinear function destroys the symmetry).

So what I advocate for is actually to use monomorphic vector types, or at least treat them as monomorphic:

data Vector2D a = Vector2D a a

type ℝ² = Vector2D Double

Likewise, a given linear-map instance will be specific to one concrete vector type. There are two ways of expressing this:

  • With an associated type family. In fact you maybe want two, for the domain and codomain:

     class LinearMapTF m where
       type LinMapDomain m :: Type
       type LinMapCodomain m :: Type
       apply :: m -> LinMapDomain m -> LinMapCodomain m
    

    This is IMO the clearest, but it means every linearmap-type will have one particular domain and codomain, and in particular you can't have Reflection act on different-typed domains. It's the same issue you get with your functional dependency.

  • As a multi-param typeclass. You already had this in the original, but I would remove the scalar type from the interface in favour of abstract vector spaces, and also remove the functional dependency if you want to allow some kinds of linear maps to act on different spaces. Sticking to the specific case of endomorphisms, it's simply

     class LinearMapMP m v where
       apply :: m -> v -> v
    

Despite the treatment of vector spaces as non-parametric entities, you can in both cases perfectly well swap out scalar types. Rotation can still

data Rotation a = Rot a

instance LinearMapTF (Rotation a) where
  type LinMapDomain (Rotation a) = Vector2D a
  type LinMapCodomain (Rotation a) = Vector2D a
  Rot phi `apply` V x y = ...

instance a~b => LinearMapMP (Rotation a) (Vector2D b) where
  Rot phi `apply` V x y = ...

In this example, both approaches are basically equivalent. In case of reflection, they're different:

data ReflectionFxd a = XRefl | YRefl

instance LinearMapTF (ReflectionFxd a) where
  type LinMapDomain (ReflectionFxd a) = Vector2D a
  type LinMapCodomain (ReflectionFxd a) = Vector2D a
  apply = ...

data ReflectionArb = XRefl | YRefl

instance LinearMapMP ReflectionArb (Vector2D a) where
  apply = ...

Side note: none of what you're asking about really has to do with linear mappings. Your examples are actually specific cases of groups acting on manifolds. It makes a lot of sense to use rotations on spheres, for example. This is another motivation not to use scalar-parametric vector types but instead abstract types representing topological spaces. I also have a package going in that direction.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.