[Haskell-cafe] Re: Pattern combinators
David Menendez
dave at zednenem.com
Tue Jan 6 14:58:47 EST 2009
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/>
More information about the Haskell-Cafe
mailing list