<div class="gmail_quote">On Tue, Aug 30, 2011 at 4:53 PM, Sebastian Fischer <span dir="ltr">&lt;<a href="mailto:fischer@nii.ac.jp">fischer@nii.ac.jp</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
I think the idea of functional lists is that the monoids of &#39;lists&#39;<br>
and &#39;functions on lists&#39; are isomorphic with isomorphisms toFList and<br>
toList:<br>
<br>
    toFList [] = id<br>
    toFList (xs++ys) = toFList xs . toFList ys<br>
<br>
    toList id = []<br>
    toList (f . g) = toList f ++ toList g<br></blockquote></div><br>Oh absolutely, but my point (if you will pardon the pun), was that just given the type<br><br>newtype FList a = FL ([a] -&gt; [a])<br>runFList (FL f) = f<br>
<br>and the law<br><br>runFList fl as = runFList fl [] ++ as<br><br>we can prove that<br><br>fmap f fl = FL $ \bs -&gt; map f (runFList fl []) ++ bs<br><br>is a valid functor instance:<br><br>fmap id<br>(eta expand) = \fl -&gt; fmap id fl<br>
(apply fmap) = \fl -&gt; FL $ \bs -&gt; map id (runFList fl []) ++ bs<br>(map law) = \fl -&gt; FL $ \bs -&gt; id (runFList fl []) ++ bs<br>(apply id) = \fl -&gt; FL $ \bs -&gt; runFList fl [] ++ bs<br>(FList law) = \fl -&gt; FL $ \bs -&gt; runFList fl bs<br>
(eta reduce) = \fl -&gt; FL $ runFList fl<br>(constructor of destructor) = \fl -&gt; fl<br>(unapply id) = \fl -&gt; id fl<br>(eta reduce) = id<br><br>We don&#39;t need to know that FList is supposed to represent an isomorphism to/from lists, although you can derive one, as you&#39;ve shown.  I just wanted to show that it&#39;s a valid functor, but only if you assume an extra law on the type.  The functor instance depends critically on converting back to a list which requires that law.<br>
<br>There&#39;s no functor instance for this type that doesn&#39;t convert back to a list, which is unfortunate, because you lose the performance benefits of constant-time append!<br><br>  -- ryan<br>