Hutton 2016 ex8.3a

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Hutton 2016 ex8.3a

trent shipley
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: 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, <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Hutton 2016 ex8.3a

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

How could I modify this definition so that a Node could be:

Node (Tree a) Null/Nothing/[] -- basically a zilch that would match anything or nothing, because it would make programming simple. Alternatively:

Node (Tree a)

-- Would I be looking at,

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

-- Or possibly the best I can do is,

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









On Mon, Sep 3, 2018 at 3:06 AM Rishi Rajasekaran <[hidden email]> wrote:
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, <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners