On Sat, Jan 3, 2009 at 4:06 PM, Massimiliano Gubinelli
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