On Tue, Dec 27, 2011 at 7:23 AM, Sebastian Fischer
2011/12/26 Eugene Kirpichov
Whoa. Sebastian, you're my hero — I've been struggling with defining Arrow for ListTransformer for a substantial time without success, and here you got it, dramatically simpler than I thought it could be done (I was using explicit queues).
This stuff is tricky. I noticed that my Applicative instance did not satisfy all required laws. I think I could fix this by changing the implementation of pure to
pure x = Put x $ pure x
in analogy to the ZipList instance. At least, QuickCheck does not complain anymore (I did not write proofs).
The original definition of `pure` was inspired by Chris Smith's post on the connection of Category/Applicative and Arrow:
http://cdsmith.wordpress.com/2011/08/13/arrow-category-applicative-part-iia/
However, even with the fixed Applicative instance, the Arrow instance does not satisfy all laws. ListTransformer seems to be a type that has valid Category and Applicative instances which do not give rise to a valid Arrow instance as outlined by Chris. One of his additional axioms relating Category and Applicative does not hold.
I have extended the (corrected) code with QuickCheck tests:
Thanks, I'll take a look.
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) there :: ([a] -> [b]) -> ListT a b there as2bs bs2r = bs2r . as2bs back :: ListT a b -> ([a] -> [b]) back f = f id
Sebastian
-- Eugene Kirpichov Principal Engineer, Mirantis Inc. http://www.mirantis.com/ Editor, http://fprog.ru/