Bubble sort with counting swaps and comparsions I have bubble sort code below, which has to count swaps and comparisons of elements. How can it be made more elegant and clear, if it is possible? I think using lots of tuples is not the best way to do this.

bsort' x = bsort (x,0,0)

bsort :: (Ord a) =&gt; ([a], Int,Int) -&gt; ([a], Int, Int) -- (table, nswaps, ncompares)
bsort ([],i,j) = ([], i, j)
bsort (lst, inswp, incmp)
    | hasNoSwaps = (lst, swaps, cmps)
    | otherwise = ((next ++ [last bubbled]), subswaps, subcounts)
    where
        (next, subswaps, subcounts) = bsort ((init bubbled), swaps, cmps)
        (bubbled, hasNoSwaps, swaps, cmps) = bubble (lst, inswp ,incmp)

        bubble :: (Ord a) =&gt; ([a], Int, Int) -&gt; ([a], Bool, Int, Int)
        bubble ([x], i, j) = ([x], True, i, j)
        bubble ((x:y:xs), swaps, cmps)
            | x &gt; y = (y : bubbled_x, False, newswaps_x+1, newcmps_x+1)
            | otherwise = (x : bubbled_y, swaps_y, newswaps, newcmps+1)
            where
                (bubbled_y, swaps_y, newswaps, newcmps) = bubble ((y:xs), swaps, cmps)
                (bubbled_x, swaps_x, newswaps_x, newcmps_x) = bubble ((x:xs), swaps, cmps)
Here's a refactored version using a State monad to handle the threading of the counters.

We start with the type of counters, the notion of being Instrumented (i.e. a computation with counters) and some basic combinators increasing the counters.

import Control.Monad.State

data Counters = Counters
  { swaps       :: !Int
  , comparisons :: !Int
  }

type Instrumented = State Counters

incrSwaps :: Instrumented ()
incrSwaps = do
  cnts &lt;- get
  put $ cnts { swaps = swaps cnts + 1 }

incrComparisons :: Instrumented ()
incrComparisons = do
  cnts &lt;- get
  put $ cnts { comparisons = comparisons cnts + 1 }


We can then write down a comparison operator which records the fact it was called by increasing the appropriate counter:

cmpGT :: Ord a =&gt; a -&gt; a -&gt; Instrumented Bool
cmpGT x y = do
  incrComparisons
  return $ x &gt; y


Using the same idea, we can port your definition of bubble. Two things to be careful about: you need to use do blocks now and you shouldn't forget to call incrSwaps in the branch where you performed a swap:

bubble :: Ord a =&gt; [a] -&gt; Instrumented (Bool, [a])
bubble []  = return (True, [])
bubble [x] = return (True, [x])
bubble (x : y : zs) = do
  xgty &lt;- cmpGT x y
  if xgty
  then do
    incrSwaps
    rec &lt;- snd &lt;$&gt; bubble (x : zs)
    return $ (False, y : rec)
  else do
    fmap (x :) &lt;$&gt; bubble (y : zs)


bsort is not that different (I don't post lastAndInit :: [a] -&gt; (a, [a]) here as it's not important, it's in the gist)

bsort :: Ord a =&gt; [a] -&gt; Instrumented [a]
bsort []  = return []
bsort xxs = do
  (hasNoSwaps, bubbled) &lt;- bubble xxs
  if hasNoSwaps
  then return xxs
  else do
    let (y, ys) = lastAndInit bubbled
    next &lt;- bsort ys
    return $ next ++ [y]


Finally, bsort' corresponds to the combination of an initial state and runState:

initialCounters :: Counters
initialCounters = Counters 0 0

bsort' :: Ord a =&gt; [a] -&gt; ([a], Counters)
bsort' xs = bsort xs `runState` initialCounters