Finding value of binary tree in Haskell

Question

Code given:

data Tree a b = Leaf a | Branch b [Tree a b] deriving (Eq,Read,Show)

--with these trees defines

t1 = Branch "+" [Leaf 10, Leaf 20, Branch "*" [Leaf 2, Leaf 3, Leaf 4], Leaf 50]

t2 = Branch "*" [t1,t1,t1] //should multiply t1 3 times

How can I find the value of t1? As in, 10 + 20 + (2 * 3 * 4) + 50 = 104

I've started a solve function:

solve (Leaf a) = a 
solve (Branch _ ts) = //not sure how to make it solve itself recursively here.

Any help would be appreciated. Thank you.

Please ask a new question if you want a solution in C#; don't edit this question to change its meaning, since it already has answers. — Blorgbeard
– Blorgbeard, Commented Apr 2, 2014 at 2:27

J. Abrahamson · Accepted Answer · 2014-04-02 01:48:43Z

3

Just call solve recursively. And you may as well create your own type for your operators instead of using strings.

data Op = Plus | Mult

solve :: Tree Int Op -> Int
solve (Leaf a) = a
solve (Branch Plus args) = sum (map solve args)
solve (Branch Mult args) = product (map solve args)

edited Apr 2, 2014 at 1:48

answered Apr 2, 2014 at 1:26

J. Abrahamson

74.8k9 gold badges142 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Lee Duhem Over a year ago

Is prod a typo of product?

user3487386 Over a year ago

Great answer. I understand so much more clearly. Could you elaborate more on what you mean about operators? and what is the data Op = Plus | Mult you included?

Lee Duhem Over a year ago

@user3487386 data Op = ... is a data type definition, just like your data Tree a b = ..., you could use it to indicate which operation you want to perform, just like you use "+" and "*" to indicate the same thing, but the operation type makes the implementation of solve much easier.

Lee Duhem · Accepted Answer · 2014-04-02 01:40:00Z

1

You could try this:

data Tree a b = Leaf a
              | Branch b [Tree a b]
              deriving (Eq,Read,Show)

t1 = Branch '+' [Leaf 10, Leaf 20, Branch '*' [Leaf 2, Leaf 3, Leaf 4], Leaf 50]
t2 = Branch '*' [t1,t1,t1]

solve (Leaf a) = a
solve (Branch op ts) = op' $ map solve ts
        where op' = case op of
                        '+' -> sum
                        '*' -> product

-- testing
main = do
        print $ solve t1
        print $ solve t2

Testing

$ runghc t.hs 
104
1124864

answered Apr 2, 2014 at 1:40

Lee Duhem

15.2k3 gold badges33 silver badges50 bronze badges

2 Comments

user3487386 Over a year ago

This looks great as well but the other commenter gave a more concise answer. I appreciate the variation though! thank you

Lee Duhem Over a year ago

@user3487386 Yeah, defining operator type could make the implementation of solve looks much better.

Sassa NF · Accepted Answer · 2014-04-02 12:23:33Z

1

A generic solution looks like so:

solve (Leaf a) = a
solve (Branch f (t:ts)) = foldl' (\x -> f x . solve) (solve t) ts

Now you only need to map Tree Int String to Tree Int (Int->Int->Int):

mapop (Branch "*" ts) = Branch (*) $ map mapop ts
mapop (Branch "+" ts) = Branch (+) $ map mapop ts
mapop (Leaf x) = Leaf x

So

> print $ solve $ mapop t1
104

But really mapop asks to derive Functor for Tree:

data Tree a b = Leaf a | Branch b [Tree a b] deriving (Eq,Show,Read,Functor)
mapop :: (Num a) => Tree a String -> Tree a (a->a->a)
mapop = fmap f where
  f "+" = (+)
  f "*" = (*)

Note that I am not assuming a Monoid here, because you didn't mention in your question what to do with empty lists in Branch.

edited Apr 2, 2014 at 12:23

answered Apr 2, 2014 at 12:18

Sassa NF

5,41617 silver badges22 bronze badges

Collectives™ on Stack Overflow

Finding value of binary tree in Haskell

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related