On Tue, Dec 27, 2011 at 5:35 AM, Eugene Kirpichov <ekirpic...@gmail.com>wrote:
> I wonder if now this datatype of yours is isomorphic to StreamSummary b
>>> r -> StreamSummary a r.
>>>
>> Not sure what you mean here. StreamSummary seems to be the same as
>> ListConsumer but I don't see how functions from consumers to consumers are
>> list transformers, i.e., functions from lists to lists.
>>
> Well. They are isomorphic, if list transformers are represented as
> functions from lists. I'm assuming they could be with the other
> representation too.
>
> type ListT a b = forall r . ([b] -> r) -> ([a] -> r)
>
I see! I think the type
type ContListTransformer a b = forall r . ListConsumer b r ->
ListConsumer a r
is isomorphic to `ListConsumer a [b]`. Here are the isomorphisms (I did not
check whether they are indeed isomorphisms):
clt2lc :: ContListTransformer a b -> ListConsumer a [b]
clt2lc clt = clt idC
lc2clt :: ListConsumer a [b] -> ContListTransformer a b
lc2clt _ (Done r) = Done r
lc2clt (Done []) (Continue r _) = Done r
lc2clt (Done (b:bs)) (Continue _ f) = lc2clt (Done bs) (f b)
lc2clt (Continue bs f) c =
Continue (consumeList c bs) (\a -> lc2clt (f a) c)
However, `ListTransformer a b` is less expressive because of it's
incremental nature. Every list transformer `t` satisfies the following
property for all `xs` and `ys`:
transformList t xs `isPrefixOf` transformList t (xs++ys)
List *consumers* don't need to follow this restriction. For example, the
consumer
Continue [1] (\_ -> Done [])
which represents the function
nonIncr [] = [1]
nonIncr _ = []
is not incremental in the sense above, because
not (nonIncr [] `isPrefixOf` nonIncr ([]++[0]))
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.
Sebastian
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
