CODEWITHSUNDEEP
haskell
pgrosslicht
pgrosslicht

Reputation: 1701

Find the function that produces the largest output in a n-tree

so I have the following tree-like data structure:

data Tree = Node (Int -> Int) Int [Tree]

Basically, every node consists of a label function (Int -> Int), a label Int and a list of sub-trees. Now I want to write a function, that, when given a Tree and an Int, finds the function that would produce the largest output with the given input.

I am able to find the largest output if I apply the function, but I don't seem to be able to find the associated function.

tmax :: Int -> Tree -> Int
tmax l (Node func _ []) = func l
tmax l (Node func _ xs) = max (func l) $ maximum $ map (tmax l) xs

This gives me the largest output that can be produced by any of the functions when applied to l.

Some examples of the the intended function:

t2 = Node (+1) 1 [Node (+5) 2 [], Node (-3) 7 [], Node (\x -> x*x) 4 []]

          (+1) 1
     /-------|-------\
  (+5) 2   (-3) 7   (\x -> x*x) 4

So if I were to apply tmax 4 t2, the answer would be (\x -> x*x), because that would deliver the biggest output. If I were to execute tmax 2 t2, the output would be (+5) because then that would deliver the biggest output. My current function however would only deliver the biggest value, but not the function. So for the first example it would deliver 16, for the second one 7.

Thanks!

Upvotes: 0

Views: 140

Answers (2)

pgrosslicht
pgrosslicht

Reputation: 1701

Well, I was able to do it by writing my own implementations of maximum and max so they return the function and not the value. Then everything worked just fine, thanks!

Upvotes: 1

chi
chi

Reputation: 116139

Here's a hint. Write a binary maximum, first.

bmax :: Int -> Tree -> Tree -> Tree
bmax l t1@(Node f1 _ _) t2@(Node f2 _ _) | f1 l > f2 l = t1
                                         | otherwise   = t2

Then, use recursion to compute the maximum of all the subtrees. You can use a fold for the subtree lists.

Upvotes: 1

Related Questions