Abstracting Bubblesort

In my August 4th entry I conjectured that monads might be a good way to abstract away the question of whether a bubblesort was done over time or laid out across memory as a sequence of permutations.

I thought that was a good exercise for me to brush up on Haskell monads, so here's the program I wrote. It's "literate haskell", so you can take this whole posting, save it as an whatever.lhs, and it should compile.

I especially relied on a monad tutorial at A Neighborhood of Infinity, that Sigfpe happened to post just as I was in need of it. Thanks, Sigfpe!

I'll be using the State, List, and IO monads.  Eek, trial by fire.
To start with, State has to be imported:

>import Control.Monad.State

So here's my generic bubblesort to start out with.  It sets everything
up without actually having the list available yet; all it needs is the
length for now.

The cf and swap parameters are functions that compare and swap elements,
respectively.  Actually, they just take the indexes of the element(s)
and return a function which will be responsible for testing and permuting
anything the caller wants, however they want.  cf x y should compare elements
x and y (whatever that may mean), and swap x should swap the xth and (x+1)th
elements.

So this function cycles through pairs of adjacent indices in bubblesorty
fashion, and builds a list of functions, each of which is responsible
for testing, and maybe swapping, a pair of elements, with those 
user-supplied comparison and swapping functions.

>bubblesort cf swap theLen = do
>                       i <- reverse [0..theLen]
>                       j <- [0..(i-2)]
>                       [do
>                            i <- cf j (j+1)
>                            if i
>                                 then swap j 
>                                 else return ()]

Now here's a simple comparison function: it assumes that the 
list will be just an ordinary list, with elements instances of
Ord (so that > works).  What it returns is (State [a] Bool),
which is actually another function, taking one list [a]
and returning the same unchanged list [a] and a Boolean.

>cf1 :: Ord a => Int -> Int -> (State [a] Bool)
>cf1 i j = do
>            ls <- get
>            return $ (ls!!i) > (ls!!j)

And here's the corresponding swap function.  It returns a
function which takes a list, and returns a list with the
jth and (j+1)th elements swapped.

>swap1 :: Int -> (State [a] ())
>swap1 j = do
>            theList <- get
>            put $ (take j theList) ++ 
>                 [theList!!(j+1)] ++ [theList!!j] ++ drop (j+2) theList

Let's look at another pair of swapping/comparison functions,
before putting everything together:

This set has a more complicated state -- it's an ordered pair,
of the current permutation [a], and a list of strings [[Char]]
representing the Plinko toy that 
would produce the sort so far.

>cf2 :: Ord a => Int -> Int -> (State ([a],[[Char]]) Bool)
>cf2 i j = do
>            (theList, history) <- get
>            return $ (theList!!i) > (theList!!j)

And here's the corresponding swap function:

>swap2 j = do
>            (theList, history) <- get
>            let newList = (take j theList) 
>                          ++ [theList!!(j+1)] 
>                          ++ [theList!!j] 
>                          ++ drop (j+2) theList in
>                let newHistory = (( (replicate j '|') 
>                              ++ "><" 
>                              ++ (replicate ((length theList)-j-1) '|')) 
>                                  : history) in
>                    put (newList, newHistory)

In this second example, the state is more than just the
list, so we need a function to create the original ([a], [[Char]])
structure:

>buildstate2 :: [a] -> ([a], [[a]])
>buildstate2 a = (a, [[]])

And one to get our plinko toy out after we're done sorting:

>getresult2 :: (Show a) => ([a], [[a]]) -> [Char]
>getresult2 (_, b) = foldl (++) "" $ map (\b -> "\n" ++ show(b) ) b

I skipped the equivalent functions before for the straightforward
sorting example because they are straightforward:

>buildstate1 :: [a] -> [a]
>buildstate1 a = a
 
>getresult1 :: (Show a) => [a] -> [Char]
>getresult1 a = show a

So now we're ready to call this contraption.  dosort takes
the four functions that relate to our state: buildstate, getresult,
swap, and cf; along with the string to be sorted (I call it string,
but it could have been a list of anything in Ord, really).

The "sequence" function links up that list of functions that
bubblesort created, and execState is what runs them, when supplied
with the output of buildstate.

>dosort buildstate cf swap getresult string = 
>           let sorter = bubblesort cf swap $ length string in
>               getresult $ execState (sequence sorter) (buildstate string)

Here are some test functions which call both suites on the same string:

>test1 = dosort buildstate1 cf1 swap1 getresult1 "sambangu!"
>test2 = dosort buildstate2 cf2 swap2 getresult2 "sambangu!"
>
>main = do
>        putStrLn test1
>        putStrLn test2

I'm certain I'm not doing this in a very elegant way. It appears that those four characteristic functions belong together in a class declaration, and somehow different execution types would be instances of that class, but I was unable to get it to compile that way. Could be my syntax was wrong, or more likely, fuzzy thinking, which Haskell seems to be pretty (justifiably) intolerant of.