How to apply a function to all elements of a tree?

user_12036912 0
Viewed 905
data RoseTree a = RoseNode a [RoseTree a] deriving Show

things :: RoseTree String
things = 
    RoseNode "thing" [
        RoseNode "animal" [
            RoseNode "cat" [], RoseNode "dog" []
        ],

        RoseNode "metal" [
            RoseNode "alloy" [
                RoseNode "steel" [], RoseNode "bronze" []
            ],
            RoseNode "element" [
                RoseNode "gold" [], RoseNode "tin" [], RoseNode "iron" []
            ]
        ],       
    ] 
-- Turns string into all upper case
allCaps :: String -> String
allCaps x = map toUpper x
-- This function uses allCaps as a helper function 
--  to turn the elements in tree into upper case
roseMap :: (a -> b) -> RoseTree a -> RoseTree b
roseMap  f  rtree = case rtree of
    RoseNode a []    ->  allCaps a
    RoseNode a sub   ->  Rose (allCaps a) (map (roseMap f sub)

that takes a function, and applies it to every element of a rosetree. Test the result by mapping the function allCaps to the rosetree things. All the elements should now be written in uppercase.

I have no idea about how to use recursion to write this function.

map-function tree recursion haskell
1 Answers

You are already using recursion. Indeed, you use roseMap f in terms of itself:

roseMap :: (a -> b) -> RoseTree a -> RoseTree b
roseMap f  rtree = case rtree of
    RoseNode a [] -> allCaps a
    RoseNode a sub -> Rose (allCaps a) (map (roseMap f sub))

But the above will not work for several reasons:

  1. you do not make use of f here. Indeed you write Rose (allCaps a), so you do not use f to map the elements;
  2. the sub should not be passed in the brackets of roseMap f;
  3. you should use RoseNode instead of Rose; and
  4. your first case, you return allCaps a, instead of RoseNode (allCaps a) [].

Making a distinction between a node with no children, or with children, is not necessary anway. We can define the mapping as:

roseMap :: (a -> b) -> RoseTree a -> RoseTree b
roseMap f (RoseNode a xs) = RoseNode (f a) (map (roseMap f) xs)

So here we use f a instead, and we perform a mapping on the children.

If we then perform a roseMap with allCaps as function, we get:

Prelude Data.Char> roseMap allCaps things
RoseNode "THING" [RoseNode "ANIMAL" [RoseNode "CAT" [],RoseNode "DOG" []],RoseNode "METAL" [RoseNode "ALLOY" [RoseNode "STEEL" [],RoseNode "BRONZE" []],RoseNode "ELEMENT" [RoseNode "GOLD" [],RoseNode "TIN" [],RoseNode "IRON" []]],RoseNode "FRUIT" [RoseNode "APPLE" [RoseNode "GRANNY SMITH" [],RoseNode "PINK LADY" []],RoseNode "BANANA" [],RoseNode "ORANGE" []],RoseNode "ASTRONOMICAL OBJECT" [RoseNode "PLANET" [RoseNode "EARTH" [],RoseNode "MARS" []],RoseNode "STAR" [RoseNode "THE SUN" [],RoseNode "SIRIUS" []],RoseNode "GALAXY" [RoseNode "MILKY WAY" []]]]

We do not need to implement the mapping ourself, we can enable the DeriveFunctor extension [ghc-doc], and let Haskell do the work for us:

{-# LANGUAGE DeriveFunctor #-}

data RoseTree a = RoseNode a [RoseTree a] deriving (Functor, Show)

the we can call this with fmap :: Functor f => (a -> b) -> f a -> f b:

Prelude Data.Char> fmap (map toUpper) things
RoseNode "THING" [RoseNode "ANIMAL" [RoseNode "CAT" [],RoseNode "DOG" []],RoseNode "METAL" [RoseNode "ALLOY" [RoseNode "STEEL" [],RoseNode "BRONZE" []],RoseNode "ELEMENT" [RoseNode "GOLD" [],RoseNode "TIN" [],RoseNode "IRON" []]],RoseNode "FRUIT" [RoseNode "APPLE" [RoseNode "GRANNY SMITH" [],RoseNode "PINK LADY" []],RoseNode "BANANA" [],RoseNode "ORANGE" []],RoseNode "ASTRONOMICAL OBJECT" [RoseNode "PLANET" [RoseNode "EARTH" [],RoseNode "MARS" []],RoseNode "STAR" [RoseNode "THE SUN" [],RoseNode "SIRIUS" []],RoseNode "GALAXY" [RoseNode "MILKY WAY" []]]]
user_675790
Related