Copyright	(c) Armando Santos 2019-2020
Maintainer	armandoifsantos@gmail.com
Stability	experimental
Safe Haskell	None
Language	Haskell2010

LAoP.Matrix.Type

Contents

Type safe matrix representation
Constraint type aliases
Type aliases
Primitives
Auxiliary type families
Matrix construction and conversion
Functor instance equivalent function
Applicative/Monoidal instance equivalent functions
Selective equivalent instance function
Monad equivalent instance function
Misc
Biproduct approach
Matrix composition and lifting
- Arrow matrix combinators
Relation
Matrix printing

Description

The LAoP discipline generalises relations and functions treating them as Boolean matrices and in turn consider these as arrows.

LAoP is a library for algebraic (inductive) construction and manipulation of matrices in Haskell. See my Msc Thesis for the motivation behind the library, the underlying theory, and implementation details.

This module offers a newtype wrapper around Matrix that uses arbitrary types instead of canonical data types for the matrices dimensions.

NOTE: If the types in the dimensions are custom they must need to implement a Generic instance.

Synopsis

newtype Matrix e (cols :: Type) (rows :: Type) = M (Matrix e (Normalize cols) (Normalize rows))
type Countable a = KnownNat (Count a)
type CountableDimensions a b = (Countable a, Countable b)
type CountableN a = KnownNat (Count (Normalize a))
type CountableDimensionsN a b = (CountableN a, CountableN b)
type FromListsN e a b = FromLists e (Normalize a) (Normalize b)
type Liftable e a b = (Bounded a, Bounded b, Enum a, Enum b, Eq b, Num e, Ord e)
type Trivial a = Normalize a ~ Normalize (Normalize a)
type TrivialE a b = Normalize (Either a b) ~ Either (Normalize a) (Normalize b)
type TrivialP a b = Normalize (a, b) ~ Normalize (Normalize a, Normalize b)
type Zero = Void
type One = ()
empty :: Matrix e Zero Zero
one :: e -> Matrix e One One
junc :: TrivialE a b => Matrix e a rows -> Matrix e b rows -> Matrix e (Either a b) rows
split :: TrivialE a b => Matrix e cols a -> Matrix e cols b -> Matrix e cols (Either a b)
type family FromNat (n :: Nat) :: Type where ...
type family Count (d :: Type) :: Nat where ...
type family Normalize (d :: Type) :: Type where ...
class FromLists e cols rows
fromLists :: FromListsN e cols rows => [[e]] -> Matrix e cols rows
toLists :: Matrix e cols rows -> [[e]]
toList :: Matrix e cols rows -> [e]
matrixBuilder :: (FromListsN e cols rows, CountableDimensionsN cols rows) => ((Int, Int) -> e) -> Matrix e cols rows
row :: FromListsN e cols () => [e] -> Matrix e cols One
col :: FromListsN e () rows => [e] -> Matrix e One rows
zeros :: (Num e, FromListsN e cols rows, CountableDimensionsN cols rows) => Matrix e cols rows
ones :: (Num e, FromListsN e cols rows, CountableDimensionsN cols rows) => Matrix e cols rows
bang :: forall e cols. (Num e, Enum e, FromListsN e cols (), CountableN cols) => Matrix e cols One
constant :: (Num e, FromListsN e cols rows, CountableDimensionsN cols rows) => e -> Matrix e cols rows
fmapM :: (Liftable e a b, CountableDimensionsN a b, FromListsN e b a) => (a -> b) -> Matrix e c a -> Matrix e c b
unitM :: Num e => Matrix e () ()
multM :: (CountableDimensionsN a b, CountableN (a, b), Num e, FromListsN e (a, b) a, FromListsN e (a, b) b, TrivialP a b) => Matrix e c a -> Matrix e c b -> Matrix e c (a, b)
selectM :: (Num e, FromListsN e b b, CountableN b, TrivialE a b) => Matrix e cols (Either a b) -> Matrix e a b -> Matrix e cols b
returnM :: forall e a. (Num e, Enum e, Enum a, FromListsN e () a, Countable a) => a -> Matrix e One a
bindM :: Num e => Matrix e a b -> Matrix e b c -> Matrix e a c
columns :: CountableN cols => Matrix e cols rows -> Int
rows :: CountableN rows => Matrix e cols rows -> Int
tr :: Matrix e cols rows -> Matrix e rows cols
cond :: (Trivial a, CountableN a, FromListsN e () a, FromListsN e a (), FromListsN e a a, Liftable e a Bool) => (a -> Bool) -> Matrix e a b -> Matrix e a b -> Matrix e a b
abideJS :: Matrix e cols rows -> Matrix e cols rows
abideSJ :: Matrix e cols rows -> Matrix e cols rows
(===) :: TrivialE a b => Matrix e cols a -> Matrix e cols b -> Matrix e cols (Either a b)
p1 :: (Num e, CountableDimensionsN n m, FromListsN e n m, FromListsN e m m, TrivialE m n) => Matrix e (Either m n) m
p2 :: (Num e, CountableDimensionsN n m, FromListsN e m n, FromListsN e n n, TrivialE m n) => Matrix e (Either m n) n
(|||) :: TrivialE a b => Matrix e a rows -> Matrix e b rows -> Matrix e (Either a b) rows
i1 :: (Num e, CountableDimensionsN n m, FromListsN e n m, FromListsN e m m, TrivialE m n) => Matrix e m (Either m n)
i2 :: (Num e, CountableDimensionsN n m, FromListsN e m n, FromListsN e n n, TrivialE m n) => Matrix e n (Either m n)
(-|-) :: (Num e, CountableDimensionsN j k, FromListsN e k k, FromListsN e j k, FromListsN e k j, FromListsN e j j, TrivialE n m, TrivialE k j) => Matrix e n k -> Matrix e m j -> Matrix e (Either n m) (Either k j)
(><) :: forall e m p n q. (Num e, CountableDimensionsN m n, CountableDimensionsN p q, CountableDimensionsN (m, n) (p, q), FromListsN e (m, n) m, FromListsN e (m, n) n, FromListsN e (p, q) p, FromListsN e (p, q) q, TrivialP m n, TrivialP p q) => Matrix e m p -> Matrix e n q -> Matrix e (m, n) (p, q)
kp1 :: forall e m k. (Num e, CountableDimensionsN m k, CountableN (m, k), FromListsN e (m, k) m, TrivialP m k) => Matrix e (m, k) m
kp2 :: forall e m k. (Num e, CountableDimensionsN k m, CountableN (m, k), FromListsN e (m, k) k, TrivialP m k) => Matrix e (m, k) k
khatri :: forall e cols a b. (Num e, CountableDimensionsN a b, CountableN (a, b), FromListsN e (a, b) a, FromListsN e (a, b) b, TrivialP a b) => Matrix e cols a -> Matrix e cols b -> Matrix e cols (a, b)
identity :: (Num e, FromListsN e a a, CountableN a) => Matrix e a a
comp :: Num e => Matrix e cr rows -> Matrix e cols cr -> Matrix e cols rows
fromF :: (Liftable e a b, CountableDimensionsN cols rows, FromListsN e rows cols) => (a -> b) -> Matrix e cols rows
fromF' :: (Liftable e a b, CountableDimensionsN a b, FromListsN e b a) => (a -> b) -> Matrix e a b
toRel :: (Liftable (Natural 0 1) a b, CountableDimensionsN a b, FromListsN (Natural 0 1) b a) => (a -> b -> Bool) -> Matrix (Natural 0 1) a b
pretty :: (CountableN cols, Show e) => Matrix e cols rows -> String
prettyPrint :: (CountableN cols, Show e) => Matrix e cols rows -> IO ()

Documentation

LAoP (Linear Algebra of Programming) Inductive Matrix definition.

LAoP generalises relations and functions treating them as Boolean matrices and in turn consider these as arrows. This library offers many of the combinators mentioned in the work of Macedo (2012) and Oliveira (2012).

This definition is a wrapper around Type but dimensions are arbitrary data types. Type inference might not be as desired.

Type safe matrix representation

newtype Matrix e (cols :: Type) (rows :: Type) Source #

Constructors

M (Matrix e (Normalize cols) (Normalize rows))

Instances

Num e => Category (Matrix e :: Type -> Type -> Type) Source #	It isn't possible to implement the `id` function so it's implementation is `undefined`. However `comp` can be and this partial class implementation exists just to make the code more readable. Please use `identity` instead.
Instance details Defined in LAoP.Matrix.Type Methods id :: Matrix e a a # (.) :: Matrix e b c -> Matrix e a b -> Matrix e a c #
Eq e => Eq (Matrix e cols rows) Source #
Instance details Defined in LAoP.Matrix.Type Methods (==) :: Matrix e cols rows -> Matrix e cols rows -> Bool # (/=) :: Matrix e cols rows -> Matrix e cols rows -> Bool #
Num e => Num (Matrix e cols rows) Source #
Instance details Defined in LAoP.Matrix.Type Methods (+) :: Matrix e cols rows -> Matrix e cols rows -> Matrix e cols rows # (-) :: Matrix e cols rows -> Matrix e cols rows -> Matrix e cols rows # (*) :: Matrix e cols rows -> Matrix e cols rows -> Matrix e cols rows # negate :: Matrix e cols rows -> Matrix e cols rows # abs :: Matrix e cols rows -> Matrix e cols rows # signum :: Matrix e cols rows -> Matrix e cols rows # fromInteger :: Integer -> Matrix e cols rows #
Ord e => Ord (Matrix e cols rows) Source #
Instance details Defined in LAoP.Matrix.Type Methods compare :: Matrix e cols rows -> Matrix e cols rows -> Ordering # (<) :: Matrix e cols rows -> Matrix e cols rows -> Bool # (<=) :: Matrix e cols rows -> Matrix e cols rows -> Bool # (>) :: Matrix e cols rows -> Matrix e cols rows -> Bool # (>=) :: Matrix e cols rows -> Matrix e cols rows -> Bool # max :: Matrix e cols rows -> Matrix e cols rows -> Matrix e cols rows # min :: Matrix e cols rows -> Matrix e cols rows -> Matrix e cols rows #
Show e => Show (Matrix e cols rows) Source #
Instance details Defined in LAoP.Matrix.Type Methods showsPrec :: Int -> Matrix e cols rows -> ShowS # show :: Matrix e cols rows -> String # showList :: [Matrix e cols rows] -> ShowS #
NFData e => NFData (Matrix e cols rows) Source #
Instance details Defined in LAoP.Matrix.Type Methods rnf :: Matrix e cols rows -> () #

Constraint type aliases

type Countable a = KnownNat (Count a) Source #

Constraint type synonyms to keep the type signatures less convoluted

type CountableDimensions a b = (Countable a, Countable b) Source #

type CountableN a = KnownNat (Count (Normalize a)) Source #

type CountableDimensionsN a b = (CountableN a, CountableN b) Source #

type FromListsN e a b = FromLists e (Normalize a) (Normalize b) Source #

type Liftable e a b = (Bounded a, Bounded b, Enum a, Enum b, Eq b, Num e, Ord e) Source #

type Trivial a = Normalize a ~ Normalize (Normalize a) Source #

type TrivialE a b = Normalize (Either a b) ~ Either (Normalize a) (Normalize b) Source #

type TrivialP a b = Normalize (a, b) ~ Normalize (Normalize a, Normalize b) Source #

Type aliases

type Zero = Void Source #

Zero type alias

type One = () Source #

One type alias

Primitives

empty :: Matrix e Zero Zero Source #

Empty matrix constructor

one :: e -> Matrix e One One Source #

Unit matrix constructor

junc :: TrivialE a b => Matrix e a rows -> Matrix e b rows -> Matrix e (Either a b) rows Source #

Matrix Junc constructor

split :: TrivialE a b => Matrix e cols a -> Matrix e cols b -> Matrix e cols (Either a b) Source #

Matrix Split constructor

Auxiliary type families

type family FromNat (n :: Nat) :: Type where ... Source #

Type family that computes of a given type dimension from a given natural

Thanks to Li-Yao Xia this type family is super fast.

Equations

FromNat 0 = Void
FromNat 1 = ()
FromNat n = FromNat' (Mod n 2 == 0) (FromNat (Div n 2))

type family Count (d :: Type) :: Nat where ... Source #

Type family that computes the cardinality of a given type dimension.

It can also count the cardinality of custom types that implement the Generic instance.

Equations

Count (Natural n m) = (m - n) + 1
Count (List a) = (^) 2 (Count a)
Count (Either a b) = (+) (Count a) (Count b)
Count (a, b) = * (Count a) (Count b)
Count (a -> b) = (^) (Count b) (Count a)
Count (M1 _ _ f p) = Count (f p)
Count (K1 _ _ _) = 1
Count (V1 _) = 0
Count (U1 _) = 1
Count ((::) a b p) = Count (a p) Count (b p)
Count ((:+:) a b p) = Count (a p) + Count (b p)
Count d = Count (Rep d R)

type family Normalize (d :: Type) :: Type where ... Source #

Type family that normalizes the representation of a given data structure

Equations

Normalize d = FromNat (Count d)

Matrix construction and conversion

class FromLists e cols rows Source #

Type class for defining the fromList conversion function.

Given that it is not possible to branch on types at the term level type classes are needed bery much like an inductive definition but on types.

Minimal complete definition

fromLists

Instances

FromLists e () () Source #
Instance details Defined in LAoP.Matrix.Internal Methods fromLists :: [[e]] -> Matrix e () () Source #
FromLists e Void Void Source #
Instance details Defined in LAoP.Matrix.Internal Methods fromLists :: [[e]] -> Matrix e Void Void Source #
(FromLists e () a, FromLists e () b, Countable a) => FromLists e () (Either a b) Source #
Instance details Defined in LAoP.Matrix.Internal Methods fromLists :: [[e]] -> Matrix e () (Either a b) Source #
FromLists e () rows => FromLists e () (Either () rows) Source #
Instance details Defined in LAoP.Matrix.Internal Methods fromLists :: [[e]] -> Matrix e () (Either () rows) Source #
(FromLists e a (), FromLists e b (), Countable a) => FromLists e (Either a b) () Source #
Instance details Defined in LAoP.Matrix.Internal Methods fromLists :: [[e]] -> Matrix e (Either a b) () Source #
FromLists e cols () => FromLists e (Either () cols) () Source #
Instance details Defined in LAoP.Matrix.Internal Methods fromLists :: [[e]] -> Matrix e (Either () cols) () Source #
(FromLists e (Either a b) c, FromLists e (Either a b) d, Countable c) => FromLists e (Either a b) (Either c d) Source #
Instance details Defined in LAoP.Matrix.Internal Methods fromLists :: [[e]] -> Matrix e (Either a b) (Either c d) Source #

fromLists :: FromListsN e cols rows => [[e]] -> Matrix e cols rows Source #

Build a matrix out of a list of list of elements. Throws a runtime error if the dimensions do not match.

toLists :: Matrix e cols rows -> [[e]] Source #

Converts a matrix to a list of lists of elements.

toList :: Matrix e cols rows -> [e] Source #

Converts a matrix to a list of elements.

matrixBuilder :: (FromListsN e cols rows, CountableDimensionsN cols rows) => ((Int, Int) -> e) -> Matrix e cols rows Source #

Matrix builder function. Constructs a matrix provided with a construction function.

row :: FromListsN e cols () => [e] -> Matrix e cols One Source #

Constructs a row vector matrix

col :: FromListsN e () rows => [e] -> Matrix e One rows Source #

Constructs a column vector matrix

zeros :: (Num e, FromListsN e cols rows, CountableDimensionsN cols rows) => Matrix e cols rows Source #

The zero matrix. A matrix wholly filled with zeros.

ones :: (Num e, FromListsN e cols rows, CountableDimensionsN cols rows) => Matrix e cols rows Source #

The ones matrix. A matrix wholly filled with ones.

Also known as T (Top) matrix.

bang :: forall e cols. (Num e, Enum e, FromListsN e cols (), CountableN cols) => Matrix e cols One Source #

The T (Top) row vector matrix.

constant :: (Num e, FromListsN e cols rows, CountableDimensionsN cols rows) => e -> Matrix e cols rows Source #

The constant matrix constructor. A matrix wholly filled with a given value.

Functor instance equivalent function

fmapM :: (Liftable e a b, CountableDimensionsN a b, FromListsN e b a) => (a -> b) -> Matrix e c a -> Matrix e c b Source #

Functor instance equivalent function

Applicative/Monoidal instance equivalent functions

unitM :: Num e => Matrix e () () Source #

Applicative instance equivalent unit function,

multM :: (CountableDimensionsN a b, CountableN (a, b), Num e, FromListsN e (a, b) a, FromListsN e (a, b) b, TrivialP a b) => Matrix e c a -> Matrix e c b -> Matrix e c (a, b) Source #

Applicative instance equivalent unit function,

Selective equivalent instance function

selectM :: (Num e, FromListsN e b b, CountableN b, TrivialE a b) => Matrix e cols (Either a b) -> Matrix e a b -> Matrix e cols b Source #

Selective functors select operator equivalent inspired by the ArrowMonad solution presented in the paper.

Monad equivalent instance function

returnM :: forall e a. (Num e, Enum e, Enum a, FromListsN e () a, Countable a) => a -> Matrix e One a Source #

Monad instance equivalent return function,

bindM :: Num e => Matrix e a b -> Matrix e b c -> Matrix e a c Source #

Monad instance equivalent '(>>=)' function,

Misc

Get dimensions

columns :: CountableN cols => Matrix e cols rows -> Int Source #

Obtain the number of columns.

NOTE: The KnownNat constaint is needed in order to obtain the dimensions in constant time.

TODO: A columns function that does not need the KnownNat constraint in exchange for performance.

rows :: CountableN rows => Matrix e cols rows -> Int Source #

Obtain the number of rows.

NOTE: The KnownNat constaint is needed in order to obtain the dimensions in constant time.

TODO: A rows function that does not need the KnownNat constraint in exchange for performance.

Matrix Transposition

tr :: Matrix e cols rows -> Matrix e rows cols Source #

Matrix transposition.

McCarthy's Conditional

cond :: (Trivial a, CountableN a, FromListsN e () a, FromListsN e a (), FromListsN e a a, Liftable e a Bool) => (a -> Bool) -> Matrix e a b -> Matrix e a b -> Matrix e a b Source #

McCarthy's Conditional expresses probabilistic choice.

Matrix "abiding"

abideJS :: Matrix e cols rows -> Matrix e cols rows Source #

Matrix "abiding" followin the 'Junc'-'Split' abide law.

Law:

Junc (Split a c) (Split b d) == Split (Junc a b) (Junc c d)

abideSJ :: Matrix e cols rows -> Matrix e cols rows Source #

Matrix "abiding" followin the 'Split'-'Junc' abide law.

Law:

Split (Junc a b) (Junc c d) == Junc (Split a c) (Split b d)

Biproduct approach

Split

(===) :: TrivialE a b => Matrix e cols a -> Matrix e cols b -> Matrix e cols (Either a b) infixl 2 Source #

Matrix Split constructor

Projections

p1 :: (Num e, CountableDimensionsN n m, FromListsN e n m, FromListsN e m m, TrivialE m n) => Matrix e (Either m n) m Source #

Biproduct first component projection

p2 :: (Num e, CountableDimensionsN n m, FromListsN e m n, FromListsN e n n, TrivialE m n) => Matrix e (Either m n) n Source #

Biproduct second component projection

Junc

(|||) :: TrivialE a b => Matrix e a rows -> Matrix e b rows -> Matrix e (Either a b) rows infixl 3 Source #

Matrix Junc constructor

Injections

i1 :: (Num e, CountableDimensionsN n m, FromListsN e n m, FromListsN e m m, TrivialE m n) => Matrix e m (Either m n) Source #

Biproduct first component injection

i2 :: (Num e, CountableDimensionsN n m, FromListsN e m n, FromListsN e n n, TrivialE m n) => Matrix e n (Either m n) Source #

Biproduct second component injection

Bifunctors

(-|-) :: (Num e, CountableDimensionsN j k, FromListsN e k k, FromListsN e j k, FromListsN e k j, FromListsN e j j, TrivialE n m, TrivialE k j) => Matrix e n k -> Matrix e m j -> Matrix e (Either n m) (Either k j) infixl 5 Source #

Matrix coproduct functor also known as matrix direct sum.

(><) :: forall e m p n q. (Num e, CountableDimensionsN m n, CountableDimensionsN p q, CountableDimensionsN (m, n) (p, q), FromListsN e (m, n) m, FromListsN e (m, n) n, FromListsN e (p, q) p, FromListsN e (p, q) q, TrivialP m n, TrivialP p q) => Matrix e m p -> Matrix e n q -> Matrix e (m, n) (p, q) infixl 4 Source #

Matrix product functor also known as kronecker product

Applicative matrix combinators

Note that given the restrictions imposed it is not possible to implement the standard type classes present in standard Haskell. *** Matrix pairing projections

kp1 :: forall e m k. (Num e, CountableDimensionsN m k, CountableN (m, k), FromListsN e (m, k) m, TrivialP m k) => Matrix e (m, k) m Source #

Khatri Rao product first component projection matrix.

kp2 :: forall e m k. (Num e, CountableDimensionsN k m, CountableN (m, k), FromListsN e (m, k) k, TrivialP m k) => Matrix e (m, k) k Source #

Khatri Rao product second component projection matrix.

Matrix pairing

khatri :: forall e cols a b. (Num e, CountableDimensionsN a b, CountableN (a, b), FromListsN e (a, b) a, FromListsN e (a, b) b, TrivialP a b) => Matrix e cols a -> Matrix e cols b -> Matrix e cols (a, b) Source #

Khatri Rao Matrix product also known as matrix pairing.

NOTE: That this is not a true categorical product, see for instance:

               | kp1 comp khatri a b == a 
khatri a b ==> |
               | kp2 comp khatri a b == b

Emphasis on the implication symbol.

Matrix composition and lifting

Arrow matrix combinators

Note that given the restrictions imposed it is not possible to implement the standard type classes present in standard Haskell.

identity :: (Num e, FromListsN e a a, CountableN a) => Matrix e a a Source #

Identity matrix

comp :: Num e => Matrix e cr rows -> Matrix e cols cr -> Matrix e cols rows Source #

Matrix composition. Equivalent to matrix-matrix multiplication.

This definition takes advantage of divide-and-conquer and fusion laws from LAoP.

fromF :: (Liftable e a b, CountableDimensionsN cols rows, FromListsN e rows cols) => (a -> b) -> Matrix e cols rows Source #

Lifts functions to matrices with arbitrary dimensions.

NOTE: Be careful to not ask for a matrix bigger than the cardinality of types a or b allows.

fromF' :: (Liftable e a b, CountableDimensionsN a b, FromListsN e b a) => (a -> b) -> Matrix e a b Source #

Lifts functions to matrices with dimensions matching a and b cardinality's.

Relation

toRel :: (Liftable (Natural 0 1) a b, CountableDimensionsN a b, FromListsN (Natural 0 1) b a) => (a -> b -> Bool) -> Matrix (Natural 0 1) a b Source #

Lifts relation functions to Boolean Matrix

Matrix printing

pretty :: (CountableN cols, Show e) => Matrix e cols rows -> String Source #

Matrix pretty printer

prettyPrint :: (CountableN cols, Show e) => Matrix e cols rows -> IO () Source #

Matrix pretty printer