<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">On 11/20/12 6:21 PM, Steve Severance
wrote:<br>
</div>
<blockquote
cite="mid:CAGhAMHFUS4ej-GciKvhUWH1zsfr=t8xcohHR6v9xAsr14V6aEA@mail.gmail.com"
type="cite">
<div
style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">class
(ReflectDescriptor a, Typeable a, Wire a) => ProtoBuf a </div>
<div
style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)"><br>
</div>
<div
style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<div>data Expression a b where</div>
<div> OpenTable :: (ProtoBuf b) => Int -> Table ->
Expression () b</div>
<div> OpenFile :: (ProtoBuf b) => Int -> String ->
Expression () b</div>
</div>
<div
style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
<div> WriteFile :: (Typeable a, ProtoBuf b) => Int ->
String -> Expression a b -> Expression b ()</div>
<div> WriteTable :: (Typeable a, ProtoBuf b) => Int ->
Table -> Expression a b -> Expression b ()</div>
</div>
<div
style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
Map :: (ProtoBuf a, ProtoBuf b, ProtoBuf c) => Int -> (a
-> b) -> Expression c a -> Expression a b</div>
<div
style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13px;background-color:rgb(255,255,255)">
LocalMerge :: (ProtoBuf a) => Int -> [Expression c a]
-> Expression c a</div>
</blockquote>
We can implement a version of the compos operator like so:<br>
<br>
compos :: forall m c d. (forall a. a -> m a) -> (forall a b. m
(a -> b) -> m a -> m b)<br>
-> (forall e f. Expression e f -> m (Expression e
f)) -> Expression c d -> m (Expression c d)<br>
compos ret app f v = <br>
case v of<br>
OpenTable i t -> ret (OpenTable i t)<br>
OpenFile i s -> ret (OpenFile i s)<br>
Map i g e -> ret (Map i g) `app` f e<br>
WriteFile i s e -> ret (WriteFile i s) `app` f e<br>
WriteTable i t e -> ret (WriteTable i t) `app` f e<br>
LocalMerge i es -> ret (LocalMerge i) `app` mapm f es<br>
where <br>
mapm :: forall g h. (Expression g h -> m (Expression g
h)) -> [Expression g h] -> m [Expression g h]<br>
mapm g = foldr (app . app (ret (:)) . g) (ret [])<br>
<br>
Then, with this in hand, we get all the usual compos variants:<br>
<br>
composOp :: (forall a b. Expression a b -> Expression a b) ->
Expression c d -> Expression c d<br>
composOp f = runIdentity . composOpM (Identity . f)<br>
<br>
composOpM :: (Monad m) => (forall a b. Expression a b -> m
(Expression a b)) -> Expression c d -> m (Expression c d)<br>
composOpM = compos return ap<br>
<br>
composOpM_ :: (Monad m) => (forall a b. Expression a b -> m
()) -> Expression c d -> m ()<br>
composOpM_ = composOpFold (return ()) (>>)<br>
<br>
composOpFold :: b -> (b -> b -> b) -> (forall c d.
Expression c d -> b) -> Expression e f -> b<br>
composOpFold z c f = unC . compos (\_ -> C z) (\(C x) (C y) ->
C (c x y)) (C . f)<br>
newtype C b a = C { unC :: b }<br>
<br>
See Bringert and Ranta's "A Pattern for Almost Compositional
Functions" for more details:
<a class="moz-txt-link-freetext" href="http://publications.lib.chalmers.se/records/fulltext/local_75172.pdf">http://publications.lib.chalmers.se/records/fulltext/local_75172.pdf</a><br>
<br>
In my experience, compos requires a little work, but it can handle
just about any data type or family of data types you throw at it.<br>
<br>
(note the twist on compos is just an extra rank 2 type to quantify
over the "a" and "b" in "Expression a b". The same rank 2 type lets
you write the recursive code almost directly as well [using
polymorphic recursion] -- compos is just a nice generic way to avoid
writing the boilerplate traversal repeatedly).<br>
<br>
Cheers,<br>
Gershom<br>
<br>
</body>
</html>