Bubblesort using Writer monad

Question

I still consider myself a newbie to functional programming, and I still have some trouble wrapping my head around a lot of functional concepts. Anyway, here goes:

import Control.Monad.Writer
import Data.Monoid

bubblesort' :: (Ord a) => [a] -> Writer All [a]
bubblesort' (x:y:xs)
  | x > y = tell (All False) >>
    (y:) <$> bubblesort' (x:xs)
  | otherwise =
    (x:) <$> bubblesort' (y:xs)
bubblesort' xs = return xs

bubblesort :: (Ord a) => [a] -> [a]
bubblesort xs
  | ok = ys
  | otherwise = bubblesort ys
  where (ys, All ok) = runWriter (bubblesort' xs)

Answer 1

That's a reasonable implementation if you want to use Writer. Keep in mind that Writer is lazy in the monoid, so you can end up with a space leak.

Also, bubblesort doesn't look at the last element after the first iteration, e.g.

for i = N to 1
  for j = 1 to i - 1                    -- <<
    if data[j] > data[j + 1]
      swap data[j] data[j + 1]

Either way, as an exercise, I suggest you to write bubblesort and bubblesort' without Writer.

Note that Mergesort is a lot simpler to implement in Haskell.