Thanks for the reply.  Here's the decomposition I had in mind.  Start with

    type List a = Maybe (a, List a)

Rewrite a bit

    type List a = Maybe (Id a, List a)

Then make the type *constructor* pairing explicit

    type List a = Maybe ((Id :*: List) a)

where

    newtype (f :*: g) a = Prod { unProd :: (f a, g a) }

Then make the type-constructor composition explicit

    type List = Maybe :. (Id :*: List)

(which isn't legal Haskell, due to the type synonym cycle).  From there use the Functor and Applicative instances for composition and pairing of type constructors and for Id.  I think the result is equivalent to ZipList.

To clarify my "cross products" question, I mean fs <*> xs = [f x | f <- fs, x <- xs], as with lists.

Cheers,  - Conal


On Mon, Mar 24, 2008 at 8:36 AM, apfelmus <apfelmus@quantentunnel.de> wrote:
(Sorry for the late reply)

Conal Elliott wrote:
> Is there a known deconstruction of the list/backtracking applicative functor
> (AF)?  If I decompose the list type into pieces (Maybe, product,
> composition), I think I can see where the ZipList AF comes from, but not the
> list/backtracking AF.

So, you mean that the strange thing about the list monad is that the
"natural" applicative structure for [a] is derived from the "composition"

  [a]  ~  Maybe (a, Maybe (a, ...))  ~  Maybe `O` (a,) `O` Maybe `O`
(a,) `O` ...

? Well, this is not quite true since the applicativity you're seeking is
in the extra argument  a , not in the argument of the composition. In
fact, this infinite composition doesn't have an argument (that's the
whole point of taking the fixed point). In other words, every chain like

  Maybe `O` (a,) `O` Maybe `O` (a,)
  Maybe `O` (a,) `O` Maybe `O` (a,) `O` Maybe `O` (a,)

etc. is an applicative functor in its argument, but not necessarily in
a  . So, there is more to the "natural" ZipList AF than  Maybe, product
and composition.

> Is there some construction simpler than lists
> (non-recursive) that introduces cross products?

What do you mean with "cross products" here? Something with

  sequence :: Applicative f => [f a] -> f [a]

being the cartesian product for the list monad? Or simpler

  pure (,) :: Applicative f => (f a, f b) -> f (a,b)

somehow "crossing" the "elements" of  f a  and  f b ?


Regards,
apfelmus

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe