Тип-безопасная матрица Умножение

Question

После многослойного обсуждения в Напишите умнопление матрицы Scala в Haskell, Я остался задаваться вопросом ... как будет выглядеть умение матрицы, безопасную типа? Итак, вот ваша задача: либо ссылка на реализацию Haskell, либо реализовать себя следующим образом:

data Matrix ... = ...

matrixMult :: Matrix ... -> Matrix ... -> Matrix ...
matrixMult ... = ...

Где matrixMult производит Тип ошибки в Время компиляции Если вы попытаетесь умножить две матрицы на несовместимые измерения. Брауни указывает, если вы ссылаетесь на статьи или книги, в которых обсуждаются эта точная тема, и/или обсудите себя, насколько полезна/бесполезна эта функция.

Answer 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

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

Исторический интерес представляет Макбрайд "Подделывая это" с 2001 года, который описывает крепко напечатанные векторы. Методы, которые он использует, довольно похожи на тех, которые используются в вышеуказанных пакетах. Они были явно известны в кругах, делая зависимо напечатанное программирование, но мое впечатление состоит в том, что бумага «подделка его» является одним из более ранних случаев, когда они использовались в Хаскелле. Олег Статья Monad Reader 2005 Типы также имеют хорошее обсуждение истории этих методов.

Answer 2

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

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

и вы должны определить два аддитонала ADTS и класс TLN (Натурал типа):

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 May Barf при компиляции. Это просто набросок о том, как это можно сделать.

Ссылка на сайт

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

Answer 3

Извините, не могу устоять перед тем, что я вставил много лет назад. Это было перед семействами типа, поэтому я использовал фонды для арифметики. Я подтвердил, что это все еще работает на 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)

Answer 4

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

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

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

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

• Майк Избицки Субхаска, который использует матрицы HMatrix внутри, но обнажает хороший интерфейс высокого уровня.
• Мой собственный Linearmap-Category, который использует выделенную реализацию тензоров, охватываемой каждым пространством.