Recursive definition of Matrix

Like Linked-list for Array, is there a recursive counter-part for Matrix?

Is there a persistent data structure which can be used in place of Matrix in pure functional language like Haskell?

Multiple Dimensions

For a recursive counterpart for matrices, we need dependent types.

Indeed, lists are one dimensional and so (horizontal) concatenation of lists is all that is needed. However, matrices are two dimensional and so concatenation may be meaningless if the sizes do not match up. That is to say, all rows need to have the same number of columns and likewise all columns need to have the same number of rows for a matrix to be (conventionally) meaningful. I mean, for example, usually no one thinks of, say, two rows that have two different length columns as being a matrix.

A Quick Implementation

So for concatenation, we need to keep track of the lengths. We can do so by using a language that supports dependent types, such as Idris or Agda. Haskell can mimic them, but a difficult task onto itself. So here's a naive implementation in Agda.

data Matrix (A : Set) : (rows columns : ℕ) → Set where
  ∣_∣ : A → Matrix A 1 1
  _Φ_  : ∀ {r c₁ c₂} → Matrix A r c₁ → Matrix A r c₂ → Matrix A r (c₁ + c₂)
  _⊝_  : ∀ {c r₁ r₂} → Matrix A r₁ c → Matrix A r₂ c → Matrix A (r₁ + r₂) c

The first constructor embeds the type A into 1-by-1 matrices and the other two constructors are for horizontal and vertical concatenation. Notice that the natural numbers are used to keep the matrices meaningful. For example, you can stick two matrices side-by-side to produce a wider matrix precisely if the two have the same number of rows.

For example, the 2-by-2 identity matrix

id₂ : Matrix ℕ 2 2
id₂ = (∣ 1 ∣ Φ ∣ 0 ∣) ⊝
      (∣ 0 ∣ Φ ∣ 1 ∣)

Map

In one of the above comments, you remark that its troubling that we cannot pattern match and define recursive functions. Well, we can :-)

For example, the usual map of lists has a matrix counterpart.

map : ∀ {A B} (f : A → B) → ∀ {c r} → Matrix A r c → Matrix B r c
map f ∣ x ∣ = ∣ f x ∣
map f (m Φ m₁) = map f m Φ map f m₁
map f (m ⊝ m₁) = map f m ⊝ map f m₁

toString : ℕ → String
toString zero = "Zero"
toString (suc zero) = "One"
toString _ = "just no"

map-test : map toString id₂ ≡ (∣ "One"  ∣ Φ ∣ "Zero" ∣) ⊝
                              (∣ "Zero" ∣ Φ ∣ "One"  ∣)
map-test = refl

More Involved Example

As a more complicated example, let's consider matrices made by a single constant ---compare to Haskell's repeat operation that takes an element e and returns a list [e,e,...,e].

: ∀ {A} → A → ∀{r c} → Matrix A (suc r) (suc c)
 e {0} {0} = ∣ e ∣                     -- 1x1 singleton matrix
 e {0} {c + 1} = ∣ e ∣ Φ  e             -- row-vector of length r+1
 e {r + 1} {0} = ∣ e ∣ ⊝  e             -- column vector of length r+1
 e {r + 1} {c + 1} = (∣ e ∣ Φ  e) ⊝  e -- (∣ e ∣ ⊝  e {m} {0}) Φ  e {m+1}{c}

The last one says:

(    e  |  e   )
 e {r+1} {c+1} =  (  ------------- )
                   (  e {r} {c+1} )

Indeed any × matrix can be construed as the vertical concatenation
of an -row vector above an (-1)× matrix ---note a recursion!
In this case, our row vector is the element e followed by an r-row vector of e's.

Example usage:

test :  5 {2} {2}
   ≡   (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣) ⊝
       (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣) ⊝
       (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣)
test = refl

Sources

Of course, the implementation was brief and just to answer your question.
A more full account can be found in the elegant lecture notes of Richard Bird.

Hope this helps!

StackExchange Computer Science Q#56489, answer score: 7