PFP Laboratory 10

Monads

• In your prefered programming language, implement data type

bubbleSort :: Array Int Int -> Array Int Int

ghci> elems $ bubbleSort $  listArray (0,5) [8,4,9,6,7,1] 
[1,4,6,7,8,9]

import Data.Array
import Data.Array.ST
import Control.Monad

bubbleSort :: Array Int Int -> Array Int Int
bubbleSort myArray = runSTArray  $ do
    stArray <- thaw myArray
    let end = (snd . bounds) myArray
    forM_ [1 .. end] $ \i -> do
        forM_ [0 .. (end - i)] $ \j -> do
            val <- readArray stArray j
            nextVal <- readArray stArray (j + 1)
            let outOfOrder = val > nextVal
            when outOfOrder $ do
                writeArray stArray j nextVal
                writeArray stArray (j + 1) val
    return stArray