I would consider using a prefix trie. Unfortunately, such a structure is not built in to Haskell. The data structure basically contains a root; at the root you look up the first element, which gives you a new trie which represents all of the elements which begin with that initial element. If that initial element is in fact in the trie, a flag is set. A naive implementation would be something like (I haven't tested/compiled this code, so there are 'bugs'...consider it 'psuedo-haskell'): data PreTrie a = PreTrie [(a, (Bool, PreTrie a))] -- (element, is-element-in-trie, children) empty :: PreTrie a empty = PreTrie [] -- elements are non-empty lists (exercise to extend it to allow -- emty lists) insert :: PreTrie a -> [a] -> PreTrie a insert (PreTrie l) a = PreTrie (insert' x a) insert' [] [x] = [(x, (True, empty))] insert' [] (x:xs) = [(x, (False, insert empty xs))] insert' ((a,(b,c)):ls) [x] | a == x = (a,(True,c)) : ls | otherwise = (a,(b,c)) : insert' ls [x] insert' ((a,(b,c)):ls) (x:xs) | a == x = (a,(b,insert c xs)) : ls | othewrise = (a,(b,c)) : insert' ls (x:xs) elem :: PreTrie a -> [a] -> Bool elem (PreTrie l) a = elem' l a elem' [] _ = False elem' ((a,(b,c)):ls) [x] | a == x = b | otherwise = -- exercise elem' ((a,(b,c)):ls) (x:xs) | a == x = elem c xs | otherwise = -- exercise ANyway, that's my suggestion... -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On 21 Aug 2002, Dr Mark H Phillips wrote:
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.
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell