Resolved.

I don't have a full understanding either, but some observations:

List ( and Boolean, etc. ) are newtypes, which have no runtime overhead, so everything is function application ( foldr is actually a no-op! ) which may be optimised by GHC in weird, unpredictable, unintuitive, but aggressive and very efficient, ways. I'm no longer a beginner in FP, Haskell and GHC, but I can't always predict performance characteristics either. Memoisation can be fickle; sometimes it works and sometimes it doesn´t.

"a single foldr per list argument" is not the be-all-and-end-all of runtime performance; it is mostly there to clarify that you can't use tail ( which is necessarily O(n) ) to simulate pattern matching because it will completely bugger performance, but there are more ways to bugger performance. Using a single foldr in append may postpone evaluation of the other argument long enough that it is ultimately faster than using two, which may not be lazied away long enough. Encapsulating a foldr in cons may help because of memoisation somehow - but I'm speculating here; this is where I lose understanding of performance as well.

Ultimately, if it works, it works. Which is somewhat unsatisfactory, because the test framework is not very good at showing where a timeout happens. And performance analysis in GHC Haskell is not straightforward, esp. for an FP beginner. My apologies. It will probably get better for you; you seem a smart and experienced programmer ( you were one of the first solvers I noticed and followed on here, 7 years ago ), and in time, you'll learn.

There seems to be something wrong with your sortBy as well - it is indeed timing out ( yay for the View Solution on comments :). It might be your append, which has two foldrs where one would suffice ( changing that makes sortBy not time out ). Have a look at the GHC source for (++). That does pattern mathing, but it might give you a hint at how to get away with using one foldr instead of two.

OT: I've written lots of compilers. Some kata ask for assembly compilers ( cq. interpreters ), and I've done those in both JS and Haskell; I've also written several LC compilers in both JS and Haskell. This kata only uses an embedded parser, not a complete compiler, to check LC syntax embedded in Haskell ( which is ported / reused in several embedded LC kata in JS, Python and Haskell ). Piece de resistance is the LC to JS compiler that's underlying LC as a CW language of course - but credit where credit is due: Carrot did the compiler part on that one; I only wrote the parser part. I did write a LC to JS compiler for the Compiler to Lambda Calculus kata, but that uses strict evaluation ( much easier :), as opposed to the lazy evaluation for the LC to JS language compiler.

Looking at your solution, I see tail in your zipWith, which makes that O(n^2). That is probably what makes you fail performance tests ( which, incidentally, is one of the reasons this is a 1kyu kata :P ).

Does this answer your question?

Sorting can't be done in O(n), so "single foldr per list argument" does not apply to sortBy. My own solution uses insertion sort. If you have performance problems, make sure drop and zipWith are O(n) and not O(n^2).

My apologies for the confusion. Should this be explicitly clarified in the description?

thanks for the tip

Rewrote the description to remove all the irrelevant info.

Fixed

handled

There's a bigger problem with it now ..

Fixed

Added

That loophole is now fixed. Thanks for the bug report.

Lots of native array methods has already been disabled.

Sure you can do that, but in the end it's probably the easiest function to implement out of all of them, so I guess it doesn't matter that much.

Yeah... I guess it doesn't skip that much using a Proxy. Thanks for the help!