Optimización del orden de radix en Haskell

Question

Todavía estoy aprendiendo Haskell y escribí la siguiente función de clasificación de radix. Parece que funciona correctamente, pero el problema es que es bastante ineficiente en la memoria. Si se compila con ghc, la memoria supera ampliamente los 500MB con una lista de entrada de elementos de tamaño 10000.

Así que quiero preguntarle cómo podría mejorarse el siguiente algoritmo/código para hacerlo más eficiente en términos de velocidad y memoria. ¿Cuál es el mejor lugar para comenzar?

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

El principal problema es su función radixsort'', porque ++ es O (n) y se copia cada vez que la lista dada como primer argumento.

pack (-1) r' _ = r' 
pack n r' 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