[Haskell-cafe] Pattern combinators

[Jacques Carette]

Andrew Wagner wrote:
> Wadler posted a blog entry the other day about a paper on 
> pattern-matching in Haskell (http://wadler.blogspot.com/). I've taken 
> a first stab at turning it into actual code for hackage 
> (http://hpaste.org/13215). There are two commented-out definitions 
> that don't type-check, though, and the types are too wild for me to 
> grok. Anybody have any suggestions for 1.) How to fix it and/or 2.) 
> How to use data/type/newtype to simplify the types and make it more 
> manageable? Thanks!
Both errors are because you are using "any" instead of "any'"; you might 
wish to put
import Prelude hiding any
at the top of your code, just to avoid such confusion.

To make the types more readable (but not necessarily more manageable), I 
have made some changes to my version of this code.  For example, instead 
of () as the "empty stack", I use
data Void
void = undefined :: Void
in the definition of 'zero' (and thus also in p .>. k).  I also use
data FUnit = FUnit  -- Unit just for fail
Lastly, instead of having a matcher be a pair (which obscures the use of 
pairs as a stack in other places, as well as matching on pairs), I defined
data Matcher a b = Matcher a b
and use that everywhere.

This all makes the types larger to type, but at least there is a cleaner 
separation of concerns, which makes the errors easier to figure out.

The principal weakness of these pattern-matching combinators is that 
there is no support for algebraic types, i.e. things like
data Tree a = Leaf | Branch (Tree a) (Tree a)
I can see how to use Typeable to deal with that, but is there a simpler way?

Jacques