In a list of lists, impose the same length

Question

I have this data type, which should represent a table:

data R = R [Bool]  deriving Eq -- Row
data T = T [R]     deriving Eq -- Table

The problem is that it allows to have table of rows with different length, eg:

tab =T [R [True, False, True, True],
        R [False, False, True, False],
        R [False, False, False, True],
        R [False, False]]

Is it possible to modify the data definition of T to impose that all the R elements have the same length?

Answer 1

Yup, there's a pretty standard way to achieve that. The price you pay, however, is that you don't get to use the standard list functions (because you won't be using a standard list). The idea goes like this: we'll first have a spine telling how long all the "lists" are, then we'll have the actual lists at the bottom of the spine. You can encode the lengths of the lists in many ways; below, I'll just show how to do it with the simple unary numbering system, but you can of course design more efficient versions with other numbering systems.

data BalancedLists_ a as
    = Nil [as]
    | Cons (BalancedLists_ a (a, as))

type BalancedLists a = BalancedLists_ a ()

For example, a balanced list containing two length-3 lists would look like this:

Cons (Cons (Cons (Nil [(1, (2, (3, ()))), (4, (5, (6, ())))])))

There's a wonderful paper extending this technique in a hundred different directions called Manufacturing Datatypes by Ralf Hinze.