Data.List.foldr, etc. is a tougher call. Similar to Control.Monad you have to import it for many combinators, on the other hand you seem to at least nominally be asking for combinators for working with lists by implementing it.

As you mentioned, I see 3 ways to proceed for Data.List.foldr and their ilk.

1.) Given that Prelude is then exporting a type that subsumes it one option is to just remove them from Data.List. This would break some code that was explicitly referencing the qualified import from Data.List.

2.) Another option is to keep the more restricted type for Data.List.foldr. This breaks other code that relied on the fact that this was a re-export of the Prelude type to avoid needing qualification for those functions. If one of those proposals for re-exporting type restricted forms of things worked you might be able to get some traction here, but in their absence it strikes me as an awkward compromise. Lots of code imports Data.List unqualified.

3.) Data.List can just re-export the version from the Prelude. This means somewhat counter-intuitively that Data.List.foldr is generalized to Foldable, but it means that existing code that imported Data.List and just called foldr unqualified continues to work unmodified.

I tend to favor option 3 because the most existing code works with it unmodified, despite the slightly counter-intuitive state it puts things in. If it was possible to deprecate a re-export of a function from a module, deprecating the re-export of the foldr-like functions from Data.List would provide a path towards a more sane final state.

Mind you, I say this as 're-export the version from the Prelude' rather than have the Prelude re-export the version from Control.Monad not as a statement that we should flip any dependencies around in the implementation, but merely in a conversational sense based on how the modules are seen by the end user. Where the dependencies run the other way, obviously re-exports must flow the other way around.

-Edward