Bubble sort in Haskell

Question

The following code is part of my practice in implementing algorithms in Haskell. I'm aware that bubble sort is a bad choice for sorting sequences in real applications.

import Test.QuickCheck
import Data.List (sort)

-- Going from left to right, swaps two adjacent elements if they are not in order.
-- After the first go, the largest element in the list has bubbled up to the end
-- of the list. In the next go, we start swapping from the first element to the
-- penultimate element and so forth.
bubbleSort :: Ord a => [a] -> [a]
bubbleSort xs = go xs (length xs -1)
  where go xs limit | limit > 0 = let swapped = swapTill xs limit in
                                  go swapped (limit -1)
                    | otherwise = xs

-- Swaps adjacent elements in a list if they are not in order, until a limit.
-- After this, the largest elements, from limit to (length xs),
-- are sorted at the list's end.
swapTill :: (Ord a, Num p) => [a] -> p -> [a]
swapTill xs limit = go xs 0
  where go xs count | count < limit = swap xs
                    | otherwise = xs
                      where swap [x] = [x]
                            swap (x:y:xs) | x < y     = x : (go (y:xs) (count +1))
                                          | otherwise = y : (go (x:xs) (count +1))

-- Tests
bubbleSortWorks :: [Int] -> Bool
bubbleSortWorks xs = bubbleSort xs == sort xs

runQuickCheck = quickCheck bubbleSortWorks

I'd very much appreciate hints on how to make this implementation shorter (maybe using a fold) and/or more readable.

Answer 1

Here's your shortening including a fold.

bubbleSort :: Ord a => [a] -> [a]
bubbleSort xs = foldr swapTill xs [1..length xs-1]

swapTill :: Ord a => Int -> [a] -> [a]
swapTill 0 = id
swapTill count = \(x:y:xs) -> min x y : swapTill (count-1) (max x y:xs)

Reordering the swaps to sort a growing suffix of the list banishes Int.

bubbleSort :: Ord a => [a] -> [a]
bubbleSort = foldr swapTill []

swapTill x [] = [x]
swapTill x (y:xs) = min x y : swapTill (max x y) xs

Answer 2

Below is my attempt to arriving at a more readable and more elegant bubble sorting in Haskell:

main = undefined 

doit []  = []
doit [x] = [x]
doit (x:xs) | x > head xs = head xs:doit (x:tail xs)
            | otherwise = x:doit xs 

bubbleSort xs = foldl (\acc e -> doit acc) xs xs

You requested a shorter version, so the above is short. You requested the use of fold, so the above uses fold. I personally approach Haskell as like doing an mathematical algebra. No redundant formulas, and strive for the most minimal, most readable.

Answer 3

Edited my answer, thank you again to @typelogic for pointing out that my original only worked for a single pass. And since fixing it would have made my answer too close to his original posting, I decided to switch it up to make it a more readable version for beginners!

bubbleUp :: (Ord a) => [a] -> [a]
bubbleUp [] = []
bubbleUp [x] = [x]
bubbleUp (x:y:xs) = smaller : bubbleUp (larger : xs)
  where
    smaller = min x y
    larger = max x y

bubbleSort :: (Ord a) => [a] -> [a]
bubbleSort l = foldl (\acc _ -> bubbleUp acc) l [0 .. length l]

The fold uses the list to be sorted as the accumulator, and each iteration it will do a single bubbleUp, and the acc gets "passed on" to get bubbled up on again. This happens length l times to really make sure each item is where it belongs.

I challenge you to speed it up, there are early exit conditions for bubbleSort (namely a single pass with no swaps), and you can shrink down the search space as items get sorted!