title: Optimizing radix sort in Haskell
body: <p>I'm still learning Haskell and I wrote following radix sort function. It seems to work correctly, but the problem is that it is rather memory inefficient. If compiled with ghc, the memory goes highly over 500MB already with input list of size 10000 elements.</p>
  
  <p>So I want to ask you how could the following algorithm/code improved to make it more efficient in terms of speed and memory. What is the best place to start?</p>
  
  <pre><code>import System.Random
  
  -- radixsort for positive integers. uses 10 buckets
  radixsort :: [Int] -&gt; [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 &lt; 0   = ys
           | otherwise = let sortedYs   = radixsort' ys (pos - 1)
                             newBuckets = radixsort'' sortedYs [[] | i &lt;- [1..10]] pos
                         in  [element | bucket &lt;- newBuckets, element &lt;- 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 -&gt; [Int] 
  getRandIntArray seed = (randomRs (0, div (maxBound :: Int) 2) (mkStdGen seed))
  
  main = do
          value &lt;- (\x -&gt; return x ) (length (radixsort (take 10000 (getRandIntArray 0))))
          print value
  </code></pre>