Increment node values in Tree [Haskell]

Question

I'm trying to implement a haskell program which increments the value of all the nodes in a tree using functors. The input & output of the functor function is a tree. I'm trying to implement it recursively but getting compilation error regarding input parameters.

Haskell Code..

data Tree v = Empty | Node v (Tree v) (Tree v) deriving (Show)

add :: Ord v => v -> Tree v -> Maybe Tree v
add _ Empty = Nothing
add v (Node val left right) = (val + v) ++ add v left ++ add v right

Input

add (+1) (Node 3 (Node 1 Empty Empty) (Node 7 (Node 4 Empty Empty) Empty))

Output

  [1 of 1] Compiling Main             ( functor1.hs, interpreted )

  functor1.hs:17:34: error:
  * Expecting one fewer arguments to `Maybe Tree'
   Expected kind `* -> *', but `Maybe Tree' has kind `*'
  * In the type signature:
    add :: Ord v => v -> Tree v -> Maybe Tree v
       |
 17    | add :: Ord v => v -> Tree v -> Maybe Tree v
       |                                  ^^^^^^^^^^^^

  functor1.hs:17:40: error:
  * Expecting one more argument to `Tree'
    Expected a type, but `Tree' has kind `* -> *'
  * In the first argument of `Maybe', namely `Tree'
   In the type signature:
    add :: Ord v => v -> Tree v -> Maybe Tree v
   |
17 | add :: Ord v => v -> Tree v -> Maybe Tree v
   |                                        ^^^^
 Failed, no modules loaded.

Is there some mistake in the syntax? Please help

Answer 1

I'm trying to implement it recursively but getting compilation error regarding input parameters.

No the errors are already at compile time, so add is never compiled, hence it does not work.

There are some problems with both syntax and semantics, as well as some weird design decisions.

First of all, if you write Maybe Tree v, Haskell sees this as (Maybe Tree) v, which is - as far as I understand it - not the intended result, it should be Maybe (Tree v) since you wrap a Tree v into a Maybe.

But using Maybe (Tree v) as result is already kind of weird: regardless what input treee you provide, we should always construct a new valid Tree. For an Empty we simply do not add any values, so add 3 Empty == Empty, but there are no scenarios where this could go wrong.

You also ue Ord v as a type constraint, which is weird, since in the function, we never use a ==, /=, <, >, etc. function. We use +, which means we should use the Num v, so now our signature is:

add :: Num v => v -> Tree v -> Tree v

We can implement two cases: one for Empty (that stays Empty), and one for Node (that updates the value, and performs two recursive calls), like:

add :: Num v => v -> Tree v -> Tree v
add _ Empty = Empty
add v (Node x l r) = Node (v+x) (add v l) (add v r)

Your question suggests that you want to implement a Functor. Defining an fmap is quite similar to add here, but requires to generalize the first argument. I leave that as an exercise.

If you call it with:

add (+1) (Node 3 (Node 1 Empty Empty) (Node 7 (Node 4 Empty Empty) Empty))

The first argument is not a number, but a function, so you should drop the + in that case:

add 1 (Node 3 (Node 1 Empty Empty) (Node 7 (Node 4 Empty Empty) Empty))

producing:

Prelude> add 1 (Node 3 (Node 1 Empty Empty) (Node 7 (Node 4 Empty Empty) Empty))
Node 4 (Node 2 Empty Empty) (Node 8 (Node 5 Empty Empty) Empty)