[Haskell-cafe] Possible Improvements

[Don Stewart]

catamorphism:
> On 12/2/07, Don Stewart <dons at 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