Created
February 17, 2017 19:18
-
-
Save folkertdev/f5c4f1dbee7ced69a3e75be8881c6fb5 to your computer and use it in GitHub Desktop.
Using ST to modify arrays in Haskell
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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