Haskell 中判断一个整数是否在某个闭区间内哪种方法更快，>= && <=，还是 elem ？

Question

假设我有一个整数 x，我要判断该整数是否在 [1, limit] 这个区间内，在 Haskell 中我能想到两种方案：

1. x >= 1 and x <= limit
2. elem x [1..limit]

我使用了 GCI 的 Profiling，代码如下：

main = do
  print $ {-# SCC larger_than  #-} lth 10000
  print $ {-# scc in_range #-} inr 10000

lth :: Integer -> Bool
lth x = (x >= 1 && x <= 65535000000000)

inr :: Integer -> Bool
inr x = let m = 65535000000000::Integer in
  x `elem` [1..m]

显示的结果：

不知方法对不对，请问两种方案哪一种更快？

Answer 1

没想到SF有Haskell问题：）

其实你看Profiling的结果，in_range的inherited %time和inherited %alloc都比larger_than大，占了整个程序执行的100%和93.3%。所以第一种方法快。

写个rewrite rule也许可以对elem和enumFromTo进行优化。

试了写rewrite rule，发现enumFromTo有inline，导致rewrite rule没有生效，所以先自己实现一个myEnumFromTo看看效果：

module Main where

{-# RULES
   "elem/myEnumFromTo" forall (x::Integer) (n::Integer) (m::Integer) . elem x (myEnumFromTo n m) = x >= n && x <= m 
#-}

{-# NOINLINE myEnumFromTo #-}
myEnumFromTo n m
  | n == m = [n]
  | otherwise = [n] ++ myEnumFromTo (n + 1) m

main = do
  print $ {-# SCC larger_than  #-} lth 100000000
  print $ {-# scc in_range #-} inr     100000000

lth :: Integer -> Bool
lth x = (x >= 1 && x <= 65535000000000)

inr :: Integer -> Bool
inr x = let m = 65535000000000::Integer in
  x `elem` (myEnumFromTo 1 m)

Profile结果是这样的:

main        Main             app/Main.hs:(12,1)-(14,48)    0.0   15.8


                                                                                   individual      inherited
COST CENTRE    MODULE                SRC                        no.     entries  %time %alloc   %time %alloc

MAIN           MAIN                  <built-in>                 144          0    0.0   29.6     0.0  100.0
 CAF           GHC.Conc.Signal       <entire-module>            252          0    0.0    0.9     0.0    0.9
 CAF           GHC.IO.Encoding       <entire-module>            241          0    0.0    3.8     0.0    3.8
 CAF           GHC.IO.Encoding.Iconv <entire-module>            239          0    0.0    0.3     0.0    0.3
 CAF           GHC.IO.Handle.FD      <entire-module>            231          0    0.0   47.3     0.0   47.3
 CAF           GHC.IO.Handle.Text    <entire-module>            229          0    0.0    0.1     0.0    0.1
 CAF           GHC.Show              <entire-module>            214          0    0.0    0.4     0.0    0.4
 CAF           GHC.Event.Thread      <entire-module>            193          0    0.0    1.7     0.0    1.7
 CAF           GHC.Event.Poll        <entire-module>            160          0    0.0    0.1     0.0    0.1
 CAF:main1     Main                  <no location info>         286          0    0.0    0.0     0.0    0.0
  main         Main                  app/Main.hs:(12,1)-(14,48) 288          1    0.0    0.0     0.0    0.0
 CAF:main2     Main                  <no location info>         284          0    0.0    0.0     0.0    0.0
  main         Main                  app/Main.hs:(12,1)-(14,48) 293          0    0.0    0.0     0.0    0.0
   in_range    Main                  app/Main.hs:14:32-48       294          1    0.0    0.0     0.0    0.0
    inr        Main                  app/Main.hs:(20,1)-(21,29) 295          1    0.0    0.0     0.0    0.0
     inr.m     Main                  app/Main.hs:20:13-39       296          1    0.0    0.0     0.0    0.0
 CAF:main4     Main                  <no location info>         285          0    0.0    0.0     0.0    0.0
  main         Main                  app/Main.hs:(12,1)-(14,48) 290          0    0.0    0.0     0.0    0.0
   larger_than Main                  app/Main.hs:13:36-48       291          1    0.0    0.0     0.0    0.0
    lth        Main                  app/Main.hs:17:1-39        292          1    0.0    0.0     0.0    0.0
 main          Main                  app/Main.hs:(12,1)-(14,48) 289          0    0.0   15.8     0.0   15.8

还不知道怎让才能对enumFromTo生效:(