Skip to content

Instantly share code, notes, and snippets.

@folkertdev
Created February 17, 2017 19:18
Show Gist options
  • Save folkertdev/f5c4f1dbee7ced69a3e75be8881c6fb5 to your computer and use it in GitHub Desktop.
Save folkertdev/f5c4f1dbee7ced69a3e75be8881c6fb5 to your computer and use it in GitHub Desktop.
Using ST to modify arrays in Haskell
import Control.Monad (replicateM, forM_)
import Data.Ord (comparing)
import qualified Data.Array as Array
import qualified Data.Array.ST as Array.ST
import Control.Monad.ST
import Data.STRef
bsort :: (Ord a, Enum a, Bounded a) => Int -> (e -> a) -> [e] -> [e]
bsort numBuckets toKey items = List.concatMap (List.sortBy (comparing toKey)) $ Array.elems array
where array =
-- convert back into immutable array
Array.ST.runSTArray $ do
-- use ST to contain impure computations (modifying a mutable array)
-- see Data.Array.ST for docs
buckets <- Array.ST.newArray (0, numBuckets - 1) []
forM_ items $ \item -> do
let index = bucket numBuckets (toKey item)
-- there is no Array.ST.modifyArray, sadly
elements <- Array.ST.readArray buckets index
Array.ST.writeArray buckets index (item : elements)
return buckets
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment