[Haskell-cafe] Re: Pattern combinators

[David Menendez]

On Sat, Jan 3, 2009 at 4:06 PM, Massimiliano Gubinelli
<m.gubinelli at gmail.com> wrote:
>  I've tried to undestand the paper, in particular the relation between
> the combinators written in cps style and combinators written using a
> Maybe type (i.e pattern matching functions returning Maybe to signal
> success or failure).

In your implementation, they are (almost) equivalent.

> newtype PatA a b = PatA {
>  unPatA :: forall ans. (b -> ans) -> ans -> a -> ans
>  }

> newtype PatB a b = PatB { unPatB :: a -> Maybe b }

Specifically, "PatA a b" is isomorphic to "a -> (forall ans. (b ->
ans) -> ans -> ans)" and "forall ans. (b -> ans) -> ans -> ans" is
(mostly) isomorphic to "Maybe b".

maybe :: Maybe b -> (b -> ans) -> ans -> ans
maybe (Just x) f z = f x
maybe Nothing f z = z

unMaybe :: (forall ans. (b -> ans) -> ans -> ans) -> Maybe b
unMaybe f = f Just Nothing

(As usual, seq prevents this from being a true isomorphism, because
maybe (unMaybe _|_) = const (const _|_), and seq allows us to
distinguish _|_ from const _|_.)

I'm not sure which form is preferable. I suspect the continuation
version will do less allocation, but with enough in-lining, GHC can
effectively convert the Maybe version into the continuation version on
its own.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>