Типобезопасное умножение матриц - PullRequest
Новая
       7

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

15 голосов
/ 01 декабря 2011

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

data Matrix ... = ...

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

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

Ответы [ 4 ]

11 голосов
/ 01 декабря 2011

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

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

, и вам нужно определить два дополнительных ADT s и класс 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)

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

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

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

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

Ссылка

11 голосов
/ 01 декабря 2011

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

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

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

10 голосов
/ 01 декабря 2011

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

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

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

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

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

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