Я играю с векторами и матрицами, где размер кодируется в их типе, используя новое расширение DataKinds
. В основном это происходит следующим образом:
data Nat = Zero | Succ Nat
data Vector :: Nat -> * -> * where
VNil :: Vector Zero a
VCons :: a -> Vector n a -> Vector (Succ n) a
Теперь нам нужны типичные экземпляры типа Functor
и Applicative
. Functor
легко:
instance Functor (Vector n) where
fmap f VNil = VNil
fmap f (VCons a v) = VCons (f a) (fmap f v)
Но с экземпляром Applicative
возникает проблема: мы не знаем, какой тип должен возвращаться в чистом виде. Однако мы можем определить экземпляр индуктивно по размеру вектора:
instance Applicative (Vector Zero) where
pure = const VNil
VNil <*> VNil = VNil
instance Applicative (Vector n) => Applicative (Vector (Succ n)) where
pure a = VCons a (pure a)
VCons f fv <*> VCons a v = VCons (f a) (fv <*> v)
Однако, хотя этот экземпляр применяется ко всем векторам, средство проверки типов не знает этого, поэтому мы должны нести ограничение Applicative
каждый раз, когда мы используем экземпляр.
Теперь, если это применимо только к экземпляру Applicative
, это не будет проблемой, но оказывается, что трюк рекурсивных деклараций экземпляров необходим при программировании с такими типами. Например, если мы определяем матрицу как вектор векторов строк с использованием библиотеки TypeCompose,
type Matrix nx ny a = (Vector nx :. Vector ny) a
мы должны определить класс типа и добавить рекурсивные объявления экземпляра для реализации как транспонирования, так и матричного умножения. Это приводит к огромному распространению ограничений, которые нам приходится выполнять каждый раз, когда мы используем код, даже если экземпляры действительно применяются ко всем векторам и матрицам (что делает ограничения бесполезными).
Есть ли способ избежать необходимости переносить все эти ограничения? Можно ли расширить проверку типа, чтобы он мог обнаружить такие индуктивные конструкции?