[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
> "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
More information about the Beginners
mailing list