Simon Jakobi pushed to branch wip/sjakobi/T27096 at Glasgow Haskell Compiler / GHC Commits: f020dd1f by Simon Jakobi at 2026-04-15T23:32:18+02:00 Implement List.elem via foldr ...in order to allow specialization to Eq instances. Addresses #27096. - - - - - 3 changed files: - libraries/base/tests/perf/ElemNoFusion_O1.stderr - libraries/base/tests/perf/ElemNoFusion_O2.stderr - libraries/ghc-internal/src/GHC/Internal/List.hs Changes: ===================================== libraries/base/tests/perf/ElemNoFusion_O1.stderr ===================================== @@ -1,5 +1,38 @@ -noFusionElemSort = \ x x1 -> elem $fEqInt x (actualSort gtInt x1) +noFusionElemSort + = \ x x1 -> + joinrec { + go1 ds + = case ds of { + [] -> False; + : y ys -> + case x of { I# x2 -> + case y of { I# y1 -> + case ==# x2 y1 of { + __DEFAULT -> jump go1 ys; + 1# -> True + } + } + } + }; } in + jump go1 (actualSort gtInt x1) noFusionElemNonEmptyToList - = \ x x1 -> case x1 of { :| a1 as -> elem $fEqInt x (: a1 as) } + = \ x x1 -> + case x1 of { :| a1 as -> + joinrec { + go1 ds + = case ds of { + [] -> False; + : y ys -> + case x of { I# x2 -> + case y of { I# y1 -> + case ==# x2 y1 of { + __DEFAULT -> jump go1 ys; + 1# -> True + } + } + } + }; } in + jump go1 (: a1 as) + } ===================================== libraries/base/tests/perf/ElemNoFusion_O2.stderr ===================================== @@ -1,5 +1,54 @@ -noFusionElemSort = \ x x1 -> elem $fEqInt x (actualSort gtInt x1) +noFusionElemSort + = \ x x1 -> + case actualSort gtInt x1 of { + [] -> False; + : y ys -> + case x of { I# x2 -> + case y of { I# y1 -> + case ==# x2 y1 of { + __DEFAULT -> + joinrec { + go1 ds + = case ds of { + [] -> False; + : y2 ys1 -> + case y2 of { I# y3 -> + case ==# x2 y3 of { + __DEFAULT -> jump go1 ys1; + 1# -> True + } + } + }; } in + jump go1 ys; + 1# -> True + } + } + } + } noFusionElemNonEmptyToList - = \ x x1 -> case x1 of { :| a1 as -> elem $fEqInt x (: a1 as) } + = \ x x1 -> + case x1 of { :| a1 as -> + case x of { I# x2 -> + case a1 of { I# y -> + case ==# x2 y of { + __DEFAULT -> + joinrec { + go1 ds + = case ds of { + [] -> False; + : y1 ys -> + case y1 of { I# y2 -> + case ==# x2 y2 of { + __DEFAULT -> jump go1 ys; + 1# -> True + } + } + }; } in + jump go1 as; + 1# -> True + } + } + } + } ===================================== libraries/ghc-internal/src/GHC/Internal/List.hs ===================================== @@ -1517,14 +1517,9 @@ all p (x:xs) = p x && all p xs -- -- >>> 3 `elem` [4..] -- * Hangs forever * -elem :: (Eq a) => a -> [a] -> Bool -elem _ [] = False -elem x (y:ys) = x==y || elem x ys -{-# NOINLINE [1] elem #-} -{-# RULES -"elem/build" forall x (g :: forall b . (a -> b -> b) -> b -> b) - . elem x (build g) = g (\ y r -> (x == y) || r) False - #-} +elem :: Eq a => a -> [a] -> Bool +elem x = foldr (\y r -> x == y || r) False +{-# INLINE elem #-} -- | 'notElem' is the negation of 'elem'. -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/f020dd1f37acf6e7ac5e26e96ad15e18... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/f020dd1f37acf6e7ac5e26e96ad15e18... You're receiving this email because of your account on gitlab.haskell.org.