https://codereview.stackexchange.com/questions/183418/bubble-sort-with-counting-swaps-and-comparsions

Instrumented.hs

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