1

Trying to implement a mapTree in terms of foldTree.

data Tree a = Leaf   | Node (Tree a) a (Tree a) deriving Show

foldTree is shown here

foldTree :: b -> (b -> a -> b -> b) -> Tree a -> b
foldTree l n Leaf           = l
foldTree l n (Node lt x rt) = n (foldTree l n lt) x (foldTree l n rt)

This is what I have so far for mapTree so far but I'm relatively new to haskell and I'm not sure where to go from here

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f = foldTree Leaf (\x t1 t2 -> Node (f x) t1 t2)
Improve this question
1
  • look closely to how the things are ordered: Node (Tree a) a (Tree a) ; (b -> a -> b -> b) ; n (foldTree l n lt) x (foldTree l n rt) ; ====> n = (\ ..... -> Node .....(f x)..... ) . Commented Nov 3, 2020 at 16:55

1 Answer 1

Reset to default
0

I suppose this is an exercise / homework and only give you a nudge:

This Node (Tree a) a (Tree a) is:

  1. a left Tree
  2. a payload value of type a.
  3. a right Tree

in this order. And here (\x t1 t2 -> Node (f x) t1 t2) you construct a -value- (edit: Node!) out of

  1. something that looks / is named like a value f x
  2. tree1
  3. tree2

in that order.

Addressing the follow-up updated to mapTree f = foldTree Leaf (Node (f x) (\x t1 t2 -> t1 t2)): The "and here" above was deliberately vague, so lets have a look at

foldTree :: b -> (b -> a -> b -> b) -> Tree a -> b
--          1    \_______2________/       3      4

This takes:

  1. a value of type `b` for `Leafs`
  2. a combining function that takes:
    1. the result of the folded left tree `b`
    2. the value of the currently folded Node `a`
    3. the result of the folded right tree `b`
    4. and outputs a `b`
  3. the tree to be folded.
in this order. Your function `(\x t1 t2 -> Node (f x) t1 t2)` in place of 2 takes
  1. the value of the currently folded Node `a`
  2. the result of the folded left tree `b`
  3. the result of the folded right tree `b`
  4. and outputs a `b`
in that order.

So all you have to do is correct the order of both sides of the -> in (\x t1 t2 -> Node (f x) t1 t2).

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I've updated to mapTree f = foldTree Leaf (Node (f x) (\x t1 t2 -> t1 t2)) Is my implementation close? I see you say tree1 and tree 2 instead of left and right I'm guessing that part is totally wrong?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.