[Haskell-cafe] Pattern combinators

[Andrew Wagner]

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 <dave at zednenem.com> wrote:

> On Sat, Dec 20, 2008 at 9:34 PM, Jacques Carette <carette at mcmaster.ca>
> wrote:
> > 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.
>
> 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 <dave at zednenem.com>
> <http://www.eyrie.org/~zednenem/ <http://www.eyrie.org/%7Ezednenem/>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081221/bd9f2468/attachment.htm