Типоразмерное умножение матрицы

Ответ 1

Существует несколько пакетов, которые реализуют это:

• http://hackage.haskell.org/package/hmatrix-static
• http://hackage.haskell.org/packages/archive/repa-algorithms/2.2.0.1/doc/html/Data-Array-Repa-Algorithms-Matrix.html
• http://hackage.haskell.org/packages/archive/blas/0.7.6/doc/html/Data-Matrix-Dense.html#t:Matrix
• http://hackage.haskell.org/package/Vec

В документах Repa, в частности, есть действительно хорошее обсуждение пространства дизайна и сделанных выборов: http://repa.ouroborus.net/

Исторический интерес представляет McBride "Faking It" от 2001 года, который описывает сильно типизированные векторы. Методы, которые он использует, довольно похожи на используемые в вышеупомянутых пакетах. Они, очевидно, были известны в кругах, выполняющих навязчивое программирование, но мое впечатление заключается в том, что бумага "Faking It" является одним из ранних случаев, когда они использовались в Haskell. Олег 2005 В статье Monad Reader, посвященной параметрам с номером-параметризацией, есть и хорошее обсуждение истории этих методов.

Ответ 2

Вы можете использовать натуральные числа на уровне типа для кодирования измерений. Тип матрицы становится

-- x, y: Dimensions
data Matrix x y n = ...

и вам нужно определить два дополнительных ADT и класс TLN (Type Level Naturals):

data Zero
data Succ a
class    TLN a                 where fromTLN :: a -> Int
instance TLN Zero              where fromTLN = const Zero
instance TLN a => TLN (Succ a) where fromTLN = 1 + fromTLN (undefined :: a)

Тип вашей функции довольно прост:

matrixMult :: (TLN x, TLN y, TLN t, Num a) =>
  Matrix x t a -> Matrix t y a -> Matrix x y a

Вы можете извлечь размер массива, создав undefined соответствующего типа вместе с расширением ScopedTypeVariables.

Этот код полностью непроверен, и GHC может запретить компиляцию. Это всего лишь эскиз о том, как это можно сделать.

Ссылка

• http://www.haskell.org/haskellwiki/Type_arithmetic

Ответ 3

Извините, я не могу сопротивляться приклеиванию чего-то, что я взбивал много веков назад. Это было до семейств типов, поэтому я использовал fundeps для арифметики. Я подтвердил, что это все еще работает на GHC 7.

{-# LANGUAGE EmptyDataDecls,
  ScopedTypeVariables,
  MultiParamTypeClasses,
  FunctionalDependencies,
  FlexibleContexts,
  FlexibleInstances,
  UndecidableInstances #-}

import System.IO


-- Peano type numerals

data Z
data S a

type One = S Z
type Two = S One
type Three = S Two

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

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

class Pred a b | a -> b
instance Pred (S a) a


-- Vector type

newtype Vector n k = Vector {unVector :: [k]}
    deriving (Read, Show, Eq)

empty :: Vector Z k
empty = Vector []

vtail :: Pred s' s => Vector s' k -> Vector s k
vtail (Vector (a:as)) = Vector as
vhead :: Positive s => Vector s k -> k
vhead (Vector (a:as)) = a

liftV :: (a->b) -> Vector s a -> Vector s b
liftV f = Vector . map f . unVector

type Matrix m n k = Vector m (Vector n k)

infixr 6 |>
(|>) :: k -> Vector s k -> Vector (S s) k
k |> v = Vector . (k:) . unVector $ v


-- Arithmetic

instance (Num k) => Num (Vector n k) where
    (+) (Vector v) (Vector u) = Vector $ zipWith (+) v u
    (*) (Vector v) (Vector u) = Vector $ zipWith (*) v u
    abs = liftV abs
    signum = liftV signum

dot :: Num k => Vector n k -> Vector n k -> k
dot u v = sum . unVector $ v*u

class Transpose n m where
    transpose :: Matrix n m k -> Matrix m n k

instance (Transpose m a, Nat a, Nat m) => Transpose m (S a) where
    transpose v = liftV vhead v |>
                  transpose (liftV vtail v)

instance Transpose m Z where
    transpose v = empty

multiply :: (Nat n, Nat m, Nat n', Num k, Transpose m n) =>
            Matrix m n k -> Matrix n' m k -> Matrix n n' k
multiply a (Vector bs) = Vector [Vector [a `dot` b | a <- as] | b <- bs]
    where (Vector as) = transpose a

printMatrix :: Show k => Matrix m n k -> IO ()
printMatrix = mapM_ (putStrLn) . map (show.unVector) . unVector


-- Examples

m :: Matrix Three Three Integer
m =    (1 |> 2 |> 3 |> empty)
    |> (2 |> 3 |> 4 |> empty) 
    |> (3 |> 4 |> 5 |> empty) |> empty
n :: Matrix Three Two Integer
n =    (1 |> 0 |> empty)
    |> (0 |> 1 |> empty) 
    |> (1 |> 1 |> empty) |> empty
o = multiply n m
p = multiply n (transpose n)

Ответ 4

Более Haskell-идиоматично говорить не о матрицах, размерность которых является просто числом, которое мало говорит о структуре отображения/пространств, которые он отображает между ними. Вместо этого матричное умножение лучше всего рассматривать как операцию категории-композиции в категории Vect _k. Векторные пространства естественно представлены типами Хаскелла; vector-space library имеет это в течение длительного времени.

В качестве составной части линейных функций проверка размеров тогда является следствием проверки типа, которая в любом случае выполнялась для композиционных функций Хаскелла. И не только это, вы также можете различать разные пространства, которые могут быть несовместимы, несмотря на то, что они имеют одинаковое измерение - например, сами матрицы образуют векторное пространство (тензорное пространство), но пространство 3 × 3-матриц на самом деле не совместимо с пространством 9-элементных векторов. В Matlab и других "языках массива" обращение с линейными отображениями на пространстве линейного отображения требует подверженности ошибкам перестройки между тензорами разного ранга; конечно, мы не хотим этого в Haskell!

Есть один улов: эффективно реализовать эти функции, вы не можете просто иметь функции между любыми пробелами, но нуждаетесь в каком-то базовом представлении, которое все еще похоже на матрицу. Это работает только тогда, когда все разрешенные пространства фактически являются векторными пространствами, поэтому вы не можете использовать стандартный Category класс, поскольку для этого требуется id между любыми двумя типами. Вместо этого вам нужен класс категории, который фактически ограничен векторными пространствами. Однако это не очень сложно выразить в современном Haskell.

Две библиотеки, которые прошли этот маршрут:

• Mike Izbicki subhask, который использует внутренние матрицы hmatrix, но предоставляет хороший высокоуровневый интерфейс.
• Мой собственный linearmap-category, который использует выделенную реализацию тензоров, натянутых на каждое пространство.