CODEWITHSUNDEEP
haskelldictionarytree
Petter Bjao
Petter Bjao

Reputation: 325

Define a Map for Tree data in Haskell

I have the a Tree data structure like this:

data Tree a = ATree a [Tree a] 
            deriving Show

Is it possible to write a higher-order function traverse with the following declaration which just traverses (or whatever) the tree and reconstructs it?

traverse :: (a -> b) -> Tree a -> Tree b

Please note the traverses signature. It doesn't get a list of Tree. It only accepts one node at a time.

I think the signature needs to change to accept lists in order to do this. Like this:

traverse :: (a -> b) -> [Tree a] -> [Tree b]

Upvotes: 1

Views: 455

Answers (1)

Lee
Lee

Reputation: 144136

traverse :: (a -> b) -> Tree a -> Tree b
traverse f (ATree e l) = ATree (f e) (map (traverse f) l)

Note your function has the same signature as fmap so you should implement Functor for your type:

instance Functor Tree where
    fmap f (ATree e l) = ATree (f e) (fmap (traverse f) l)

in fact you can have the compiler generate your functor instance for you:

{-# LANGUAGE DeriveFunctor #-}

data Tree a = ATree a [Tree a] deriving (Show, Functor)

Upvotes: 7

Related Questions