fragmentary ideas ䷿ intellectual what-nots ䷷ and haskell programming ䷴

In my boredom, I implemented the toy sorting algorithm called Gnome Sort. It accomplishes backtracking by using a zipper-like system of two lists treated as stacks, and is about 100X slower than GHC’s merge sort on the test I used. It’s also not especially small or simple-looking. It’s basically terrible:

gnomeSort :: (Ord a)=> [a] -> [a]
gnomeSort = sort [] 
      where sort rs     []     = rs 
            sort []     (x:xs) = sort [x] xs
            sort (r:rs) (x:xs) 
                   | x > r     = sort rs (x:r:xs)          
                   | otherwise = sort (x:r:rs) xs

The above doesn’t keep track of where it left off before it began to backtrack, an obvious optimization which turned the algorithm into an insertion sort:

import Data.List (insert)

insertSort :: (Ord a)=> [a] -> [a]
insertSort = sort [] 
       where sort rs []     = rs 
             sort rs (x:xs) = sort (insert x rs) xs

about 60X slower than Data.List.sort
.

I’ve released my first package, up now on hackage (haddock docs should be generated soon). The module provides a simple data structure that mirrors a directory tree, and some useful functions for doing IO on directories of files. You can read more about it here.

It’s very likely there are some bugs, especially related to cross platform issues with file names and paths. The module is also fairly bare, so please send me any requests for functionality that I haven’t thought of, as well as any bugs you might find.

You can install it with:

$ cabal install directory-tree

And get the source with:

$ darcs get http://coder.bsimmons.name/code/DirectoryTree/

I hope this is useful to someone!