I am using the external-sort package to sort my output in the program below. I made this choice because my output dataset [[Int]] can be large (e.g. >3M items, each [Int]). What my program does: (1) Reads in a file containing 'compressed lists' which look like so: 8+12,11,7+13,10 1+2+3,1+9,3+6,4 . . One compressed list per line. These compressed lists are parsed to become [[[Int]]] [[[8,12],[11],[7,13],[10]], [[1,2,3],[1,9],[3,6],[4]], . . ] Generally files of compressed lists have lengths of ~10,000 lines. (2) Compressed lists are exploded to [[int]] via concatMap Cartesian Product over [[[Int]]], so we end up with [[Int]] [[8, 11, 7, 10], [8, 11, 13, 10], [12, 11, 7, 10], [12, 11, 13, 10], [1, 1, 3, 4], . . [3, 9, 6, 4]] These 'exploded lists are' *much* longer than the input lists. It's common for them to have >100K [Int] members, or even >1M [Int] members. (3) This [[Int]] data must be sorted in to lexicographic order and output as CSV data: i.e. output should be: 1,1,3,4 3,9,6,4 8,11,7,10 . . 12,11,13,10 There is no way to avoid the necessity of sorting the final product. I can *not* take advantage of any structure in the input data to avoid this sort stage. e.g. sorting the (smaller) input compressed lists *will not* obviate the need to lex sort the (larger) final output. The program listing below works correctly, but *is not* space- efficient. In fact it is *less* space-efficient than the equivalent program using Prelude sort! e.g. with one data set which explodes to ~3.7M I am seeing 639MB of total memory use. I am sure externalSort is not at fault because: (a) I'm the Newbie. (b) ExternalSort.bin is 'only' 228MB in size. (Expected to be not small because sorting a [[Int]] with 3.7M [Int] members.) I'm sure it must be something I'm doing wrong elsewhere which is causing the entire output data list to be read into memory. What I really want to happen is: (1) Data lazily read in from stdin and lazily parsed (2) Data lazily sucked out to disk and strictly sorted by externalSort (but no big deal since this happening on disk) (3) Data lazily sucked back out of externalSort, lazily formatted for output, and lazily written to stdout. So memory usage should hopefully never go over (say 10MB). But in fact I'm using 638MB. So somewhere in the code below I must be doing something very wrong. I hope someone can tell me what I am doing wrong here. TIA! import Algorithms.ExternalSort import Data.List.Split (splitOn) import System.IO -- Cartesian Product over a List of Lists -- Http://www.cs.nott.ac.uk/~gmh/sudoku.lhs -- cp [[1,2],[3],[4,5,6]] --> [[1,3,4],[1,3,5],[1,3,6],[2,3,4],[2,3,5], [2,3,6]] cp :: [[a]] -> [[a]] cp [] = [[]] cp (xs:xss) = [y:ys | y <- xs, ys <- cp xss] -- fromCSV ["8+12,11,7+13,10", "1+2+3,1+9,3+6,4"] --> -- [[[8,12],[11],[7,13],[10]],[[1,2,3],[1,9],[3,6],[4]]] fromCSV :: [String] -> [[[Int]]] fromCSV = map parseOneLine where parseOneLine = map parseGroup . splitOn "," where parseGroup = map read . splitOn "+" -- explode [[[1,2],[3],[4,5,6]], [[1, 2], [14,15], [16]]] --> [[1,3,4], [1,3,5], -- [1,3,6],[2,3,4],[2,3,5],[2,3,6],[1,14,16],[1,15,16],[2,14,16], [2,15,16]] explode :: [[[a]]] -> [[a]] explode = concatMap cp -- toSingles "8+12,11,7+13,10\n1+2+3,1+9,3+6,4" --> -- [[8,11,7,10],[8,11,13,10],[12,11,7,10],[12,11,13,10],[1,1,3,4], [1,1,6,4], -- [1,9,3,4],[1,9,6,4],[2,1,3,4],[2,1,6,4],[2,9,3,4],[2,9,6,4], [3,1,3,4], -- [3,1,6,4],[3,9,3,4],[3,9,6,4]] toSingles :: String -> [[Int]] toSingles = explode . fromCSV . lines -- toCSV [8,11,7,10,12] --> "8,11,7,10,12" toCSV :: (Show a) => [a] -> String toCSV = tail . init . show main = do getContents >>= externalSort . toSingles >>= mapM_ (putStrLn . toCSV)