Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
module Instrumented where
import Control.Monad.State
data Counters = Counters
{ swaps :: !Int
, comparisons :: !Int
}
type Instrumented = State Counters
incrSwaps :: Instrumented ()
incrSwaps = do
cnts <- get
put $ cnts { swaps = swaps cnts + 1 }
incrComparisons :: Instrumented ()
incrComparisons = do
cnts <- get
put $ cnts { comparisons = comparisons cnts + 1 }
cmpGT :: Ord a => a -> a -> Instrumented Bool
cmpGT x y = do
incrComparisons
return $ x > y
bubble :: Ord a => [a] -> Instrumented (Bool, [a])
bubble [] = return (True, [])
bubble [x] = return (True, [x])
bubble (x : y : zs) = do
xgty <- cmpGT x y
if xgty
then do
incrSwaps
rec <- snd <$> bubble (x : zs)
return $ (False, y : rec)
else do
fmap (x :) <$> bubble (y : zs)
lastAndInit :: [a] -> (a, [a])
lastAndInit [x] = (x, [])
lastAndInit (x:xs) = (x:) <$> lastAndInit xs
bsort :: Ord a => [a] -> Instrumented [a]
bsort [] = return []
bsort xxs = do
(hasNoSwaps, bubbled) <- bubble xxs
if hasNoSwaps
then return xxs
else do
let (y, ys) = lastAndInit bubbled
next <- bsort ys
return $ next ++ [y]
initialCounters :: Counters
initialCounters = Counters 0 0
bsort' :: Ord a => [a] -> ([a], Counters)
bsort' xs = bsort xs `runState` initialCounters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.