import Criterion.Main
import Text.Pretty.Simple
data Expr = A
| B Expr
| C [Expr]
deriving Show
nest 0 = id
nest n = nest (n-1) . B
test n = bench (show n) $ nf test' n
where
test' = pShowNoColor . flip nest (C [A,A])
main = defaultMain [bgroup "nest" $ map test [1..25]]Is O(2^n). Last five times (mean) on my machine:
21, 5.255 s
22, 9.401 s
23, 18.95 s
24, 41.77 s
25, 83.27 s
I think the problem occurs in putSurroundExpr which performs two traversals for each layer.
Is O(2^n). Last five times (mean) on my machine:
21, 5.255 s
22, 9.401 s
23, 18.95 s
24, 41.77 s
25, 83.27 s
I think the problem occurs in
putSurroundExprwhich performs two traversals for each layer.