Folding over short static lists

Joachim Breitner mail at joachim-breitner.de
Tue Feb 28 19:25:12 UTC 2017


Hi,

a common pattern is
  x `elem` [a,b,c]
or
  x `elem` "/!#"
instead of
  x == a || x == b || x == c
or
  x == '/' || x == '!' || x == '#'.

This used to be also what hlint suggested, although that hint was
removed https://github.com/ndmitchell/hlint/issues/31.

Upon closer inspection it seems that the compiler is not optimizing the
former to the latter (more efficient, as allocation-free) form, which
mildly surprised me.

I guess the problem is described in this note in GHC/Base.hs:

-- The foldr/cons rule looks nice, but it can give disastrously
-- bloated code when commpiling
--      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
-- i.e. when there are very very long literal lists
-- So I've disabled it for now. We could have special cases
-- for short lists, I suppose.
-- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)

Now I am quite demanding of my compiler, and in particular I expect it
to make a more informed choice here. Is there a good way of making an
informed choice here? Up to what length of the list is it a good idea
to do this? And can we implement it? Maybe simply with a few static
rules for list lengths up to a certain, short length?

(Maybe I should try that on a branch and see what perf.haskell.org has
to say about it.)

Greetings,
Joachim

-- 
Joachim “nomeata” Breitner
  mail at joachim-breitner.dehttps://www.joachim-breitner.de/
  XMPP: nomeata at joachim-breitner.de • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: nomeata at debian.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: This is a digitally signed message part
URL: <http://mail.haskell.org/pipermail/glasgow-haskell-users/attachments/20170228/5a3c4c86/attachment.sig>


More information about the Glasgow-haskell-users mailing list