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?<br><br><div class="gmail_quote">On Sun, Dec 21, 2008 at 12:37 AM, David Menendez <span dir="ltr"><<a href="mailto:dave@zednenem.com">dave@zednenem.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d">On Sat, Dec 20, 2008 at 9:34 PM, Jacques Carette <<a href="mailto:carette@mcmaster.ca">carette@mcmaster.ca</a>> wrote:<br>
> Andrew Wagner wrote:<br>
>><br>
>> Wadler posted a blog entry the other day about a paper on pattern-matching<br>
>> in Haskell (<a href="http://wadler.blogspot.com/" target="_blank">http://wadler.blogspot.com/</a>). I've taken a first stab at turning<br>
>> it into actual code for hackage (<a href="http://hpaste.org/13215" target="_blank">http://hpaste.org/13215</a>). There are two<br>
>> commented-out definitions that don't type-check, though, and the types are<br>
>> too wild for me to grok. Anybody have any suggestions for 1.) How to fix it<br>
>> and/or 2.) How to use data/type/newtype to simplify the types and make it<br>
>> more manageable? Thanks!<br>
><br>
> Both errors are because you are using "any" instead of "any'"; you might<br>
> wish to put<br>
> import Prelude hiding any<br>
> at the top of your code, just to avoid such confusion.<br>
<br>
</div>Example 14 also uses (.->.) where it should use (.>.), and it either<br>
needs some more parentheses or some precedence declarations for the<br>
operators.<br>
<div class="Ih2E3d"><br>
> To make the types more readable (but not necessarily more manageable), I<br>
> have made some changes to my version of this code.<br>
<br>
</div>One oddity in the paper is the type of the failure continuations, ()<br>
-> ans. I'm guessing that's left over from an earlier phase of<br>
development. In my own transcription of the library, I eliminated the<br>
() parameter without apparent loss of functionality.<br>
<br>
I think I've managed to work out the structure of the types, which can<br>
mostly be expressed in modern Haskell.<br>
<br>
The matching part of the patterns have this general form:<br>
<br>
type PMatch vec vec' ans = (vec -> ans) -> (() -> ans) -> vec' -> ans<br>
<br>
where vec and vec' are the list of argument types before and after the<br>
subpattern match, and ans is the final answer. (In my code, I just use<br>
ans instead of () -> ans for the failure continuation.)<br>
<br>
This gets us:<br>
<br>
nil :: PMatch vec vec ans<br>
one :: a -> PMatch (a,vec) vec ans<br>
(#) :: PMatch vec vec' ans -> PMatch vec' vec'' ans -> PMatch vec vec'' ans<br>
fail :: PMatch vec vec' ans<br>
catch :: PMatch vec vec' ans -> PMatch vec vec' ans -> PMatch vec vec' ans<br>
<br>
These types are less general than the ones Haskell would infer, but<br>
they do not appear to lose any functionality.<br>
<br>
The currying part of the pattern is less easy to analyze. I've been<br>
able to use type families to relate the curried and uncurried form of<br>
the function types, but I'm working with GHC 6.8, so it's possible<br>
this won't work with the more modern implementations.<br>
<br>
Given the list of argument types and the answer type, generate a<br>
curried function type:<br>
<br>
type family Curry vec ans<br>
type instance Curry () ans = ans<br>
type instance Curry (a,vec) ans = a -> Curry vec ans<br>
<br>
zero, succ zero, and so forth take a function in curried form and<br>
transform it into a function that takes a nested tuple:<br>
<br>
type CurryDigit vec ans = Curry vec ans -> vec -> ans<br>
<br>
zero :: CurryDigit () ans<br>
succ zero :: CurryDigit (a,()) ans<br>
<br>
succ :: CurryDigit vec ans -> CurryDigit (a,vec) ans<br>
succ . succ :: CurryDigit vec ans -> CurryDigit (a,(b,vec)) ans<br>
<br>
So the currying part of the pattern will have the form:<br>
<br>
type PCurry vec vec' ans = CurryDigit vec' ans -> CurryDigit vec ans<br>
<br>
So a pattern has the type,<br>
<br>
type Pattern a vec vec' ans = (PCurry vec vec' ans, a -> PMatch<br>
vec vec' ans)<br>
<br>
where a is the value being examined, vec and vec' are the list of<br>
unbound argument types before and after the match, and ans is the<br>
result.<br>
<br>
var :: Pattern a (a,vec) vec ans<br>
cst :: (Eq a) => a -> Pattern a vec vec ans<br>
pair :: Pattern a vec vec' ans -> Pattern b vec' vec'' ans -><br>
Pattern (a,b) vec vec'' ans<br>
<br>
<br>
Coming from the other side, match takes a value and a case statement<br>
and produces a result:<br>
<br>
type Case a ans = a -> (() -> ans) -> ans -- or just a -> ans -><br>
ans in my code<br>
<br>
match :: a -> Case a ans -> ans<br>
<br>
(|||) combines case statements:<br>
<br>
(|||) :: Case a ans -> Case a ans -> Case a ans<br>
<br>
and (->>) creates them from a pattern and a curried function,<br>
<br>
(->>) :: Pattern a vec () ans -> Curry vec ans -> Case a ans<br>
<br>
Note that (->>) requires the pattern to leave no unbound variables<br>
after matching.<br>
<br>
<br>
Given the way everything is polymorphic in ans, it may be possible to<br>
hide it, but I haven't tried yet.<br>
<div class="Ih2E3d"><br>
<br>
> The principal weakness of these pattern-matching combinators is that there<br>
> is no support for algebraic types, i.e. things like<br>
> data Tree a = Leaf | Branch (Tree a) (Tree a)<br>
> I can see how to use Typeable to deal with that, but is there a simpler way?<br>
<br>
</div>You can define the patterns manually:<br>
<br>
leaf = (id, \v -> case v of { Leaf -> nil; _ -> fail })<br>
<br>
branch p q = (curry_p . curry_q, \v -> case v of { Branch l r -><br>
match_p l # match_q r; _ -> fail})<br>
where<br>
(curry_p, match_p) = p<br>
(curry_q, match_q) = q<br>
<br>
I assume generating these would be pretty straightforward to automate<br>
with Template Haskell.<br>
<font color="#888888"><br>
--<br>
Dave Menendez <<a href="mailto:dave@zednenem.com">dave@zednenem.com</a>><br>
<<a href="http://www.eyrie.org/%7Ezednenem/" target="_blank">http://www.eyrie.org/~zednenem/</a>><br>
</font></blockquote></div><br>