catamorphism:

On 12/2/07, Don Stewart wrote:

...

prstanley:

...

Hi data Tree = Leaf Int | Node Tree Int Tree

occurs :: Int -> Tree -> Bool occurs m (Leaf n) = m == n occurs m (Node l n r) = m == n || occurs m l || occurs m r

It works but I'd like to know if it can be improved in any way.

You could probably get away with:

data Tree = Leaf !Int | Node Tree !Int Tree

but that's a minor issue.

IMO, there's no reason to even think about putting in the strictness annotations unless you've identified this datatype as part of a performance bottleneck in production code. Otherwise, there's no need to clutter your code and your mind with them :-)

Very true ("a minor issue"). However, *rarely* do you want lazines in the atomic types (Int,Char,Word,Integer, et al) A little test: 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 Fully lazy: data Tree = Leaf Int | Node Tree Int Tree $ time ./A 25 49 ./A 25 18.20s user 0.04s system 99% cpu 18.257 total ^^^^^^ 3556K heap use. 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. You'll be hard pressed to do better in C here. Finally, strict in the spine and elements: data Tree = Leaf !Int | Node !Tree !Int !Tree $ time ./A 25 A: out of memory (requested 1048576 bytes) ./A 25 11.46s user 2.60s system 97% cpu 14.379 total 657M heap use ^^^^ Lesson: * Full strictness == teh suckness. * Mixed lazy and strict == flexible and efficient data types. Makes me wonder why Map is strict in the spine, data Map k a = Tip | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) Anyone know? Cheers, Don