Traversing and filtering a tree in haskell

Question

I am pretty new to Haskell (still working on totally understanding monads). I have a problem where I have a tree like structure

type Tree = [DataA]

data DataA =  DataA1 [DataB] 
            | DataA2 String 
            | DataA3 String [DataA]
               deriving Show

data DataB =  DataB1 [DataA] 
            | DataB2 String 
            | DataB3 String [DataB]
               deriving Show

What I would like to do is be able to traverse this and generate a new tree with a filter. For example I may want to change all DataB2 in the tree to "foo".

I have seen examples of tree when they are in the same data section, and the constructors are similar.

In the python world, I would just traverse the list, match to whatever I needed, and replace the value.

In Haskell I am guessing that I need to be able to copy my tree, but how do you deal with lists buried in constructors and different data types?

Answer 1

You can use generic programming for this.

One such generic programming library is called Scrap Your Boilerplate. At the very top of your module, enable Scrap Your Boilerplate by writing:

{-# LANGUAGE DeriveDataTypeable #-}

Import module Data.Generics. Then besides Show, also derive Typeable and Data instances for your datatypes.

Now you can write the function you requested like this:

toFoo :: Data a => a -> a
toFoo = everywhere (mkT step)
  where
    step (DataA2 _)  = DataA2 "foo"
    step x           = x

That's all you need to do to make this work. For example, when you call toFoo [DataA1 [], DataA2 "hi", DataA3 "yo" []], the answer is [DataA1 [],DataA2 "foo",DataA3 "yo" []].

Hope this helps!