dons:
Strict in the elements, lazy in the spine:
data Tree = Leaf !Int | Node Tree !Int Tree
$ time ./A 25 49 ./A 25 14.41s user 0.03s system 99% cpu 14.442 total ^^^^^^ 3056K heap use.
And, finally, we can get a little speedup again over the basic element-strict, -funboxed-strict-fields tree by parallelising some of the traversals. Nothing great, but I didn't try very hard: Serial code: {-# OPTIONS -O2 -funbox-strict-fields #-} import System.Environment data Tree = Leaf !Int | Node Tree !Int Tree main = do n <- getArgs >>= readIO . head let t = make (n*2) n print (check t) make :: Int -> Int -> Tree make i 0 = Node (Leaf 0) i (Leaf 0) make i d = Node (make (i2-1) d2) i (make i2 d2) where i2 = 2*i d2 = d-1 check :: Tree -> Int check (Leaf _) = 0 check (Node l i r) = i + check l - check r Running: $ time ./A 28 55 ./A 28 24.39s user 0.03s system 99% cpu 24.424 total Ok. Now, parallelise that recursive call in 'check': check :: Tree -> Int check (Leaf _) = 0 check (Node l i r) = lp `par` (rp `pseq` i + lp - rp) -- <-- where lp = check l rp = check r Super-simple strategy -- will register too many sparks, but what the heh... $ time ./B 28 +RTS -N2 55 ./B 28 +RTS -N2 31.81s user 0.14s system 147% cpu 21.700 total Pretty good for a naive strategy, and only one branch, on one line had to be modified. Control.Parallel, yay! -- Don