containers
containers copied to clipboard
An alternative version of `levels` for `Data.Tree`
Hello everyone, how about an alternative version levels
for Data.Tree
?
levels :: Tree a -> [[a]]
levels t = unfoldr go [t] where
go [] = Nothing
go xs = Just . foldMap (\x -> ([rootLabel x], subForest x)) $ xs
seems slower and needs more space than the current implementation (extra allocations for Maybe and Pair)
crude way of measuring, in ghci
import Data.Tree
bin n = Node () $ map bin [0..n-1]
t = bin 18
:set +s
length $ concat $ levels t -- from Data.Tree
262144
(0.15 secs, 58,787,192 bytes)
length $ concat $ lvls t -- your proposal
262144
(0.94 secs, 136,944,168 bytes)
do you have other data? Perhaps ghc's inliner can remove extra allocations - but that needs proof.
@jwaldmann Ok, I have another variant
levels :: Tree a -> [[a]]
levels t = unfoldr go [t] where
go [] = Nothing
go xs = Just (fmap rootLabel xs, xs >>= subForest)
measure it.
@jwaldmann
*Main> length $ concat $ levels t
262144
(0.03 secs, 61,413,320 bytes)
*Main> length $ concat $ T.levels t
262144
(0.03 secs, 59,313,488 bytes)