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 | [EMAIL PROTECTED] 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 > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell > _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
