map a function to a Tree in haskell

Question

We can define a binary tree as such:

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

Now I've got a function, say (+), how could I map it to a binary tree? How could I map an arbitrary function to a binary tree?
So (+) a b will be

Node (+) a (Node (+) Empty Empty) (Node a Empty Empty))  

This is a homework which asks us to map a function to a tree and the above is how I understand it.
The function declaration could be:

 functionToTree :: (t1 -> t2) -> Tree a

I'm held up at defining a function type whose number of arguments are variable.

EDIT: Sorry, as nponeccop said, I misunderstood my task and I knew how to writefunctionToTree :: (a -> b) -> Tree a -> Tree b. Despite that I'm still curious about my original question. To clarify a bit, here is what I've been thinking:

                      (+) a 
                        /  \
                      (+)   a

As for a function f taking three parameters a b c:

                     f a b 
                      /   \
                    f a    b
                    /  \
                   f    a

Ok, this is no longer about my homework. I just wonder whether it is possible to write such a function. We can define a list in such way:

data Li a = Cons a (Li a)
          | Empty
          deriving (Show, Eq, Order)

Is it possible to define a general function like that? If you think my question makes no sense then please down vote it.

MORE: I've refined my question. I think my tree is another way to illustrate partial function and curry.

Answer 1

Given a functional data structure (in this case, a Tree), there are usually two general things you can do with it.

1. map
2. fold

Mapping is where you take a function f :: a -> b, and a structure origTree :: Tree a, and apply the function to the elements of the structure, resulting in newTree :: Tree b. (Note that the canonical way to make a structure mappable is to make it a Functor, and define fmap)

Folding is where you somehow compound all elements of the structure into some new value. When you said you had a Tree and the (+) function, I immediately thought of a fold: summing all the elements in the tree. (Note that the canonical way to make a structure foldable is to make it an instance of Foldable (surprise!) and define foldMap or foldr)

However, it appears your homework task is to define a mapping function for your tree.

---

Now, regarding your own question, turning a function into a tree. It is a bit unclear what exactly you mean by putting a, b, and c into your tree, but let's play with the idea a bit. For the sake of simplicity, I'm not going to make a completely generic function. Also, since your function "trees" are rather lopsided, I'm calling them a FunHistory instead of a Tree. This will represent a history of function applications.

data FunHistory a b = Result b (FunHistory a b)
                    | Application (a -> FunHistory a b) a (FunHistory a b)
                    | Base (a -> FunHistory a b)

Now this type is a bit weird. Result contains a result of type b, as well as a link to the previous history of function applications. Base contains a function with no history of function applications, and the capability of producing a future history if a value of type a is supplied. Application, then, is an intermediate record, which provides the capability of producing a future history, as well as noting a past history, and which value was applied to that past history.

Now let's make some functions for convenience. Strap on your seat belt, this could get bumpy.

mkHist :: (a -> b) -> FunHistory a b
mkHist f = let h = Base (\x -> Result (f x) h) in h

Given a single-argument function, we can create a history out of it by...magic. This particular flavor of magic is called "laziness" and "recursive let".

Let's move on and create a function that will take a FunHistory and an input value, and move the history along. Sadly, this is not a total function; it is undefined for the Result type of a FunHistory.

-- The caller should make sure it isn't a `Result` type before using this function
app :: a -> FunHistory a b -> FunHistory a b
app x (Result _ _)        = undefined
app x (Application f _ _) = f x
app x (Base f)            = f x

This is fine and dandy for single-argument functions, but the intermediate Application constructor is never needed for such simple cases. Let's try creating a smart-constructor for a 2-argument function:

mkHist2 :: (a -> a -> b) -> FunHistory a b
mkHist2 f = let h = Base (\x -> mkHist' f x h)
            in h

mkHist' f x h = let h' = Application (\y -> Result (f x y) h') x h
                in h'

Let's try it for a 3-argument function now:

mkHist3 :: (a -> a -> a -> b) -> FunHistory a b
mkHist3 f = let h = Base (\x -> mkHist2' f x h)
            in h

mkHist2' f x h = let h' = Application (\y -> mkHist' (f x) y h') x h
                 in h'

Now a 4-argument function:

mkHist4 :: (a -> a -> a -> b) -> FunHistory a b
mkHist4 f = let h = Base (\x -> mkHist3' f x h)
            in h

mkHist3' f x h = let h' = Application (\y -> mkHist2' (f x) y h') x h
                 in h'

Well look at that; these functions look almost exactly like mkHist3 and mkHist2' respectively! The next step from here would be to generalize these functions into a typeclass, so that it scales to functions with arbitrary numbers of inputs. The catch is that all the inputs must have the same type.

[warning: this code is untested, but I'm somewhat sure it's mostly correct...ish]

instance (Show a, Show b) => Show (FunHistory a b) where
  show (Base _) = "base"
  show (Application _ x h) = "app " ++ show x ++ ", " ++ show h
  show (Result r h) = "result: " ++ r ++ ", " ++ show h

Answer 2

You didn't understand the task well. Mapping a function over a tree is applying the function to each data element contained in the tree.

I suggest you to start with drawing a tree containing numbers.

             1
           /   \
          2     3
           \   / \
            4 6   5  

Can you encode this tree using your Tree a data type, that is, write the tree as an expression with Node and Empty constructors?

Here are some hints:

• The top node contains 1 and two non-empty subtrees.

• The left subtree contains 2, one empty subtree and one non-empty subtree.

• The right subtree contains 3 and two non-empty subtrees.

• The level three nodes are all trees with empty subtrees.

Edit your post to insert the example tree there. Once you show us that you can do that, we can help you to proceed further.

You drew your tree wrong. The correct tree is:

              f 1
            /     \
         f 2       f 3
            \     /   \
           f 4  f 6   f 5

So you can only map functions with one argument, but not with two, three or more.

The idea is that you can (for example) add two to each element of the tree. So if you pass

             1
           /   \
          2     3           and (\x -> x + 2) or equivalently (+2)
           \   / \
            4 6   5  

to your function, e.g. tree2 = functionToTree (+2) tree1, you get back the amended tree:

             3
           /   \
          4     5
           \   / \
            6 8   7

So each element of the tree is replaced with a new element.