import qualified Data.Map as Map -- A trie datatype data Trie a = Trie { numLeafs, numDescendant :: !Int , children :: Map.Map a (Trie a) } instance (Show a) => Show (Trie a) where showsPrec _ t = showString "fromList " . shows (toList t) -- The empty trie empty :: Trie a empty = Trie 0 0 Map.empty -- A trie that contains a single string singleton :: Ord a => [a] -> Trie a singleton [] = Trie 1 1 Map.empty singleton (x:xs) = Trie 0 1 (Map.singleton x (singleton xs)) -- Merge two tries merge :: Ord a => Trie a -> Trie a -> Trie a merge (Trie l d c) (Trie l' d' c') = Trie (l+l') (d+d') (Map.unionWith merge c c') fromList :: Ord a => [[a]] -> Trie a fromList = foldr merge empty . map singleton toList :: Trie a -> [[a]] toList (Trie l _ c) = replicate l [] ++ [ x:xs | (x,t) <- Map.toList c, xs <- toList t ] data CommonPrefix a = Prefix { prefix :: [a], names :: Trie a } instance (Show a) => Show (CommonPrefix a) where showsPrec _ (Prefix p ns) = shows p . showString " ++ " . shows (toList ns) -- Find prefixes that have at least minD descendants. -- when there is a prefix xs with >=minD descendants, then shorter prefixes will not be returned atLeastThisManyDescendants :: Int -> Trie a -> [CommonPrefix a] atLeastThisManyDescendants minD trie@(Trie l d c) | d < minD = [] -- too few descendants | null forChildren = [Prefix [] trie] -- all longer prefixes have too few descendants, but this prefix doesn't | otherwise = forChildren -- there are longer prefixes with enough descendants, return them where forChildren = [ Prefix (x:pfx) names | (x,t) <- Map.toList c , Prefix pfx names <- atLeastThisManyDescendants minD t ] test1 = fromList ["chorus-kiminoshiranaimonogatari.ogg" ,"chorus-mrmusic.ogg" ,"choucho-lastnightgoodnight.ogg" ,"dylanislame-aikotoba.ogg" ,"electriclove-������������������������������-korskremix.ogg" ,"gumi-bacon8-justhangingaround.ogg" ,"gumi-iapologizetoyou.ogg" ,"gumi-montblanc.ogg" ,"gumi-mozaikrole.ogg" ,"gumi-������������������������������.ogg" ,"gumi-showasengirl.ogg" ,"gumi-sweetfloatflats������������������������������������.ogg" ,"gumi-timewarpedafterchoppingmystagbeetle.ogg" ,"gumi-������������������-���������������������.ogg" ,"gumi-���������������������������.ogg" ,"kaito-byakkoyano.ogg" ,"kaito-flowertail.ogg" ,"kasaneteto-tam-ochamekinou���������������������������������������������.ogg" ,"len-crime-timetosaygoodbye.ogg" ,"len-fire���flower.ogg" ,"len-ponponpon.ogg" ,"lily-prototype.ogg" ,"luka-apolxcore-waitingforyou.ogg" ,"luka-dim���������.ogg" ,"luka-dion-myheartwillgoon.ogg" ,"luka-dirgefilozofio-dirgeasleepinjesus.ogg" ,"luka-���������������-doubelariat������������������������.ogg" ,"luka-emon-heartbeats.ogg" ,"luka-emonloid3-������������������.ogg" ,"luka-everybreathyoutake.ogg" ,"luka-���������������-garden.ogg" ,"luka-justbefriends.ogg" ,"lukameiko-gemini.ogg" ,"luka-milkyway.ogg" ,"luka-������������-���������.ogg" ,"luka-tic-tick.ogg" ,"luka-torinouta.ogg" ,"luka-zeijakukei-shounenshoujo.ogg" ,"luka-������������������-nologic-���������������.ogg" ,"luka-������������.ogg" ,"meiko-artemis-awake.ogg" ,"miku-9ronicle������������.ogg" ,"miku-acolorlinkingworld-���������������������.ogg" ,"miku-acolorlinkingworld-���������.ogg" ,"miku-a+jugos-lullabyforkindness.ogg" ,"miku-akayaka-beacon.ogg" ,"miku-akayakap-sunrise.ogg" ,"miku-aoihana.ogg" ,"miku-arabianresponse.ogg" ,"miku-avtechno-tear.ogg" ,"miku-���������������������cicci.ogg" ,"miku-cleantears-remind2011natsu-greenhillzonecrystiararemix.ogg" ,"miku-cleantears-remind2011natsu-������summerwindremix.ogg" ,"miku-clocklockworks.ogg" ,"miku-dancedancevol2-runner.ogg" ,"miku-daniwellp-chaoticuniverse.ogg" ,"miku-dixieflatline-shinonomescrumble.ogg" ,"miku-electriclove���������������������������.ogg" ,"miku-elegumitokyo-kissmebaby.ogg" ,"miku-galaxyodyssey-cryingirl.ogg" ,"miku-galaxyodyssey-galaxyspacelines.ogg" ,"miku-hakamairi.ogg" ,"miku-haruna.ogg" ,"miku-heartshooter.ogg" ,"miku-hoshikuzutokakera.ogg" ,"miku-innes.ogg" ,"miku-innocence������������.ogg" ,"miku-jemappelle-motion-likeyou.ogg" ,"miku-jemappelle-motion-ohwell.ogg" ,"miku-jevannip-myfavoritesummer.ogg" ,"miku-kakokyuudance-������������������.ogg" ,"miku-kz-packaged.ogg" ,"miku-kz-tellyourworld.ogg" ,"miku-lastscene.ogg" ,"miku-lostmemories������-������������.ogg" ,"miku-lovelyday.ogg" ,"miku-������������love_song.ogg" ,"mikulukagumi-prayfor.ogg" ,"miku-maple-���������������-������������������.ogg" ,"miku-more1.5.ogg" ,"miku-m@rk-eklosion.ogg" ,"miku-m@rk-kirch.ogg" ,"miku-nana-������������������������-������������������������.ogg" ,"miku-nekomimiswitch.ogg" ,"miku-nightrainbow.ogg" ,"miku-noyounome.ogg" ,"miku-������������������������������������������������������.ogg" ,"miku-pandolistp-neverendinghammertime.ogg" ,"miku-������������P-birthdayofeden-deepsleep.ogg" ,"miku-������������P-birthdayofeden-������������.ogg" ,"miku-plustellia-dear.ogg" ,"miku-plustellia-������������-crazygirl.ogg" ,"miku-plustellia-������������-discoradio.ogg" ,"miku-������������P-���������������������.ogg" ,"miku-rabbitforgets.ogg" ,"miku-re:package-lastnightgoodnight.ogg" ,"miku-re:package-ourmusic.ogg" ,"miku-re:package-sutorobonaitsu.ogg" ,"miku-rollinggirl.ogg" ,"miku-ryo-���������-melt.ogg" ,"miku-senseiniitteyaro.ogg" ,"miku-sevencolors-���������������.ogg" ,"miku-shoukinosatadenia.ogg" ,"miku-stratosphere.ogg" ,"miku-supernova.ogg" ,"miku-tam-lastnightgoodnight.ogg" ,"miku-tanatofobia.ogg" ,"miku-thearmyforyourenvy-������������������������.ogg" ,"miku-theendlesslove.ogg" ,"miku-tinyparadise-snowflake.ogg" ,"miku-tinyparadise-tinyparadise.ogg" ,"miku-unfragment.ogg" ,"miku-worldismine-���������������������.ogg" ,"miku-yakiimo.ogg" ,"miku-���������������������-���������������.ogg" ,"miku-������������������������������������������������.ogg" ,"miku-���������life.ogg" ,"miku-������������������������������������������������������.ogg" ,"miku-������������beautyfloor-buddhamix.ogg" ,"miku-���������������������.ogg" ,"niconicochorus-blackrockshooter.ogg" ,"niconicochorus-justbefriends.ogg" ,"rin-dixieflatline-gemini.ogg" ,"rin-elegumitokyo-������������������girlsside.ogg" ,"rin-helloworld.ogg" ,"rin-jutenija.ogg" ,"rin-lastnightgoodnight.ogg" ,"rin-ripples-evergreen.ogg" ,"rin-����������c.ogg" ,"rollinggirl-piano.ogg" ,"seeu-gagain-������������ddadada.ogg" ,"utau-������������beyond������������������.ogg" ,"yuki-discochocolatheque.ogg" ,"yuki-shouwasenhosiga^ru.ogg" ,"yuki-shouwasenhosiga^ru.ogg"]