How do I define map and fold on search trees?

I have a search tree that开发者_如何学编程's defined as:

data (Ord a) => Stree a = Null | Fork (Stree a) a (Stree a) deriving Show 

and I have to define two functions, mapStree:

mapStree :: (Ord b, Ord a) => (a -> b) -> Stree a -> Stree b

and foldStree:

foldStree :: (Ord a) => (b -> a -> b -> b) -> b -> Stree a -> b

I don't fully understand what's going on and don't know how to do this.

You want your map to apply a function to any label carried by your tree. This means that any occurrence of a is to be changed to an occurrence to b, using the function given as a transformation function.

To do this, you'll need to figure out what to do with each possible constructor of the Stree. Now, Null is easy -- it won't depend on a in the first place. Trickier is what to do with Fork. In Fork, there is one a, and two further Strees sitting around, so you need functions that take a -> b and that take Stree a -> Stree b. For the former, the invocation of mapStree gives you a function, and for the latter, mapStree f has the call signature you need (by partial application!).

For foldStree, you have some accumulation type b and your labeltype a, and an accumulation function that takes two values of type b and a value of type a and produces a b. This is helpful, not in the least because that accumulation function mirrors what you might have at any given Fork in the tree: by recursion you can assume you have results from both left and right Stree, and it only remains to combine those with the a value you have in the middle to give a new b value to hand up the recursion. The b parameter to foldStree provides you with enough of a standard value to get the whole thing started by getting a value for each leaf.

Thus, your foldStree will also need to be defined on the possible constructors: picking out the parameter for a Null value, and then for a Fork value, it needs to recurse into both Stree values before combining everything with the parameter combining function.

Please clarify in comments whether this helps you enough to deal with the problem: I (and many others here) can clarify, but the hope is for you to learn how to do it rather than to just hand you code.

I highly recommend Lecture 5 from this course.