[Haskell-beginners] Applicative Functors: Rose Trees with an alternate behavior

[Brent Yorgey]

On Tue, Aug 10, 2010 at 12:49:51AM -0700, Travis Erdman wrote:
> The rose trees implemented in Data.Tree behave in the same way as the applicative style on lists (ie all possible combinations/permutations).  I need a different behavior: one-to-one application.
> 
> instance Applicative Tree where
>     pure x = Node x emptyForest
>     (<*>) (Node f tfs) (Node cargo subtrees) = Node (f cargo) (zipWithForest (<*>) tfs subtrees)

Right, your definition of 'pure' is wrong.  For these sorts of 'zippy'
Applicative instances, pure should create an infinite data structure
containing nothing but the given data element.  For example, take a
look at the Applicative instance for ZipList:

  instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ...

Why is this?  Note that since <*> matches up two structures pointwise,
the shape of the result is necessarily the intersection of the shapes
of the two inputs.  In order for laws like

  pure id <*> v = v

to be satisfied, pure must create a structure which is "as large as
possible" so that v does not get truncated.  This is what was
happening in your example -- since your implementation of 'pure' just
created a one-element tree, the result of your call to sequenceA was
getting truncated to this shape.

The correct implementation of pure looks like this:

  pure x = Node x (repeat (pure x))

(Hooray for lazy infinite data structures!) With this definition the
standard sequenceA works just fine.

-Brent