---
title: "Software Tools in Haskell: bubble"
subtitle: (bubble)sort lines on stdin
date: 2016-03-10
author: nbloomf
tags: software-tools-in-haskell, literate-haskell
---
As usual, we start with some imports.
> -- sth-bubble: (bubble)sort lines on stdin
> module Main where
>
> import System.Exit (exitSuccess)
> import Data.List (unfoldr)
This is a horrible sorting program which should never be used by anyone. But in the interest of completeness, here it is all the same: bubblesort. Because the bubble sort algorithm is so terrible, I won't bother giving this program useful options (we'll write a for-real sorting tool next).
Some traditional sorting algorithms are a little awkward to write in Haskell due to immutability. The bottom line is that we can't "update" a data structure in place in memory; instead Haskell creates a new copy of the data structure with changes applied. So some simple ideas like "swap the entries at positions $i$ and $j$", essential to efficient implementations of quicksort and shellsort, are difficult to express.
That said, here's my attempt at bubblesort.
> bubble :: (Ord a) => [a] -> [a]
> bubble xs = case accum False [] xs of
> (True, ys) -> bubble ys
> (False, ys) -> ys
> where
> accum p zs (x:y:ys) = if x <= y
> then accum p (x:zs) (y:ys)
> else accum True (y:zs) (x:ys)
> accum p zs ys = (p, reverse $ (reverse ys) ++ zs)
The ``accum`` helper function marches down a list swapping elements which are out of order. It also keeps track of whether or not any swaps are made. Then ``bubble`` applies ``accum`` over and over again until no swaps are made. Interestingly, this makes ``bubble`` linear on lists which are already sorted. And I think (but am not certain) that if each element of the input list is at most $k$ indices out of place that the complexity of ``bubble`` is $\mathcal{O}(kn)$. This is not to say that ``bubble`` is the Right Way to sort things; in my testing it is excruciatingly slow even on small lists (1000 items).
The main program simply applies ``bubble`` to the contents of ``stdin``. Note that since we use the standard ``Ord`` instance for strings, ``bubble`` sorts by unicode code point.
> main :: IO ()
> main = do
> lns <- fmap getLines getContents
> mapM_ putStrLn $ bubble lns
> exitSuccess
Old Stuff
---------
> -- split on \n
> getLines :: String -> [String]
> getLines = unfoldr firstLine
> where
> firstLine :: String -> Maybe (String, String)
> firstLine xs = case break (== '\n') xs of
> ("","") -> Nothing
> (as,"") -> Just (as,"")
> (as,b:bs) -> Just (as,bs)