1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.