Skip to content

Data.OldList.elemIndex generates a PAP

Currently, the definition of Data.OldList.elemIndex looks like

elemIndex       :: Eq a => a -> [a] -> Maybe Int
elemIndex x     = findIndex (x==)

But this definition is problematic, because it results in a PAP in codegen. To understand why, here's the code for findIndex and its callee findIndices:

findIndex       :: (a -> Bool) -> [a] -> Maybe Int
findIndex p     = listToMaybe . findIndices p

findIndices      :: (a -> Bool) -> [a] -> [Int]
{-# INLINABLE findIndices #-}
findIndices ... -- not important; large enough that it won't inline in `findIndex`

we get the following code for elemIndex:

elemIndex
  = \ (@a) ($dEq :: Eq a) (a1 :: a) ->
      let {
        p [Dmd=LCS(L)] :: a -> Bool
        [LclId]
        p = == @a $dEq a1 } in
      \ (x :: [a]) ->
        case findIndices @a p x of {
          [] -> GHC.Maybe.Nothing @Int;
          : y ys -> GHC.Maybe.Just @Int y
        }

with a (potentially non-cheap) let between two lambda binders; a PAP of arity 2.

And in Prep, we will actually have to allocate a local let for the last lambda:

      let {
        sat [Occ=Once1T[0]] :: [a] -> GHC.Maybe.Maybe GHC.Types.Int
        [LclId]
        sat
          = \ (x [Occ=Once1] :: [a]) ->
              case findIndices @a p x of {
                [] -> GHC.Maybe.Nothing @GHC.Types.Int;
                : y [Occ=Once1] _ [Occ=Dead] -> GHC.Maybe.Just @GHC.Types.Int y
              } } in
      sat

I suggest to eta-expand the definition of elemIndex so that we don't get a PAP. Useful (==) implementations have almost always arity 2 anyway, so the PAP will share no work whatsoever.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information