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.

• robbie: WIll applying tell or <$> strictly solve the space leak problem?
• Zeta: @robbie0630 no, see stackoverflow.com/questions/7720929/….