Re: [Haskell-cafe] Pattern combinators

I'd love to see a copy of this go up on hackage for experimentation. Would you care to upload your code, or send it to me so I can upload it? On Sun, Dec 21, 2008 at 12:37 AM, David Menendez wrote:

...

Andrew Wagner wrote:

...

Wadler posted a blog entry the other day about a paper on

On Sat, Dec 20, 2008 at 9:34 PM, Jacques Carette wrote: 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.

Example 14 also uses (.->.) where it should use (.>.), and it either needs some more parentheses or some precedence declarations for the operators.

...

To make the types more readable (but not necessarily more manageable), I have made some changes to my version of this code.

One oddity in the paper is the type of the failure continuations, () -> ans. I'm guessing that's left over from an earlier phase of development. In my own transcription of the library, I eliminated the () parameter without apparent loss of functionality.

I think I've managed to work out the structure of the types, which can mostly be expressed in modern Haskell.

The matching part of the patterns have this general form:

type PMatch vec vec' ans = (vec -> ans) -> (() -> ans) -> vec' -> ans

where vec and vec' are the list of argument types before and after the subpattern match, and ans is the final answer. (In my code, I just use ans instead of () -> ans for the failure continuation.)

This gets us:

nil :: PMatch vec vec ans one :: a -> PMatch (a,vec) vec ans (#) :: PMatch vec vec' ans -> PMatch vec' vec'' ans -> PMatch vec vec'' ans fail :: PMatch vec vec' ans catch :: PMatch vec vec' ans -> PMatch vec vec' ans -> PMatch vec vec' ans

These types are less general than the ones Haskell would infer, but they do not appear to lose any functionality.

The currying part of the pattern is less easy to analyze. I've been able to use type families to relate the curried and uncurried form of the function types, but I'm working with GHC 6.8, so it's possible this won't work with the more modern implementations.

Given the list of argument types and the answer type, generate a curried function type:

type family Curry vec ans type instance Curry () ans = ans type instance Curry (a,vec) ans = a -> Curry vec ans

zero, succ zero, and so forth take a function in curried form and transform it into a function that takes a nested tuple:

type CurryDigit vec ans = Curry vec ans -> vec -> ans

zero :: CurryDigit () ans succ zero :: CurryDigit (a,()) ans

succ :: CurryDigit vec ans -> CurryDigit (a,vec) ans succ . succ :: CurryDigit vec ans -> CurryDigit (a,(b,vec)) ans

So the currying part of the pattern will have the form:

type PCurry vec vec' ans = CurryDigit vec' ans -> CurryDigit vec ans

So a pattern has the type,

type Pattern a vec vec' ans = (PCurry vec vec' ans, a -> PMatch vec vec' ans)

where a is the value being examined, vec and vec' are the list of unbound argument types before and after the match, and ans is the result.

var :: Pattern a (a,vec) vec ans cst :: (Eq a) => a -> Pattern a vec vec ans pair :: Pattern a vec vec' ans -> Pattern b vec' vec'' ans -> Pattern (a,b) vec vec'' ans

Coming from the other side, match takes a value and a case statement and produces a result:

type Case a ans = a -> (() -> ans) -> ans -- or just a -> ans -> ans in my code

match :: a -> Case a ans -> ans

(|||) combines case statements:

(|||) :: Case a ans -> Case a ans -> Case a ans

and (->>) creates them from a pattern and a curried function,

(->>) :: Pattern a vec () ans -> Curry vec ans -> Case a ans

Note that (->>) requires the pattern to leave no unbound variables after matching.

Given the way everything is polymorphic in ans, it may be possible to hide it, but I haven't tried yet.

...

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?

You can define the patterns manually:

leaf = (id, \v -> case v of { Leaf -> nil; _ -> fail })

branch p q = (curry_p . curry_q, \v -> case v of { Branch l r -> match_p l # match_q r; _ -> fail}) where (curry_p, match_p) = p (curry_q, match_q) = q

I assume generating these would be pretty straightforward to automate with Template Haskell.

-- Dave Menendez <http://www.eyrie.org/~zednenem/ http://www.eyrie.org/%7Ezednenem/>