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.

• Please see What to do when someone answers. I have rolled back Rev 5 → 4. Jul 11 '18 at 17:25
• In my style of learning Haskell, I do not import Data.List and other weird stuff i don't know about. I first learn to operate from its basic primitives this language is so different that importing libraries will only dilute the learning process into chaotic descent Apr 6 '20 at 6:41
• @typelogic: The only function I use from Data.List is sort. This is used in runQuickCheck to make sure that my bubbleSort produces correct output. The testing code stands apart from the code that I wanted to have reviewed. Apr 6 '20 at 8:02

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


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.

• Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. Nov 19 '18 at 9:14

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!

• I tested, this is not working. Apr 6 '20 at 6:38
• Hey @typelogic , can you send the data you are running it on to cause it to not work? I’ll confirm on my side. Apr 7 '20 at 10:34
• asciinema.org/a/EbRRcpmsFexWRn95QpXTq0lmb Apr 7 '20 at 21:01
• Thanks @typelogic you're absolutely correct, I guess what I wrote was a bubblePass, which only handles one pass. I will update it promptly, ideally I will write it with only the one parameter of the list. Apr 7 '20 at 23:33