11/05/2009
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
.
9/05/2009
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!
UPDATE: I’ve just released v0.9.0 of this package which has a number of sneaky changes and additions, most notably the inclusion of a readDirectoryWithL function that allows for lazy directory reading IO. This will let users work with a DirTree read from disk just as if it was a pure lazy data structure, while IO is done in the background as needed. No more exploding code! (hopefully)