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 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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