[Top] [All Lists]

## [Haskell-cafe] Re: Space Efficiency When Sorting a List of Many Lists

 Subject: [Haskell-cafe] Re: Space Efficiency When Sorting a List of Many Lists Heinrich Apfelmus Thu, 31 Dec 2009 17:27:27 +0100
 ```Felipe Lessa wrote: > Luke Palmer wrote: >> But if you're serious, you can probably do better than just generating >> them all and passing them to sort. I get the impression that there is >> some structure here that can be taken advantage of. > > Isn't what he wants a trie? In particular, a Patricia trie? Peter, this is a very nice problem. Is this a programming exercise or did you encounter it in the "real world"? There is indeed a structure that can be taken advantage of and it involves tries. The key point is that thanks to the lexicographic ordering, you can *interleave* exploding and sorting the rows. In other word, we can exploit the fact that for example (sort . cartesian) ([8,12]:[11]:[7,13]:[10]:[]) = [8 : (sort . cartesian) ([11]:[7,13]:[10]:[]) ] ++ [12 : (sort . cartesian) ([11]:[7,13]:[10]:[]) ] where cartesian denotes the cartesian product. The code will mainly work with functions like type Row a = [a] headsIn :: [Row a] -> [(a, [Row a])] which groups rows by their first element. The result type is best understood as a finite map from a to [Row a] headsIn :: [Row a] -> Map a [Row a] And unsurprisingly, the fixed point of the (Map a) functor is the trie for [a] . Without much explanation, here the full formulation in terms of catamorphisms and anamorphisms. {-# LANGUAGE NoMonomorphismRestriction #-} import qualified Data.Map import Control.Arrow (second) -- the underlying structure newtype Map a b = Map { unMap :: [(a,b)] } deriving (Eq, Show) -- category theory: bananas and lenses instance Functor (Map a) where fmap f = Map . (map . second) f . unMap newtype Fix f = In { out :: f (Fix f) } cata f = In . fmap (cata f) . f ana f = f . fmap (ana f) . out -- very useful type synonym to keep track of rows and colums type Row a = [a] -- grouping and "ungrouping" by the first elements of each row headsIn :: [Row a] -> Map a [Row a] headsIn xss = Map [(x,[xs]) | x:xs <- xss] headsOut :: Map a [Row a] -> [Row a] headsOut (Map []) = [[]] headsOut xxs = [x:xs | (x,xss) <- unMap xxs, xs <- xss] -- cartesian product cartesian1 :: Row [a] -> Map a (Row [a]) cartesian1 [] = Map [] cartesian1 (xs:xss) = Map [(x,xss) | x <- xs] cartesian = ana headsOut . cata cartesian1 -- sorting sort1 :: Ord a => Map a [b] -> Map a [b] sort1 = Map . Data.Map.toList . Data.Map.fromListWith (++) . unMap sortRows = ana headsOut . cata (sort1 . headsIn) -- and cold fusion! -- sortCartesian = sortRows . cartesian -- best written as hylomorphism sortCartesian = ana headsOut . cata (sort1 . cartesian1) This is readily extended to handle the explode function as well. And thanks to lazy evaluation, I expect this to run with a much better memory footprint. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe ```
 Current Thread [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists, Peter Green Re: [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists, Alexander Dunlap Re: [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists, Luke Palmer Re: [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists, Daniel Fischer Re: [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists, Felipe Lessa [Haskell-cafe] Re: Space Efficiency When Sorting a List of Many Lists, Heinrich Apfelmus <= Re: [Haskell-cafe] Space Efficiency When Sorting a List of Many Lists, Peter Green [Haskell-cafe] Re: Space Efficiency When Sorting a List of Many Lists, Heinrich Apfelmus