-------------------- review 3 --------------------

PAPER: 8
TITLE: Functional Pearl: Sparse Bitmaps for Pattern Match Coverage
 
OVERALL RATING: -2 (strong reject) 
REVIEWER'S CONFIDENCE: 4 (expert) 
Novelty: 2 (Average)

----------------------- REVIEW --------------------

The paper describes an algorithm for checking pattern match coverage using
expandable bit masks. The first half of the paper describes a simply typed
version where the types of the pattern are represented as data being passed
around. This part is quite good.
However, in the second half of the paper a failed attempt is made at reflecting
the types of the patterns as Haskell types, allowing matching against
polymorphic patterns. This implementation is poorly explained and it seems like
the authors haven't fully understood why it isn't working. In fact, it is quite
possible to make it work (see below).
This could be a very nice paper if the second half were rewritten.
Making it work:

> type family   Expand t
> type instance Expand ()         = Nil
> type instance Expand (a, b)     = ExpandPair (Expand a) (Expand b)
> type instance Expand Bool       = () ::: () ::: Nil
> type instance Expand (Maybe a)  = () ::: a ::: Nil
> type instance Expand [a]        = () ::: (a, [a]) ::: Nil
> type instance Expand (Tuple xs) = xs
> type family   ExpandPair as bs
> type instance ExpandPair as         Nil        = as
> type instance ExpandPair Nil        (b ::: bs) = b ::: bs
> type instance ExpandPair (a ::: as) (b ::: bs) = Cross (a ::: as) (b ::: bs)
> type family   Cross as bs
> type instance Cross Nil        bs = Nil
> type instance Cross (a ::: as) bs = Tuple (Map ((,) a) bs) ::: Cross as bs
> type family   Map (f :: * -> *) xs
> type instance Map f Nil        = Nil
> type instance Map f (x ::: xs) = f x ::: Map f xs
> data Tuple xs
> data Bit t where
>   O  :: Bit t
>   I  :: Expandable t => Bit t
>   Bs :: BList (Expand t) -> Bit t
> data Nil
> data x ::: xs
> data BList ts where
>   Nil   :: BList Nil
>   (:::) :: Expandable t => Bit t -> BList ts -> BList (t ::: ts)
> class Expandable t where
>   expand :: Bit t -> BList (Expand t)
> instance (Expandable a, Expandable b) => Expandable (a, b) where
>   expand (I :: Bit (a, b)) =
>     expandPair (undefined :: (a, b))
>                (\_ _ -> I) (expand (I :: Bit a)) (expand (I :: Bit b))
> expandPair :: forall a b. (Expandable a, Expandable b) =>
>               (a, b) -> -- for unification purposes
>               (forall x y. (Expandable x, Expandable y) => Bit x -> Bit y -> Bit (x, y)) ->
>               BList (Expand a) -> BList (Expand b) -> BList (Expand (a, b))
> expandPair _ pair as         Nil        = as
> expandPair _ pair Nil        (b ::: bs) = b ::: bs
> expandPair _ pair (a ::: as) (b ::: bs) = crossB (a ::: as) (b ::: bs)
>   where
>     crossB :: BList xs -> BList ys -> BList (Cross xs ys)
>     crossB Nil        ys = Nil
>     crossB (x ::: xs) ys = Bs (mapB x ys) ::: crossB xs ys
>     mapB :: Expandable x => Bit x -> BList ys -> BList (Map ((,) x) ys)
>     mapB x Nil        = Nil
>     mapB x (y ::: ys) = pair x y ::: mapB x ys
> (|*|) :: forall t u. (Expandable t, Expandable u) => Bit t -> Bit u -> Bit (t, u)
> O     |*| _     = O
> _     |*| O     = O
> I     |*| I     = I
> I     |*| Bs ys = case expand (I :: Bit t) of
>                     Nil -> Bs (cast ys)
>                     xs  -> Bs xs |*| Bs ys
>   where
>     cast :: BList bs -> BList (ExpandPair Nil bs)
>     cast Nil        = Nil
>     cast (b ::: bs) = b ::: bs
> Bs xs |*| I     = case expand (I :: Bit u) of
>                     Nil -> Bs xs
>                     ys  -> Bs xs |*| Bs ys
> Bs xs |*| Bs ys = Bs (expandPair (undefined :: (t, u)) (|*|) xs ys)