[Haskell-cafe] ANN: sparsebit 0.5 - Sparse Bitmaps for Pattern Match Coverage

[Ahn, Ki Yung]

sparsebit - Sparse Bitmaps for Pattern Match Coverage
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/sparsebit

This library packages the functional peal paper 'Sparse Bitmaps for
Pattern Match Coverage' submitted to ICFP 2009 by Ki Yung Ahn and Tim
Sheard. You can look up the tutorial-like paper and the talk slides,
which are availabel at:
  http://kyagrd.dyndns.org/wiki/SparseBitmapsForPatternMatchCoverage

Abstract:
  Pattern matching coverage over Algebraic Data Types(ADTs) has most
often been studied in the context of pattern compilation algorithms.
However, it is worth considering the pattern matching coverage problem
in isolation, since general solutions will be independent of the
specifics of any implementation or language.
  We define an intuitive and mathematically well-established bit masking
semantics for pattern match coverage. We design and implement a sparse
bitmap data structure, which realizes this semantics in a compact and
flexible manner. This bitmap data structure supports computing coverage
solutions of large programs incrementally from coverage solutions of
sub-programs. It can also be used as a common data representation for
pattern coverage shared between different tools (e.g., compilers,
linting tools, software analysis tools) that need pattern match coverage
information.


Additional source files Type.hs and TestType.hs packaged with this
library provides the examples and QuickCheck extracted from the paper to
demonstrate how to use this library.

====================================================================
Some additional notes:

Personally, I am very happy to upload my first project on Hackage.  If
you are looking for simple and elegant way of describing pattern match
coverage or testing exhaustiveness of pattern matching, we hope this may
give you a better insight.  This is a reference implementation, but I
think it is still usable to some extent.  One might want to define
monadic version of the library functions and operators since the type
representation in the program analysis tools might be monadic for
implementation reasons (easy to generate fresh type variables) and
performance reasons (to exploit sharing while unification of type
variables).  And in such cases, more optimized implementation of tensor
product may be possible as well.  And there are some other issues
discussed in the paper as well.

I was not able to make the haddock documentation appear in Hackage,
although I have no problem generating documentation using "cabal
haddock" locally.  It would be nice if there is a way to see some
diagnose of warning or error messages why haddock failed on Hackage.

--
  Ahn, Ki Yung