CODEWITHSUNDEEP
haskelltypesnested
arryn
arryn

Reputation: 329

Nested datatype for square matrices

I am trying to understand how this datatype (Square) represents square matrices.

type Square = Square' Nil
data Square' t a = Zero (t (t a) ) | Succ (Square' (Cons t) a)
data Nil a = Nil
data Cons t a = Cons a (t a)

So. What is t here? I suppose it is one of the types declared above. I decided to start with the simplest, so 

Zero (Nil (Nil Int))

If I put integer 4 as a value, is this a matrix (4)?

Suppose it is something. Now, what is this:

Succ ( Zero (Cons t) a)

if I am right about t, then this, perhaps, must represent some 2×2 matrix, but what are its values?

Succ (Zero (Cons Nil) a)

I would appreciate your help in my understanding of how it is a square matrix.

Upvotes: 7

Views: 222

Answers (1)

chi
chi

Reputation: 116174

Let's introduce some informal notation to guide intuition. Write T :> U to denote that T is a sum type having one or more subcases, and U is one of them (at least modulo some isomorphism). We'll also use = between types to denote isomorphism.

So, by definition, we have

Square a = Square' Nil a
:> { taking the Zero branch }
Nil (Nil a)
=
()

So, this case denotes the empty "0x0" matrix.

Square a = Square' Nil a
:> { taking the Succ branch }
Square' (Cons Nil) a
:> { taking the Zero branch }
Cons Nil (Cons Nil a)
=  { def of Cons }
(Cons Nil a, Nil (Cons Nil a))
=  { def of Cons }
((a, Nil a), Nil (Cons Nil a))
=  { def of Nil }
((a, ()), ())
=
a

So, this is the 1x1 matrix.

Square a = Square' Nil a
:> { taking the Succ branch }
Square' (Cons Nil) a
:> { taking the Succ branch again }
Square' (Cons (Cons Nil)) a
:> { taking the Zero branch }
Cons (Cons Nil) (Cons (Cons Nil) a)
=
Cons (Cons Nil) (a, Cons Nil a)
=
Cons (Cons Nil) (a, a, Nil a)
=
Cons (Cons Nil) (a, a, ())
=
Cons (Cons Nil) (a, a)
=
((a,a), Cons Nil (a, a))
=
((a,a), (a,a), Nil (a, a))
=
((a,a), (a,a), ())
=
((a,a), (a,a))

So, this is the 2x2 matrix.

We should now be able to spot some pattern. Taking the Succ branches, we end up with a type of the form

Square' (Cons (Cons (Cons (...(Cons Nil))))) a

Which becomes, with the final Zero,

F (F a)
  where F = (Cons (Cons (Cons (...(Cons Nil)))))

Note that we considered all possible cases, so the final type must indeed be of the form F (F a) with some F of the form above.

Now, one can see that F a is isomorphic to (a,a,a,....) where the number N of as it exactly the number N of Conses in the definition of F. Hence, F (F a) will produce a square matrix (an N-tuple of N-tuples = square matrix).

Let's prove that by induction on the number of Conses. For the zero case, we have F = Nil, and indeed, as we wanted, zero as appear:

Nil a = ()

For the induction case, assume F a with N Conses is (a,a,...) with N as. The N+1 case to prove would state that (Cons F) a is (a,a,...,a), having N+1 as. Indeed:

Cons F a
=
(a, F a)
=
(a, (a,a....))   { 1 + N a's , as wanted }

QED.

Upvotes: 8

Related Questions