[Haskell-beginners] Re: Applicative functors and trees

[Maciej Piechotka]

On Mon, 2010-03-22 at 11:59 +1030, Darryn Reid wrote:
> Where I'm stuck is with Applicative:
>   class (Functor f) => Applicative f where
>       pure  :: a -> f a
>       (<*>) :: f (a -> b) -> f a -> f b
> 
> I understand that pure lifts a value into the applicative functor, so
> this one is easy:
>     pure = Leaf
> but I cannot see what <*> should look like. I know that <*> is
> essentially application ($) lifted into the functor, so if the functor
> were also a monad then <*> would be liftM2 ($), I suppose. But I want
> a
> "direct" implementation, without monads floating about, but I cannot
> see
> what to do. 

Hmm. When I played with trees I've done:

data Tree a = Leaf | Node (Tree a) a (Tree a)

instance Applicative Tree where
	pure x                          = let t = Node t x t in t
                        -- if you prefer Node (pure x) x (pure x)
                        -- or fix (\t -> Node t x t)
	Leaf         <*> _              = Leaf
	_            <*> Leaf           = Leaf
	(Node l f r) <*> (Node l' v r') =
		Node (l <*> l') (f v) (r <*> r')

So maybe:

instance Applicative Tree where
	pure x                          = let t = Node t x t in t
                        -- if you prefer Node (pure x) x (pure x)
	Empty        <*> _              = Empty
	_            <*> Empty          = Empty
	(Leaf f)     <*> (Leaf v)       = Leaf (f v)
        (Leaf f)     <*> (Node _ v _)   = Leaf (f v)
	(Node _ f _) <*> (Leaf v)       = Lead (f v)
	(Node l f r) <*> (Node l' v r') =
		Node (l <*> l') (f v) (r <*> r')

Both have unpleasant property of function returning infinite tree.

Regards

PS. Why do you need Leaf? How does Leaf x differ from (Node Empty x
Empty)?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: This is a digitally signed message part
Url : http://www.haskell.org/pipermail/beginners/attachments/20100321/cc410130/attachment.bin