CODEWITHSUNDEEP
haskelltree
user3487386
user3487386

Reputation: 23

Finding value of binary tree in Haskell

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.

Upvotes: 2

Views: 294

Answers (3)

Sassa NF
Sassa NF

Reputation: 5406

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.

Upvotes: 1

J. Abrahamson
J. Abrahamson

Reputation: 74334

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)

Upvotes: 3

Lee Duhem
Lee Duhem

Reputation: 15121

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

Upvotes: 1

Related Questions