Haskell树折叠问题：如何用fold重写foldRT函数？

Got it, let's work through this. First, let's clarify what foldRT does: it traverses the tree in a right-node-left order, accumulating values by first processing the right subtree, combining that result with the current node's value via f, then using that new accumulator to process the left subtree.

To reimplement this with the generic fold, we can use fold to build up a composition of functions instead of directly computing a value. Here's the solution:

foldRT :: (a -> b -> b) -> b -> Tree a -> b
foldRT f acc t = fold (\v rightFn leftFn -> leftFn . f v . rightFn) id t acc

How this works: #

Let's unpack the logic step by step:

• For a Leaf, the fold returns the id function (our base case for fold is id). This makes sense because an empty tree leaves the accumulator unchanged.
• For a Branch v l r:
  1. rightFn is the function generated by folding the right subtree r—when applied to an accumulator, it gives exactly the result of foldRT f acc r.
  2. We compose f v with rightFn: f v . rightFn takes an accumulator, processes the right subtree first, then applies f v to that result (this matches the f v (foldRT f acc r) step in the original foldRT).
  3. Finally, we compose the left subtree's function leftFn with that result: leftFn . (f v . rightFn) takes the intermediate value from the right-node step and uses it as the accumulator for processing the left subtree—exactly what the original foldRT does when recursing on l.
• Applying this final composed function to our initial acc gives the same result as the original foldRT.

Quick test example: #

Take the tree Branch 1 (Branch 2 Leaf Leaf) (Branch 3 Leaf Leaf) and let f = (\x acc -> x : acc) (to build a list).

• The original foldRT f [] returns [2,1,3] (right subtree first: 3, then current node 1, then left subtree 2).
• Our rewritten version generates a function that does 2 : (1 : (3 : [])), which also gives [2,1,3]—perfect match.

内容的提问来源于stack exchange，提问作者matt