During the early days of the App Store the guidelines prohibited duplicating system functionality, but that hasn’t been the case in a long time, wasn’t retroactive, didn’t apply to non-system Apple software and I’m not sure how strictly it was enforced in the first place anyway.

Not sure about apple but it did happen with Twitter and third party clients.

F.lux for example.

Was f.lux ever available on the Mac App Store? I downloaded it for free from their website... It wasn't allowed on the iOS App Store because it needs access to private APIs.

I thought it was kicked out of the iOS App Store for using the private APIs, after it was accepted. That is fair on its face, because those are the rules Apple set. However, the F.lux developers pleaded with Apple to open up the APIs needed to implement their software and were ignored. Then Apple copied their functionality as a built in feature of the OS. So the full story doesn’t make Apple look good.

It was never on the App store, they just offered a download that could be installed without jailbreaking: https://justgetflux.com/sideload/

Flux

AppGratis.

what was the similar feature Apple wanted to release?

App discovery services.

I don't know about that. iOS 7 didn't have any app discovery improvements in the App store. Unless you want to count slightly different top apps lists and the "Near me" feature. It wasn't until iOS 8 (a year and a half later) that they added the Explore tab.