[Haskell-beginners] Hutton 2016 ex8.3a

[Rishi Rajasekaran]

Hi Trent

For executing your approach, you can do the following:
1. Compute the number of leaves in the left subtree first.
2. Pass that computed value into leaves' call for the right subtree

Regards

Rishi


On Mon, 3 Sep, 2018, 2:36 PM trent shipley, <trent.shipley at gmail.com> wrote:

> Given
> data Tree a = Leaf a | Node (Tree a) (Tree a)
>
> Write a leaf counter.
>
> Hutton suggests:
>
> leaves :: Tree a -> Int
> leaves (Leaf _) = 1
> leaves (Node l r) = leaves l + leaves r
>
> I tried:
>
> leavesTrent :: Tree a -> Int
> leavesTrent = leaves' 0
>          where
>            leaves' n (Leaf a) = n + 1
>            leaves' n (Node l r) = (leaves' n l), (leaves' n r)
>
> The idea is:
>
> If it is a leaf, add one to the accumulator.  (Following Hutton's
> explanation of how sum works if defined with foldl.)   If it is a tree,
> proceed down the left subtree recursively, until you get to a leaf, then
> roll up to the right subtree.  The problem (among the problems) is that I
> don't know how to tell the compiler to do all lefts, before backing up to
> go right.  I only know how to do that using a real operator like "+" or foo
> (l, r).
>
> Is that kind of no-op recursive branching possible?
>
> Trent.
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20180903/0e74b1a7/attachment.html>