[Haskell-cafe] Finding longest common prefixes in a list

Gwern Branwen gwern0 at gmail.com
Fri Jan 20 23:44:14 CET 2012

On Fri, Jan 20, 2012 at 1:57 PM, Twan van Laarhoven <twanvl at gmail.com> wrote:
> Here is some example code (untested):

Well, you're right that it doesn't work. I tried to fix the crucial
function, 'atLeastThisManyDescendants', but it's missing something
because varying parts doesn't much affect the results when I try it
out on example input - it either returns everything or nothing, it

atLeastThisManyDescendants :: Int -> Trie a -> [CommonPrefix a]
atLeastThisManyDescendants minD trie@(Trie l d t')
   | d < minD = []
   | null forChildren = [Prefix [] trie]
   | otherwise = forChildren
   forChildren = [ Prefix (x:pfx) nms
                 | (x,t) <- Map.toList t'
                 , Prefix pfx nms <- atLeastThisManyDescendants l t ]


More information about the Haskell-Cafe mailing list