On Wed, Aug 21, 2002 at 04:44:03PM +0930, Dr Mark H Phillips wrote:
... 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.)
This is the same as one way of representing search trees, called a "trie". Two representations in Haskell are:
data Trie a = Trie [(a, Trie a)]
or, using the FiniteMap module, if you only care about the set of lists,
data Trie a = Trie (FiniteMap a (Trie a))
(There are slight variations depending on your exact needs.) Best, Dylan