Foundations

The code described here is mainly simple stuff, but which is used throughout the more advanced stuff.

module MergeSort

MergeSort.hs
mergeSort is the most efficient sorting algorithm for functional languages (that I know of). The implementation is based on the one in Rabhi, Lapalme, Algorithms: A Functional Programming Approach.

module RedBlackTree

RedBlackTree.hs
I use red-black trees for sets and finite maps, including arrays. The implementation is based on the one in Okasaki, Purely Functional Data Structures, with enhancements by Stefan Kahrs (a delete function). Main functions are:
Exports
data RedBlackTree a - the type of a red-black tree over type a. Type a must be an instance of Ord.
rbempty :: RedBlackTree a - the empty red-black tree
rbisempty :: RedBlackTree a -> Bool - test whether a red-black tree is empty
rbinsert :: Ord a => RedBlackTree a -> a -> RedBlackTree a - insert an element into a red-black tree
rbmember :: Ord a => a -> RedBlackTree a -> Bool - test whether an element is a member of a red-black tree
rbdelete :: Ord a => RedBlackTree a -> a -> RedBlackTree a - delete an element from a red-black tree
rblookup :: Ord k => RedBlackTree (k,a) -> k -> Maybe a - look up the value associated to a key in a red-black tree
rbupdate :: Ord k => RedBlackTree (k,a) -> (k,a) -> RedBlackTree (k,a) - update the value associated to a key in a red-black tree
rbdeleteat :: Ord k => RedBlackTree (k,a) -> k -> RedBlackTree (k,a) - delete the value associated to a key in a red-black tree
rbtolist :: RedBlackTree a -> [a] - convert a red-black tree to a list
rbfromlist :: Ord a => [a] -> RedBlackTree a - convert a list to red-black tree
There are a few other useful functions - see the code for details

module MathsPrimitives

MathsPrimitives.hs
This module is a collection of "low-level" functions which are used by the implementations of vector, matrix, polynomial etc.

module QQ

QQ.hs
My implementation of the rationals. The only real difference between this and the implementation in the Haskell Prelude is the show function. (Also, I don't provide a :% constructor - I prefer to just write 3/5, say, and provide a type annotation if necessary to make sure Haskell interprets it as a rational.)
Exports
data QQ

module FF

FF.hs
Finite fields. This code only implements fields of prime order. (I have code for fields of prime power order, but it's a bit messy.) Exports
data FF
FF is defined as an instance of Num and Fractional, so +, -, *, / all work.
(%) :: Integer -> Integer -> FF - n % p constructs the element n in the field Fp, for example
Examples
4 % 5 creates the element 4 in the field F5

module UPoly

UPoly.hs
Univariate polynomials.
Exports
data UPoly a = UP [a] - the type of univariate polynomials, for which the arithmetic operations +, -, * are defined
x = UP [0,1] :: UPoly QQ
derivUP f returns the derivative of f with respect to x
evalUP f a returns f evaluated at a
Examples
derivUP (x^2+1) returns 2x
evalUP (x^2+1) 5 returns 26