Week 5 progress

What happened to week 4? The power cable for my laptop silently gave up (the first sign of trouble was the melting plastic). It took me a long time to replace it - the first replacement I ordered still hasn't arrived. So instead of coding I spent the week sketching out designs and idea's on paper which actually ended up being really useful.

I'm now in Scotland, for some reason. I'm currently working on, in parallel, tweaking the api (code.haskell.org/gmap/api), writing tests and writing reference implementations on sorted and unsorted association lists. Once I have a really formidable test suite I'll begin converting the ~9000 lines of heavily optimised maps to the new api.

The current Map and OrderedMap classes are a compromise between generality and speed. The classes are huge - 50 or so methods each. I've started with some very neat, general methods like merge and alter as was suggested on the libraries list. I've then added lots of very specific methods like insertMaybe which have default implementations in terms of the general methods. The idea is that you can very quickly produce a working instance and then redefine the faster, more specific methods as necessary.

I'm writing the main part of the test suite as a test against the reference instances. You run a method once with the instance to be tested and once with the reference and check that both produce the same answer (or set of associations). This is a bit fiddly to set up type-wise but I think TestM will come to the rescue again. I'll write more on that later when I've made it less fiddly (and typechecked it) but the basic idea looks like this:

data Compare m1 m2 = forall a b. Eq b => Compare (PolyGen (m1 a) b) (PolyGen (m2 a) b)

checkMethod :: (Map map1 k, Map map2 k, Eq b) => (forall a map. Map map k => PolyGen (map a) b) -> Compare (map1 a) (map2 a)
checkMethod test = Compare test test

runCompare :: Compare m1 m2 -> Gen Bool
runCompare (Compare ma mb) =
a <- unPoly ma
b <- unPoly mb
return (a==b)

The PolyGen monad (which evolved from the test monad of 2 weeks back) is like the Gen monad but additonally can fix the type of class methods. An example might make this clearer:

empty :: Map map k => map a

prop_size_empty :: Map map k => PolyGen (map a) Bool
prop_size_empty = do
mp <- Poly empty
return $ (size empty = 0)

main = do
quickCheck (prop_size_empty :: PolyGen (IntMap Int) Bool)
quickCheck (prop_size_empty :: PolyGen (ListMap OrdMap Char String) Bool)

So now thanks to GADT magic (fiddly, verbose magic :-/ ) we can get test code that looks like:

checkSize :: Map map1 k, Map map2 k => Compare (map1 a) (map2 a)
checkSize = checkMethod $ do
mp <- PolyArb
return $ size mp

comps :: Map map1 k, Map map2 k => [Compare (map1 a) (map2 a)]
comps =
[
....
,checkSize
....
]

type CA map a = [Compare (AssocList a) (map a)]
type CSA map a = [Compare (SortedAssocList a) (map a)]

runComps = mapM (quickCheck . runCompare)

main = do
runComps (comps :: CA IntMap String)
runComps (comps :: CSA IntMap String)
runComps (comps :: CA (OrdMap Int) String)
runComps (comps :: CSA (OrdMap Int) String)
runComps (comps :: CA (ListMap IntMap Int) String)
runComps (comps :: CSA (ListMap IntMap Int) String)
etc ...

What this does is for each instance specified in main and for each test in the list of tests check that the same results are obtained when the test is run in the specified instance, in the AssocList reference instance and in the SortedAssocList reference instance. Which is damn handy, seeing as Adrian already wrote 6 0r 7 more or less working instances and there will be plenty more to follow.

Its a bit complicated and messy. And it would be nicer if I didn't have to keep rerunning the same reference tests against each instance. But I'll get all these wrinkles ironed out as I use it more. The whole thing would be far easier if I could just pass the types as an argument to the testing function. I also need to eventually need to look into testing laziness and strictness properties so I can make sure that

I've decided that I like writing this blog. I've come up with some nice ideas whilst writing progress updates, mostly due to that little twinge of embarrassment that you get when you post manky code.