Unexpected list non-fusion

Joachim Breitner mail at joachim-breitner.de
Mon Dec 12 22:20:12 CET 2011


Am Montag, den 12.12.2011, 15:37 -0500 schrieb wren ng thornton:
> I've noticed that take and filter are good producers (and consumers) for 
> list fusion, but takeWhile, drop, and dropWhile are not. Is there any 
> reason for this discrepancy?
> If not, would I need to go through the libraries@ process for fixing it, 
> or should I just submit a patch?

while preparing my guest lecture¹ about Haskell Performance recently I
also noticed that takeWhile (and concatMap!) are not setup for list
fusion, here is what I showed the students; it improved performance
considerably in the testcase.

takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' p xs = build $ \c n -> foldr (takeWhileF p c n) n xs
{-# INLINE takeWhile' #-}

takeWhileF p c n x xs = if p x then x `c` xs else n

Of course, for a proper inclusion one first has to find out if
takeWhile' is sufficiently fast even when not fused, or whether one has
to do the „replace first, try to fuse, and then try to replace back by
original function if not fused“ tick that is used for, e.g., (++).

But yes, you are right that all these function ought to be fusable.


¹ http://www.joachim-breitner.de/blog/archives/539-Guest-lecture-on-Haskell-performance.html
Joachim "nomeata" Breitner
  mail at joachim-breitner.de  |  nomeata at debian.org  |  GPG: 0x4743206C
  xmpp: nomeata at joachim-breitner.de | http://www.joachim-breitner.de/

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: <http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20111212/4aac2445/attachment.pgp>

More information about the Glasgow-haskell-users mailing list