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

[Gwern Branwen]

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
seems:

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

-- 
gwern
http://www.gwern.net