[prev in list] [next in list] [prev in thread] [next in thread] 

List:       haskell-beginners
Subject:    [Haskell-beginners] Re: Applicative functors and trees
From:       Maciej Piechotka <uzytkownik2 () gmail ! com>
Date:       2010-03-22 2:18:41
Message-ID: 1269224320.5411.68.camel () picard
[Download RAW message or body]

[Attachment #2 (multipart/signed)]


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)?


["signature.asc" (application/pgp-signature)]

_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners


[prev in list] [next in list] [prev in thread] [next in thread]