Folding over short static lists

Previous Topic Next Topic
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
Report Content as Inappropriate

Folding over short static lists

Joachim Breitner-2

a common pattern is
  x `elem` [a,b,c]
  x `elem` "/!#"
instead of
  x == a || x == b || x == c
  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.)


Joachim “nomeata” Breitner
  [hidden email]https://www.joachim-breitner.de/
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
Glasgow-haskell-users mailing list
[hidden email]

signature.asc (849 bytes) Download Attachment