On Haskell, there a standard function that performs "scan" on a tree?

Question

I have a tree:

a :: Tree Double
a = 
    Node 1 
       [Node 20 
           [Node 300 
               [Node 400 [], 
               Node 500 []], 
           Node 310 []], 
       Node 30 [], 
       Node 40 []]

I want to apply it an scan operation similar to lists - except that, instead of returning a list, it should return a tree with the travelled paths. For example:

scan (+) 0 a

Should reduce to:

Node 1 
    [Node 21 
        [Node 321 
            [Node 721 [], 
            Node 821 []], 
        Node 331 []], 
    Node 31 [], 
    Node 41 []]

Which is accumulated the sums through the tree. Is there a standard function for this?

Answer 1

There is no standard library function that does this. In the case of lists: Haskell has just about any function you can think of already in Data.List, but Data.Tree is actually pretty sparse.

Fortunately the function you want is quite simple.

scan f ~(Node r l) = Node r $ map (fmap (f r) . scan f) l

--edit--

The above function has a problem: in the example given by the OP it calculates the "721" as "1 + (20 + (400 + 300))", which prevents the "1 + 20" calculation from being re-used in the other branches.

The below function doesn't have this problem, but I'm leaving the original one in place because it can still be useful depending on what function is passed as the first argument.

scan f ~(Node r l) = Node r $ map (scan' r) l where
  scan' a ~(Node n b) = let a' = f a n in Node a' $ map (scan' r) b