Is there a standard function in Haskell that "scans" a tree?
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 as scan
a list- like operation , except that instead of returning a list, it should return a traversed tree. For example:
scan (+) 0 a
Should be reduced to:
Node 1
[Node 21
[Node 321
[Node 721 [],
Node 821 []],
Node 331 []],
Node 31 [],
Node 41 []]
Which accumulates sums through the tree. Is there a standard function for this?
source to share
There is no standard library function that does this. In the case of lists: Haskell has almost any function you can think of already in Data.List
, but Data.Tree
is actually quite sparse.
Luckily, the function you want is pretty 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 computes "721" as "1 + (20 + (400 + 300))", which prevents toggling the computation "1 + 20" - used in other branches.
The function below doesn't have this problem, but I'm leaving it in place because it might be useful depending on which 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
source to share
update: this gives different results than requested; but it does show a valuable general approach that can be useful where applicable, and is also useful here as a counterpoint.
It is quite possible to do such a traversal in the general case with the help of base
GHC. The class you are looking for Traversable
and mapAccum{R,L}
does the function fst
or snd
:
Let's not write our own instances:
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
Now we can get the parts we need:
import Data.Traversable
import Data.Foldable
data Tree a = Node a [Tree a]
deriving (Functor, Traversable, Foldable, Show)
Then the usage is pretty simple. If you don't need the latest battery, just use snd
.
main :: IO ()
main = print $ mapAccumL (\acc e -> (acc+e,acc+e)) 0 demo
demo :: Tree Int
demo =
Node 1 [Node 20.
[Node 300 [Node 400 []
, Node 500 []]
, Node 310 []
]
, Node 30 [], Node 40 []
]
source to share