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)


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.

• WIll applying tell or <\$> strictly solve the space leak problem? Commented Nov 26, 2017 at 16:16
• @robbie0630 no, see stackoverflow.com/questions/7720929/….
– Zeta
Commented Nov 26, 2017 at 20:21