[Haskell-cafe] Re: deconstruction of the list/backtracking applicative functor?

[Conal Elliott]

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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080324/a7d43329/attachment.htm