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
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:
| 1 | +section: base
|
|
| 2 | +synopsis: Reimplement ``Data.List.elem`` and ``notElem`` using ``foldr`` to enable better specialization.
|
|
| 3 | +issues: #27096
|
|
| 4 | +mrs: !15793 |
| 1 | 1 | # Changelog for [`base` package](http://hackage.haskell.org/package/base)
|
| 2 | 2 | |
| 3 | +## 4.24.0.0 *TBA*
|
|
| 4 | + * 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))
|
|
| 5 | + |
|
| 3 | 6 | ## 4.23.0.0 *TBA*
|
| 4 | 7 | * Add `System.IO.hGetNewlineMode`. ([CLC proposal #370](https://github.com/haskell/core-libraries-committee/issues/370))
|
| 5 | 8 | * Add `{-# WARNING in "x-partial" #-}` to `Data.List.{init,last}`.
|
| 1 | -noFusionElemSort = \ x x1 -> elem $fEqInt x (actualSort gtInt x1)
|
|
| 1 | +noFusionElemSort
|
|
| 2 | + = \ x x1 ->
|
|
| 3 | + joinrec {
|
|
| 4 | + go1 ds
|
|
| 5 | + = case ds of {
|
|
| 6 | + [] -> False;
|
|
| 7 | + : y ys ->
|
|
| 8 | + case x of { I# x2 ->
|
|
| 9 | + case y of { I# y1 ->
|
|
| 10 | + case ==# x2 y1 of {
|
|
| 11 | + __DEFAULT -> jump go1 ys;
|
|
| 12 | + 1# -> True
|
|
| 13 | + }
|
|
| 14 | + }
|
|
| 15 | + }
|
|
| 16 | + }; } in
|
|
| 17 | + jump go1 (actualSort gtInt x1)
|
|
| 2 | 18 | |
| 3 | 19 | noFusionElemNonEmptyToList
|
| 4 | - = \ x x1 -> case x1 of { :| a1 as -> elem $fEqInt x (: a1 as) }
|
|
| 20 | + = \ x x1 ->
|
|
| 21 | + case x1 of { :| a1 as ->
|
|
| 22 | + joinrec {
|
|
| 23 | + go1 ds
|
|
| 24 | + = case ds of {
|
|
| 25 | + [] -> False;
|
|
| 26 | + : y ys ->
|
|
| 27 | + case x of { I# x2 ->
|
|
| 28 | + case y of { I# y1 ->
|
|
| 29 | + case ==# x2 y1 of {
|
|
| 30 | + __DEFAULT -> jump go1 ys;
|
|
| 31 | + 1# -> True
|
|
| 32 | + }
|
|
| 33 | + }
|
|
| 34 | + }
|
|
| 35 | + }; } in
|
|
| 36 | + jump go1 (: a1 as)
|
|
| 37 | + }
|
|
| 5 | 38 |
| 1 | -noFusionElemSort = \ x x1 -> elem $fEqInt x (actualSort gtInt x1)
|
|
| 1 | +noFusionElemSort
|
|
| 2 | + = \ x x1 ->
|
|
| 3 | + case actualSort gtInt x1 of {
|
|
| 4 | + [] -> False;
|
|
| 5 | + : y ys ->
|
|
| 6 | + case x of { I# x2 ->
|
|
| 7 | + case y of { I# y1 ->
|
|
| 8 | + case ==# x2 y1 of {
|
|
| 9 | + __DEFAULT ->
|
|
| 10 | + joinrec {
|
|
| 11 | + go1 ds
|
|
| 12 | + = case ds of {
|
|
| 13 | + [] -> False;
|
|
| 14 | + : y2 ys1 ->
|
|
| 15 | + case y2 of { I# y3 ->
|
|
| 16 | + case ==# x2 y3 of {
|
|
| 17 | + __DEFAULT -> jump go1 ys1;
|
|
| 18 | + 1# -> True
|
|
| 19 | + }
|
|
| 20 | + }
|
|
| 21 | + }; } in
|
|
| 22 | + jump go1 ys;
|
|
| 23 | + 1# -> True
|
|
| 24 | + }
|
|
| 25 | + }
|
|
| 26 | + }
|
|
| 27 | + }
|
|
| 2 | 28 | |
| 3 | 29 | noFusionElemNonEmptyToList
|
| 4 | - = \ x x1 -> case x1 of { :| a1 as -> elem $fEqInt x (: a1 as) }
|
|
| 30 | + = \ x x1 ->
|
|
| 31 | + case x1 of { :| a1 as ->
|
|
| 32 | + case x of { I# x2 ->
|
|
| 33 | + case a1 of { I# y ->
|
|
| 34 | + case ==# x2 y of {
|
|
| 35 | + __DEFAULT ->
|
|
| 36 | + joinrec {
|
|
| 37 | + go1 ds
|
|
| 38 | + = case ds of {
|
|
| 39 | + [] -> False;
|
|
| 40 | + : y1 ys ->
|
|
| 41 | + case y1 of { I# y2 ->
|
|
| 42 | + case ==# x2 y2 of {
|
|
| 43 | + __DEFAULT -> jump go1 ys;
|
|
| 44 | + 1# -> True
|
|
| 45 | + }
|
|
| 46 | + }
|
|
| 47 | + }; } in
|
|
| 48 | + jump go1 as;
|
|
| 49 | + 1# -> True
|
|
| 50 | + }
|
|
| 51 | + }
|
|
| 52 | + }
|
|
| 53 | + }
|
|
| 5 | 54 |
| ... | ... | @@ -1517,14 +1517,9 @@ all p (x:xs) = p x && all p xs |
| 1517 | 1517 | --
|
| 1518 | 1518 | -- >>> 3 `elem` [4..]
|
| 1519 | 1519 | -- * Hangs forever *
|
| 1520 | -elem :: (Eq a) => a -> [a] -> Bool
|
|
| 1521 | -elem _ [] = False
|
|
| 1522 | -elem x (y:ys) = x==y || elem x ys
|
|
| 1523 | -{-# NOINLINE [1] elem #-}
|
|
| 1524 | -{-# RULES
|
|
| 1525 | -"elem/build" forall x (g :: forall b . (a -> b -> b) -> b -> b)
|
|
| 1526 | - . elem x (build g) = g (\ y r -> (x == y) || r) False
|
|
| 1527 | - #-}
|
|
| 1520 | +elem :: Eq a => a -> [a] -> Bool
|
|
| 1521 | +elem x = foldr (\y r -> x == y || r) False
|
|
| 1522 | +{-# INLINE elem #-}
|
|
| 1528 | 1523 | |
| 1529 | 1524 | -- | 'notElem' is the negation of 'elem'.
|
| 1530 | 1525 | --
|
| ... | ... | @@ -1544,14 +1539,9 @@ elem x (y:ys) = x==y || elem x ys |
| 1544 | 1539 | --
|
| 1545 | 1540 | -- >>> 3 `notElem` [4..]
|
| 1546 | 1541 | -- * Hangs forever *
|
| 1547 | -notElem :: (Eq a) => a -> [a] -> Bool
|
|
| 1548 | -notElem _ [] = True
|
|
| 1549 | -notElem x (y:ys)= x /= y && notElem x ys
|
|
| 1550 | -{-# NOINLINE [1] notElem #-}
|
|
| 1551 | -{-# RULES
|
|
| 1552 | -"notElem/build" forall x (g :: forall b . (a -> b -> b) -> b -> b)
|
|
| 1553 | - . notElem x (build g) = g (\ y r -> (x /= y) && r) True
|
|
| 1554 | - #-}
|
|
| 1542 | +notElem :: Eq a => a -> [a] -> Bool
|
|
| 1543 | +notElem x = foldr (\y r -> x /= y && r) True
|
|
| 1544 | +{-# INLINE notElem #-}
|
|
| 1555 | 1545 | |
| 1556 | 1546 | -- | \(\mathcal{O}(n)\). 'lookup' @key assocs@ looks up a key in an association
|
| 1557 | 1547 | -- list.
|