Strict functions

Ian Lynagh igloo@earth.li
Sun, 21 Oct 2001 12:19:06 +0100

```On Sat, Oct 20, 2001 at 01:11:05AM +1000, Andrew J Bromage wrote:
> G'day all.
>
> On Fri, Oct 19, 2001 at 02:30:59PM +0100, Ian Lynagh wrote:
>
> > Also, the prelude definition of zipWith has LVL whereas the following
> > definition has LVV. Why is something like the following not used?
> >
> > > zipWith                 :: (a->b->c) -> [a] -> [b] -> [c]
> > > zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
> > > zipWith _ _      []     = []
> > > zipWith _ _      _      = []
>
> Generally speaking, Haskell programmers don't like inserting more code
> with the only effect being to make the function less lazy.  This goes
> double for standard library code.
>
> I say "generally" because occasionally there's a good reason (e.g.
> forcing evaluation can make a program more space-efficient).  Is there
> a good reason behind your version of zipWith other than the strictness
> signature being more symmetrical? :-)

With the following code:

main :: IO()
main = putStrLn \$ show \$ last \$ zipa list (cycle "hello world")
where list = concat \$ replicate 1000000000 \$ replicate 10 'a'

zipa :: [a] -> [b] -> [(a, b)]
zipa (x:xs) (y:ys) = (x, y):zipa xs ys
zipa _ _ = []

zipb :: [a] -> [b] -> [(a, b)]
zipb (x:xs) (y:ys) = (x, y):zipb xs ys
zipb _ [] = []
zipb _ _ = []

I get

\$ time nice -n 10 ./W
('a','h')

real    148m50.013s
user    146m37.930s
sys     0m4.470s
\$

whereas changing the zipa to zipb gives me

\$ time nice -n 10 ./W
('a','h')

real    136m56.882s
user    135m13.690s
sys     0m2.370s
\$

which is a speedup of around 7 or 8 percent.

> If you really need a reason which doesn't involve bottom, consider a
> (fairly common) call such as:
>
> 	zipWith f xs [1..]
>
> If xs is finite, your version of zipWith would evaluate the infinite
> list [1..] one place beyond that which was really needed.

Sure, there is a single extra amount of evaluation needed to work out if
there is a following list item (I guess this could be quite high in more
complex cases - is this the reason?), but there is a constant time
speedup on every zip(With) call that actually does some zipping.

Ian

```