Optimization opportunity: hidden identity functions.

Motivation

See my discourse thread for the background story.

I am investigating if stream fusion could replace foldr/build fusion in base. During the investigation I've encountered bad benchmark results for the streamed drop function: it is up to 20x slower than Prelude.drop. I've looked at the core and found that the streamed drop boiles down to a function like this:

drop :: Int -> [a] -> [a]
drop 0 [] = []
drop 0 (x:xs) = x : drop 0 xs -- [1]
drop n [] = []
drop n (x:xs) = drop (n - 1) xs

The main difference with Prelude.drop is that this function walks over the remainder of the list that it does not drop (see the recursive call at [1]). That is extremely inefficient. In my benchmarks it is up to 20x slower than Prelude.drop because of the extra allocation and subsequent copying of the remainder of the list after dropping.

Proposal

I think this function could be optimized further. First of all, SpecConstr could split it into two:

drop :: Int -> [a] -> [a]
drop 0 [] = []
drop 0 (x:xs) = x : drop0 xs
drop n [] = []
drop n (x:xs) = drop (n - 1) xs

drop0 :: [a] -> [a]
drop0 [] = []
drop0 (x:xs) = x : drop0 xs

SpecConstr doesn't do this optimization yet, but #22781 tracks that issue.

Then a special optimization pass could recognize that drop0 is an identity function and optimize it further to:

drop :: Int -> [a] -> [a]
drop 0 [] = []
drop 0 (x:xs) = x : drop0 xs
drop n [] = []
drop n (x:xs) = drop (n - 1) xs

drop0 :: [a] -> [a]
drop0 xs = xs

This optimization could simply look for the pattern:

<f> xs =
  case xs of
    [] -> []
    x : xs -> x : <f> xs

In Core and replace that with <f> xs = xs.

It also shouldn't be hard to generalize that for any ADT.

Then finally the result of that optimization already simplifies to (modulo unboxing):

drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop n [] = []
drop n (x:xs) = drop (n - 1) xs

Which is what we want.