More suitable data structure needed

Dr Mark H Phillips mark@austrics.com.au
21 Aug 2002 16:44:03 +0930


Hi,

Consider the following data structure, effectively
of type [[(Int,Int)]]:

(2,5) (1,3) (2,0)
(2,5) (1,2) (1,1) (1,0)
(2,5) (3,1)
(1,5) (2,4) (2,0)
(1,5) (1,4) (1,3) (1,1) (1,0)
(1,5) (1,4) (2,2) (1,0)
(1,5) (1,4) (1,2) (2,1)
(1,5) (2,3) (1,2) (1,0)
(1,5) (2,3) (2,1)
(1,5) (1,3) (2,2) (1,1)
(1,5) (4,2)

Notice that the some of the "inner lists" start off the same.
If we delete the repetitions, we can more clearly see an
emerging structure.

(2,5) (1,3) (2,0)
      (1,2) (1,1) (1,0)
      (3,1)
(1,5) (2,4) (2,0)
      (1,4) (1,3) (1,1) (1,0)
            (2,2) (1,0)
            (1,2) (2,1)
      (2,3) (1,2) (1,0)
            (2,1)
      (1,3) (2,2) (1,1)
      (4,2)

I would like to represent this structure in Haskell, but 
am not sure quite the best way of doing it.  (I am relatively
new to Haskell.)  I think I want to do something like:

[
[(2,5),[(1,3),[(2,0)]],
       [(1,2),[(1,1),[(1,0)]]],
       [(3,1)]],
[(1,5),[(2,4),[(2,0)]],
       [(1,4),[(1,3),[(1,1),[(1,0)]]],
              [(2,2),[(1,0)]],
              [(1,2),[(2,1)]]],
       [(2,3),[(1,2),[(1,0)]],
              [(2,1)]],
       [(1,3),[(2,2),[(1,1)]]],
       [(4,2)]]
]

But what is the best way to represent this in Haskell?  (Clearly
I can't do exactly this, because Haskell requires all list elements
to be of the same type.)

Thanks,

Mark.