An alternative version of `levels` for `Data.Tree`

[xgrommx]

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

[jwaldmann]

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.

[xgrommx]

@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)

[jwaldmann]

measure it.

[xgrommx]

@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)