finding sum of tree to list using haskell

Question

I am trying to apply sum using id function while giving input to program.but i am with below. any guidance is much appreciated.

data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving (Eq, Show)
reduce_tree :: Tree a -> (a -> b) -> (b -> a -> b -> b) -> b
reduce_tree (Leaf v) = [v]
reduce_tree (Node left root right) = reduce_tree left ++ [root] ++   reduce_tree right

input as follows:

ghci> reduce_tree (VNode (VLeaf 1) 2 (VNode (VLeaf 3) 4 (VLeaf 5)))
                   id sum
                   where sum t1 v t2 = t1 + v + t2
15

Answer 1

Since I don't understand your question completely, here are some observations:

• reduce_tree's type signature suggests that it should have more arguments than you give it.

  If f is a function that maps values of type a to values of type b, and g is what appears to be an accumulating function of three arguments (although I'm unsure why two are not enough), then

  reduce_tree :: Tree a -> (a -> b) -> (b -> a -> b -> b) -> b
  reduce_tree (Leaf v) f g = ...
  reduce_tree (Node left v right) f g = ...
  

• If reduce_tree is in fact a reduce function, and not one that simply flattens trees into lists, you may draw inspiration from Data.Foldable.

  data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving (Show, Eq)
  
  treefold :: (a -> b -> b) -> b -> Tree a -> b
  treefold f acc (Leaf x) = f x acc
  treefold f acc1 (Node left x right) =
    let acc2 = treefold f acc1 right
        acc3 = f x acc2
        acc4 = treefold f acc3 left
    in acc4
  

  With such a function you can either flatten or sum the elements of a tree:

  flattenTree :: Tree a -> [a]
  flattenTree tree = treefold (:) [] tree
  
  sumTree :: Num a => Tree a -> a
  sumTree tree = treefold (+) 0 tree
  

• The only bell that rings when you say "apply sum using id function" is that perhaps you wish to use continuations. This is already covered thoroughly in e.g. Haskell: tail recursion version of depth of binary tree and concisely in Tail-recursion on trees (Standard ML). A Haskell equivalent would be:

  treefold :: (a -> b -> b) -> b -> Tree a -> b
  treefold f acc tree = tf f acc tree id
    where
      tf f acc (Leaf x) k = k (f x acc)
      tf f acc (Node left x right) old_k = tf f left acc new_k
        where
          new_k = \acc -> tf f right (f x acc) old_k
  

  Now sumTree can be defined in the exact same way as before, except it would use folding as well as the identity function as the initial continuation. Or you could extract the helper function tf to the top-level if you want to feed the traversal function with the function id yourself.

Answer 2

Oh, if I understand correctly, I think you are just trying to enter your example into ghci. I would recommend putting the complexity in the file:

sum_tree :: Tree Int -> Int
sum_tree t = reduce_tree t id sum
    where sum t1 v t2 = t1 + v + t2

then in ghci, after you have loaded the file that sum_tree and reduce_tree are defined in,

ghci> sum_tree (VNode (VLeaf 1) 2 (VNode (VLeaf 3) 4 (VLeaf 5))

If you must do it all in ghci, be aware that you can't use where in ghci usually, since where is only used in definitions. Use let ... in instead:

ghci> let sum t1 v t2 = t1 + v + t2 in reduce_tree (VNode (VLeaf 1) 2 (VNode (VLeaf 3) 4 (VLeaf 5))) id sum

If you for some reason don't want to use let, you can use a lambda:

ghci> reduce_tree (VNode (VLeaf 1) 2 (VLeaf 3)) id (\t1 v t2 -> t1 + v + t2)

Did I understand your question correctly?