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

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 has
to say about it.)


Joachim “nomeata” Breitner
  [hidden email]
  XMPP: [hidden email] • OpenPGP-Key: 0xF0FBF51F
  Debian Developer: [hidden email]
Glasgow-haskell-users mailing list
[hidden email]

signature.asc (849 bytes) Download Attachment