Optimizing radix collation in Haskell

Question

I'm still learning Haskell, and I wrote the following radix sort function. It seems to work correctly, but the problem is that it is rather inefficient in memory. If compiled with ghc, the memory will have more than 500 MB, already containing a list of elements of size 10,000.

Therefore, I want to ask you how the following algorithm / code can be improved to make it more efficient in terms of speed and memory. What is the best place to start?

import System.Random -- radixsort for positive integers. uses 10 buckets radixsort :: [Int] -> [Int] radixsort [] = [] radixsort xs = -- given the data, get the number of passes that are required for sorting -- the largest integer let maxPos = floor ((log (fromIntegral (foldl max 0 xs)) / log 10) + 1) -- start sorting from digit on position 0 (lowest position) to position 'maxPos' radixsort' ys pos | pos < 0 = ys | otherwise = let sortedYs = radixsort' ys (pos - 1) newBuckets = radixsort'' sortedYs [[] | i <- [1..10]] pos in [element | bucket <- newBuckets, element <- bucket] -- given empty buckets, digit position and list, sort the values into -- buckets radixsort'' [] buckets _ = buckets radixsort'' (y:ys) buckets pos = let digit = div (mod y (10 ^ (pos + 1))) (10 ^ pos) (bucketsBegin, bucketsEnd) = splitAt digit buckets bucket = head bucketsEnd newBucket = bucket ++ [y] in radixsort'' ys (bucketsBegin ++ [newBucket] ++ (tail bucketsEnd)) pos in radixsort' xs maxPos -- get an random array given an seed getRandIntArray :: Int -> [Int] getRandIntArray seed = (randomRs (0, div (maxBound :: Int) 2) (mkStdGen seed)) main = do value <- (\x -> return x ) (length (radixsort (take 10000 (getRandIntArray 0)))) print value 

Answer 1

The main problem is your radixsort'' function radixsort'' because ++ is O (n), and it copies every time the list is specified as the first argument.

 pack (-1) r' _ = r' pack nr' relems = let getn = (map snd) . (filter ((n==) . fst)) in pack (n - 1) ((getn relems):r') relems radixsort'' elems pos = let digit = \y -> div (mod y (10 ^ (pos + 1))) (10 ^ pos) relems = zip (map digit elems) elems in pack 9 [] relems