Thanks for the reply.&nbsp; Here&#39;s the decomposition I had in mind.&nbsp; Start with<br><br>&nbsp;&nbsp;&nbsp; type List a = Maybe (a, List a)<br><br>Rewrite a bit<br><br>&nbsp;&nbsp;&nbsp; type List a = Maybe (Id a, List a)<br><br>Then make the type *constructor* pairing explicit<br>
<br>&nbsp;&nbsp;&nbsp; type List a = Maybe ((Id :*: List) a)<br><br>where<br><br>&nbsp;&nbsp;&nbsp; newtype (f :*: g) a = Prod { unProd :: (f a, g a) }<br><br>Then make the type-constructor composition explicit<br><br>&nbsp;&nbsp;&nbsp; type List = Maybe :. (Id :*: List)<br>
<br>(which isn&#39;t legal Haskell, due to the type synonym cycle).&nbsp; From there use the Functor and Applicative instances for composition and pairing of type constructors and for Id.&nbsp; I think the result is equivalent to ZipList.<br>
<br>To clarify my &quot;cross products&quot; question, I mean fs &lt;*&gt; xs = [f x | f &lt;- fs, x &lt;- xs], as with lists.<br><br>Cheers,&nbsp; - Conal<br><br><br><div class="gmail_quote">On Mon, Mar 24, 2008 at 8:36 AM, apfelmus &lt;<a href="mailto:apfelmus@quantentunnel.de">apfelmus@quantentunnel.de</a>&gt; wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">(Sorry for the late reply)<br>
<div class="Ih2E3d"><br>
Conal Elliott wrote:<br>
&gt; Is there a known deconstruction of the list/backtracking applicative functor<br>
&gt; (AF)? &nbsp;If I decompose the list type into pieces (Maybe, product,<br>
&gt; composition), I think I can see where the ZipList AF comes from, but not the<br>
&gt; list/backtracking AF.<br>
<br>
</div>So, you mean that the strange thing about the list monad is that the<br>
&quot;natural&quot; applicative structure for [a] is derived from the &quot;composition&quot;<br>
<br>
 &nbsp; [a] &nbsp;~ &nbsp;Maybe (a, Maybe (a, ...)) &nbsp;~ &nbsp;Maybe `O` (a,) `O` Maybe `O`<br>
(a,) `O` ...<br>
<br>
? Well, this is not quite true since the applicativity you&#39;re seeking is<br>
in the extra argument &nbsp;a , not in the argument of the composition. In<br>
fact, this infinite composition doesn&#39;t have an argument (that&#39;s the<br>
whole point of taking the fixed point). In other words, every chain like<br>
<br>
 &nbsp; Maybe `O` (a,) `O` Maybe `O` (a,)<br>
 &nbsp; Maybe `O` (a,) `O` Maybe `O` (a,) `O` Maybe `O` (a,)<br>
<br>
etc. is an applicative functor in its argument, but not necessarily in<br>
a &nbsp;. So, there is more to the &quot;natural&quot; ZipList AF than &nbsp;Maybe, product<br>
and composition.<br>
<div class="Ih2E3d"><br>
&gt; Is there some construction simpler than lists<br>
&gt; (non-recursive) that introduces cross products?<br>
<br>
</div>What do you mean with &quot;cross products&quot; here? Something with<br>
<br>
 &nbsp; sequence :: Applicative f =&gt; [f a] -&gt; f [a]<br>
<br>
being the cartesian product for the list monad? Or simpler<br>
<br>
 &nbsp; pure (,) :: Applicative f =&gt; (f a, f b) -&gt; f (a,b)<br>
<br>
somehow &quot;crossing&quot; the &quot;elements&quot; of &nbsp;f a &nbsp;and &nbsp;f b ?<br>
<br>
<br>
Regards,<br>
apfelmus<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br>