More suitable data structure needed

[Hal Daume III]

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
>