Map function for custom n-ary tree

Question

I'm trying to get a mapping function like this working for an n-ary tree, but am struggling.

data NTree a = Leaf a | Node a [NTree a]

ntreeMap :: (a -> b) -> NTree a -> NTree b
ntreeMap f (Leaf x) = Leaf (f x)
ntreeMap f (Node y t) = Node (ntreeMap f y) (ntreeMap f t)

gives me

 Type error in application
*** Expression     : ntreeMap f t
*** Term           : t
*** Type           : [NTree b]
*** Does not match : NTree a

Could someone give me a pointer as to where I'm going wrong? Thanks

Answer 1

You have two problems here. One is that you need not invoke ntreeMap recursively for y in the Node case as it is of type a and not NTree a:

ntreeMap f (Node y t) = Node (f y) (ntreeMap f t)

The second one is that t is a list of trees and your function only maps over a single tree, so it should be

ntreeMap f (Node y t) = Node (f y) (map (ntreeMap f) t)

Answer 2

BTW: Your type is a Functor.

An interesting thing about Functors is that there's only one way for a type to be a Functor (and adhering to the Functor laws).

Therefore Functor instances can be automatically derived:

{-# LANGUAGE TemplateHaskell #-}

import Data.DeriveTH

data NTree a = Leaf a | Node a [NTree a]
$( derive makeFunctor ''NTree )

ntreeMap :: (a -> b) -> NTree a -> NTree b
ntreeMap = fmap

Answer 3

While I think Rüdiger's answer is the best one I just wanted to add that in GHC 6.12 you can automatically derive a Functor instance for your datatype:

{-# LANGUAGE -DeriveFunctor #-}
data NTree a = Leaf a | Node a [NTree a]
  deriving Functor