catamorphism:
> On 12/2/07, Don Stewart <dons(a)galois.com> 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
