Optimize Data.elem on enumerated lists.
Motivation
Consider the following code:
f a b c = elem a [b..c]
This code is in many cases functionally identical to
g a b c = a >= b && a <= c
.
The function f
runs in linear time while the function g
runs in constant time.
Proposal
Add a Rewrite-Rule that optimizes this kind of code. I guess it would have to look something like this:
{-# RULES "elem/range" forall (n :: Ord k => k) (l :: Ord k => k) (u :: Ord k => k). elem n (enumFromTo l u) = n >= l && n <= u #-}
This rule applied on all Ord-Instances is probably a bad idea for 2 reasons:
- The resulting code could be slower if
compare
is a lot more expensive than==
. - For Floats the behavior would be incorrect, if n is not an integer (
elem 1.5 [1..2]
).
That being said, I think this would be a useful optimization for all types, for which 1 and 2 are known to be false (Int, Word, Char, ...).