Simon Jakobi pushed to branch wip/sjakobi/T27096 at Glasgow Haskell Compiler / GHC Commits: bb295a03 by Simon Jakobi at 2026-05-19T21:17:48+02:00 Implement List.elem via foldr ...in order to allow specialization to Eq instances. The implementation of notElem is updated for consistency.` Corresponding CLC proposal: https://github.com/haskell/core-libraries-committee/issues/412 Addresses #27096. - - - - - 5 changed files: - + changelog.d/elem-via-foldr-27096 - libraries/base/changelog.md - libraries/base/tests/perf/ElemNoFusion_O1.stderr - libraries/base/tests/perf/ElemNoFusion_O2.stderr - libraries/ghc-internal/src/GHC/Internal/List.hs Changes: ===================================== changelog.d/elem-via-foldr-27096 ===================================== @@ -0,0 +1,4 @@ +section: base +synopsis: Reimplement ``Data.List.elem`` and ``notElem`` using ``foldr`` to enable better specialization. +issues: #27096 +mrs: !15793 ===================================== libraries/base/changelog.md ===================================== @@ -1,5 +1,8 @@ # Changelog for [`base` package](http://hackage.haskell.org/package/base) +## 4.24.0.0 *TBA* + * Ensure that `Data.List.elem` and `notElem` can be specialized even when no list fusion happens. ([CLC proposal #412)(https://github.com/haskell/core-libraries-committee/issues/412)) + ## 4.23.0.0 *TBA* * Add `System.IO.hGetNewlineMode`. ([CLC proposal #370](https://github.com/haskell/core-libraries-committee/issues/370)) * Add `{-# WARNING in "x-partial" #-}` to `Data.List.{init,last}`. ===================================== 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'. -- @@ -1544,14 +1539,9 @@ elem x (y:ys) = x==y || elem x ys -- -- >>> 3 `notElem` [4..] -- * Hangs forever * -notElem :: (Eq a) => a -> [a] -> Bool -notElem _ [] = True -notElem x (y:ys)= x /= y && notElem x ys -{-# NOINLINE [1] notElem #-} -{-# RULES -"notElem/build" forall x (g :: forall b . (a -> b -> b) -> b -> b) - . notElem x (build g) = g (\ y r -> (x /= y) && r) True - #-} +notElem :: Eq a => a -> [a] -> Bool +notElem x = foldr (\y r -> x /= y && r) True +{-# INLINE notElem #-} -- | \(\mathcal{O}(n)\). 'lookup' @key assocs@ looks up a key in an association -- list. View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/bb295a035a1c77899e38e3d3e3ce2de8... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/bb295a035a1c77899e38e3d3e3ce2de8... You're receiving this email because of your account on gitlab.haskell.org.