# [Haskell-beginners] Re: Applicative functors and trees

Maciej Piechotka uzytkownik2 at gmail.com
Sun Mar 21 22:18:41 EDT 2010

```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
> 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