(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