-- Trie, yet another implementation -- (c) Vadim Vinnik, 2011 trieEmpty = Trie False [] trieInsert (Trie _ l) [] = Trie True l trieInsert (Trie x l) s = Trie x (f l s) where f [] (a:b) = [h a b] f l1@(e@(TrieEdge c1 t):l2) s@(c2:s2) | c1 == c2 = (TrieEdge c1 (trieInsert t s2)):l2 | c1 > c2 = (h c2 s2) : l1 h a b = TrieEdge a (trieInsert trieEmpty b) trieExists (Trie x _) [] = x trieExists (Trie _ l) s = f l s where f [] _ = False f ((TrieEdge c1 t):l2) s@(c2:s2) | c1 == c2 = trieExists t s2 trieToString t = h t " " where f (TrieEdge c t) = (s ++ (c:[]) ++ (h t (" " ++ s))) trieAllWords (Trie x l) = (if x then "":r else r) where trieEndings t [] = trieAllWords t trieEndings (Trie _ l) s = f l s where f [] _ = [] f ((TrieEdge c1 t1):l1) s1@(c2:s2) | c1 == c2 = trieEndings t1 s2 | c1 < c2 = f l1 s1 let t = trieFromText s
what which witch when where will wire wind window
[1 of 1] Compiling Main ( prog.hs, prog.o ) Linking prog ...
w h a t# e n# r e# i c h# i l l# n d# o w# r e# t c h# ["what","when","where","which","will","wind","window","wire","witch"] ["at","en","ere","ich"] ["will","wind","window","wire","witch"]