On Tue, Dec 27, 2011 at 5:35 AM, Eugene Kirpichov <span dir="ltr">&lt;<a href="mailto:ekirpichov@gmail.com" target="_blank">ekirpichov@gmail.com</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div class="gmail_quote"><div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_quote"><div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div bgcolor="#FFFFFF"><div>I wonder if now this datatype of yours is isomorphic to StreamSummary b r -&gt; StreamSummary a r.</div></div></blockquote></div><div>Not sure what you mean here. StreamSummary seems to be the same as ListConsumer but I don&#39;t see how functions from consumers to consumers are list transformers, i.e., functions from lists to lists.</div>


</div></blockquote></div><div>Well. They are isomorphic, if list transformers are represented as functions from lists. I&#39;m assuming they could be with the other representation too.</div><div><br></div><div>type ListT a b = forall r . ([b] -&gt; r) -&gt; ([a] -&gt; r)</div>

</div></blockquote><div><br></div><div>I see! I think the type</div><div><br></div><div>    type ContListTransformer a b = forall r . ListConsumer b r -&gt; ListConsumer a r</div><div><br></div><div>is isomorphic to `ListConsumer a [b]`. Here are the isomorphisms (I did not check whether they are indeed isomorphisms):</div>

<div><br></div><div><div>    clt2lc :: ContListTransformer a b -&gt; ListConsumer a [b]</div><div>    clt2lc clt = clt idC</div><div>    </div><div>    lc2clt :: ListConsumer a [b] -&gt; ContListTransformer a b</div><div>

    lc2clt _               (Done r)       = Done r</div><div>    lc2clt (Done [])       (Continue r _) = Done r</div><div>    lc2clt (Done (b:bs))   (Continue _ f) = lc2clt (Done bs) (f b)</div><div>    lc2clt (Continue bs f) c              =</div>

<div>      Continue (consumeList c bs) (\a -&gt; lc2clt (f a) c)</div></div><div><br></div><div>However, `ListTransformer a b` is less expressive because of it&#39;s incremental nature. Every list transformer `t` satisfies the following property for all `xs` and `ys`:</div>

<div><br></div><div>    transformList t xs `isPrefixOf` transformList t (xs++ys)</div><div><br></div><div>List *consumers* don&#39;t need to follow this restriction. For example, the consumer</div><div><br></div><div>    Continue [1] (\_ -&gt; Done [])</div>

<div><br></div><div>which represents the function</div><div><br></div><div>    nonIncr [] = [1]</div><div>    nonIncr _  = []</div><div><br></div><div>is not incremental in the sense above, because</div><div><br></div><div>

    not (nonIncr [] `isPrefixOf` nonIncr ([]++[0]))</div><div><br></div><div>I think it is the incremental nature of list transformers that allows them to be composed in lock-step in the Category instance. `lc2clt` above is sequential composition for list *consumers* but it applies the second consumer only after executing the first completely.</div>
<div><br></div><div>Sebastian</div></div>