Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# gallais/Instrumented.hs

Created Dec 22, 2017
 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
to join this conversation on GitHub. Already have an account? Sign in to comment