The simplest way to generically traverse a tree in haskell
Not sure if it's the simplest, but:
> data T = L | B T T deriving Data
> everything (++) (const [] `extQ` (\x -> [toConstr (x::T)])) (B L (B (B L L) L))
[B,L,B,B,L,L,L]
Here ++
says how to combine the results from subterms.
const []
is the base case for subterms who are not of type T
. For those of type T
, instead, we apply \x -> [toConstr (x::T)]
.
If you have multiple tree types, you'll need to extend the query using
const [] `extQ` (handleType1) `extQ` (handleType2) `extQ` ...
This is needed to identify the types for which we want to take the constructors. If there are a lot of types, probably this can be made shorter in some way.
Note that the code above is not very efficient on large trees since using ++
in this way can lead to quadratic complexity. It would be better, performance wise, to return a Data.Map.Map Constr Int
. (Even if we do need to define some Ord Constr
for that)
universe from the Data.Generics.Uniplate.Data
module can give you a list of all the sub-trees of the same type. So using Ilya's example:
data T = L | B T T deriving (Data, Show)
tree :: T
tree = B L (B (B L L) L)
λ> import Data.Generics.Uniplate.Data
λ> universe tree
[B L (B (B L L) L),L,B (B L L) L,B L L,L,L,L]
λ> fmap toConstr $ universe tree
[B,L,B,B,L,L,L]