3

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 ?

Community
  • 1
  • 1
Michael
  • 41,026
  • 70
  • 193
  • 341
  • 2
    How would you define `flatMap` for matrices? – Gábor Bakos Dec 08 '14 at 17:07
  • I do not know. Does it prove that it is impossible ? I hope there is a better proof than "proof by lack of imagination" :) – Michael Dec 08 '14 at 17:08
  • 1
    Proving something is impossible is a bit harder. Proving a definition does not satisfy monad laws would be easier. :) – Gábor Bakos Dec 08 '14 at 17:10
  • Ok. Does such a proof exist or it is just our guess ? – Michael Dec 08 '14 at 17:17
  • 1
    You cannot show such things with Scala code, unless you write a theorem prover in Scala. – n. m. could be an AI Dec 10 '14 at 06:58
  • I suspect that it is hard to show that Matrix is not a monad, partly because Matrix is in fact a monad. – n. m. could be an AI Dec 10 '14 at 07:02
  • @n.m. So, how would you write `flatMap` for Matrix ? – Michael Dec 10 '14 at 07:05
  • @n.m. I guess it is possible to show with Scala code that matrix is an applicative functor. – Michael Dec 10 '14 at 07:07
  • Wait, are you talking about fixed-size matrices or arbitrary size matrices? – n. m. could be an AI Dec 10 '14 at 07:11
  • You can demonstrate some Scala code, but you need to separately show that it is well-behaved. – n. m. could be an AI Dec 10 '14 at 07:13
  • Maybe I can show that it _behaves well_ with unit tests. – Michael Dec 10 '14 at 07:21
  • Let's consider matrices of arbitrary size. I guess it would be easier. Is it possible to write `flatMap` for such matrices ? – Michael Dec 10 '14 at 07:22
  • 1
    Sure. It's just like List in each dimension separately. Imagine a rectangular array of things written down on a whiteboard, say 5x6 things, with a border around it. Now imagine a rectangular array of such rectangular arrays, say, a 7x8 one, written on a whiteboard. Now wipe the internal borders. You end up with a (5*7)x(6*8) rectangular array of things. That's your `flatten`. `flatMap` is just a composition of `map` and `flatten`, so it's trivial. – n. m. could be an AI Dec 10 '14 at 07:44
  • 1
    No wait, that's not correct. I have assumed all the internal matrices are of the same size, which of course need not be true. Shame on me. – n. m. could be an AI Dec 10 '14 at 07:50
  • @n.m No problem :) I will think it over. It is interesting _why_ a one-dimensional array is a monad while a multi-dimensional array is probably not. Looks like adding a dimension changes the game completely. – Michael Dec 10 '14 at 07:59
  • one-dimensional array is a monad only if `map` and `++` are defined. Generally, you may define it in several ways - there is no general rules how to concat one-dim arrays. Same for matrixes, but they don't have so obvious concatenation, like "add second list to tail of another", because they have N + M tails and shape restricted to be rectangular. – dk14 Dec 10 '14 at 09:34

1 Answers1

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).

dk14
  • 22,206
  • 4
  • 51
  • 88