Matrix as Applicative functor, which is not Monad

Question

I run into examples of Applicatives that are not Monads. I like the multi-dimensional array example but I did not get it completely.

Let's take a matrix M[A]. Could you show that M[A] is an Applicative but not a Monad with Scala code ? Do you have any "real-world" examples of using matrices as Applicatives ?

Answer 1

Something like M[T] <*> M[T => U] is applicative:

val A = [[1,2],[1,2]] //let's assume such imaginary syntax for arrays
val B = [[*2, *3], [*5, *2]]

A <*> B === [[2,6],[5,4]]

There may be more complex applicatives in signal processing for example. Using applicatives allows you to build one matrix of functions (each do N or less element-operations) and do only 1 matrix-operation instead of N.

Matrix is not a monoid by definition - you have to define "+" (concatenation) between matrixes for that (fold more precisely). And not every (even monoidal) matrix is a monad - you have to additionaly define fmap (not flatMap - just map in scala) to make it a Functor (endo-functor if it returns matrix). But by default Matrix isn't Functor/Monoid/Monad(Functor + Monoid).

About monadic matrixes. Matrix can be monoid: you may define dimension-bound concatenation for matrixes that are same sized along the orthogonal dimension. Dimension/size-independent concatenation will be something like:

val A = [[11,12],[21,22]]; val B = [[11,12,13],[21,22,23],[31,32,33]]
A + B === [[11,12,0,0,0], [21,22,0,0,0], [0,0,11,12,13],[0,0,21,22,23],[0,0,31,32,33]

Identity element will be []

So you can also build the monad (pseudocode again):

def flatMap[T, U](a: M[T])(f: T => M[U]) = {
    val mapped = a.map(f)// M[M[U]] // map
    def normalize(xn: Int, yn: Int) = ... // complete matrix with zeros to strict xn * yn size
    a.map(normalize(a.max(_.xn), a.max(_.yn)))
     .reduceHorizontal(_ concat _)
     .reduceVertical(_ concat _) // flatten
}

val res = flatMap([[1,1],[2,1]], x => if(x == 1)[[2,2]] else [[3,3,3]])

res === [[2,2,0,2,2],[3,3,3,2,2]]

Unfortunately, you must have zero-element (or any default) for T (not only for monoid itself). It doesn't make T itself some kind of magma (because no defined binary operation for this set is required - only some const defined for T), but may create additional problems (depending on your challenges).