implementing mapTree function

Question

i am asket to Define the function:

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b

Which takes a function and a binary tree, and produces a binary tree in which all nodes are the result of applying the function on the given tree

the binary tree is:

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a)

and my code doesnt complie. i am getting an error of:

error: Not in scope: data constructor ‘BinaryTree’
treeMap f (BNode x (BinaryTree l) (BinaryTree r)) =    |                                    ^^^^^^^^^^

my code:

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a)

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b
treeMap f Nil  = Nil
treeMap f (BNode x (BinaryTree l) (BinaryTree r)) =
    BNode (f x) (BinaryTree (treeMap f l)) (BinaryTree (treeMap f r))

Answer 1

Your pattern (BNode x (BinaryTree l) (BinaryTree r)) is not a valid pattern. Indeed the data definition of a binary tree says:

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a)

so that means that BNode is a data constructor that packs three arguments. The type of the last two arguments is BinaryTree a, but you can not use types in pattern matching.

You thus should use l and r as variables for these parameters (or you can use the data constructors of the BinaryTree a type).

The same when you construct a BinaryTree a type. You call the constructor with BNode x l r with x, l and r the values, you do not specify the types here in the expression. You can specify the types, byt then you use the :: operator.

You can thus fix your code with:

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b
treeMap f Nil  = Nil
treeMap f (BNode x l r) = BNode (f x) (treeMap f l) (treeMap f r)

or more elegant:

treeMap :: (a -> b) -> BinaryTree a -> BinaryTree b
treeMap f = go
    where go Nil = Nil
          go (BNode x l r) = BNode (f x) (go l) (go r)

That being said, you can let ghc derive the Functor instance for you, by using the DeriveFunctor pragma:

{-# LANGUAGE DeriveFunctor #-}

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a) deriving Functor

The treeMap is just fmap :: Functor f => (a -> b) -> f a -> f b with f ~ BinaryTree here.